Smalltalk

Gibt es eigentlich "mathematische Algorithmen", die ungefähre Aussagen liefern über die Anzahl der Zugmöglichkeiten pro Zug, unabhängig davon ob sinnvoll oder nicht?
Nehmen wir Zug 1: Weiß kann jeden der Bauern 1 oder 2 Felder vorrücken (sprich 16 Zugmöglichkeiten), oder jeden Springer auf max. 2 Felder ziehen, d.h. im Zug 1 hat Weiß 20 mögliche Züge (Schwarz übrigens auch).

Nee, kann nicht gehen, denn die Möglichkeiten in Zug 2 hängen schon davon ab, was in Zug 1 gezogen wurde (Bsp.: e4 e5 => der e-Bauer kann erstmal nicht mehr ziehen).
D.h. das Problem ist m.E. mathematisch nicht entscheidbar.....oder doch?

Bei meinen Überlegungen bin ich von durchschnittlich 30 Möglichkeiten pro Zug ausgegangen; ich meine das mal gelesen zu haben; vielleicht weiß es aber jemand besser

Ich glaube es würde funktionieren, falls der Algorithmus die Stellung bzw. Position/Koordinaten ,der einzelnen Figuren, nach jedem Zug zugesendet bekommen würde.
LG
Boris

Die Zuggeneratoren von Schachprogrammen machen ja genau das, aber ich bezweifle, dass diese Algorithmen in eine praktikable Formel zu pressen wären. Es spielen hier sehr viele Parameter eine Rolle wie Anzahl, Art und Positionen der Figuren, Schachs, Pattsituationen, Bauern-Umwandlungen, Rochade, En-Passant-Möglichkeiten etc.

Vergangenheitswerte spielen auch eine Rolle, z.B ob eine Rochade oder En-Passant-Schlagen erlaubt ist, daher kann eine Stellung ohne Informationen aus dem bisherigen Geschehen manchmal nicht ausreichen, um die Anzahl der Züge zu errechnen.

Gibt es mit Sicherheit, musst du mal einen Mathematiker fragen :-)

Einen rein mathematischer Ansatz mit hinreichender Genauigkeit sehe ich auch nicht. Für jede mögliche Stellung müsste ja wieder die Anzahl der zulässigen Züge ermittelt werden.
Vielleicht findet man aber im Internet entsprechende Daten aus Schach-Engines. Wenn man denen mal die Eröffnungsdatenbank und die "Intelligenz" wegnimmt (oder eine alte Engine nimmt), dann bleibt ja für die Engine nichts anderes als in jeder Stellung zunächst jeden erlaubten Zug zu ermitteln und durchzurechnen. Die meisten Möglichkeiten werden dann sicherlich verworfen. Aber man hätte an dieser Stelle die Möglichkeit die Anzahl erlaubter Züge zu zählen. Wenn man dann diese Engine große Partiedatenbanken durcharbeiten ließe, dann würde man zumindest Mittelwerte und Schwankungsbreiten für die Anzahl der Möglichkeiten je Zug erhalten.
Vielleicht keine elegante Lösung, aber zumindest eine Idee für eine Annäherung.

Ja, es hängt sehr stark ab von der jeweiligen Stellung, und variiert deutlich.
Denken wir an den Fall, wo der König im Schach steht und exakt ein Ausweichfeld hat => genau 1 Zugmöglichkeit.

Oder gerade habe ich mal die 'Schachaufgabe des Tages - schwer' angeschaut, da hat Weiß z.B. 48 Zugmöglichkeiten (falls ich richtig gezählt habe). Interesssanterweise hätte ich bei diesem Bsp. geschätzt, dass es bestimmt viel mehr sind.
Da sollte man doch meinen, da kann es doch gar nicht so schwer sein, die beste Lösung zu finden: Ich gehe einfach im Geist die 48 Möglichkeiten durch, verwerfe die schlechten, und übrig bleibt die beste. Aber so einfach ist es eben nicht: Ich muss ja auch immer die Folgen meines Zuges im Auge behalten, sprich was könnte mein Gegner darauf ziehen (Züge vorausdenken). Und da ist rasch das Durchschnittshirn überlastet... ;-))

Die Maximalzahl von Zügen in einer regulären Stellung ist übrigens 122, es sei denn, in den letzten Jahren sind per Computer neuere Ergebnisse erzielt worden.

König 8
Dame 19
Türme 28
Läufer 23
Springer 16
Bauern 28
Für den schwarzen König gibt es dabei mehrere Stellplätze.
Quelle: Buch: "Schach+Mathematik" von J.Gik von 1986

...danke Gammapappa, weißt Du, wie die Zugzahl 28 bei den Bauern zustande kommt?

Ach ich hab's schon: Die 6 Bauern auf der 7er Linie können sich im nächsten Zug in 4 unterschiedliche Figuren verwandeln (gibt 24), und die anderen beiden können 1 oder 2 Felder vorrücken.

@gammapapa spannend, stand im Buch von Gik etwas zur Herleitung der „Maximalstellung“? mathematisch? algorithmisch?

und was ist, wenn man beispielsweise statt der bauern von d bis h damen hinstellt? die haben doch viel mehr zugmöglichkeiten

@toby84: es geht um eine gültige Stellung....obwohl Du hast Recht: Es könnten auch in einer regulären Stellung schon paar Bauern in eine Dame umgewandelt worden sein. Also müsste die von gammapappa genannte Zahl größer sein, oder?

außerdem frage ich mich gerade, wie diese stellung zustande gekommen sein kann. da schwarz keine figur außer dem könig auf dem brett hat, muss der letzte zug Ka6 gewesen sein. doch auf jedem benachbarten feld steht er mindestens im doppelschach. von keinem dieser mehrfachschachs sehe ich, wie weiß sie in seinem letzten zug beide gleichzeitig aufgestellt haben soll. also woher kommt der Ka6?

soweit ich das sehe ist Kh4 der einzige mögliche stellplatz in dieser konstellation

Ihr habt Recht. Das ist nicht die Stellung mit der größten Anzahl möglicher Züge. Beim Nachlesen habe ich gesehen, es ging um die meißten Züge bei einem kompletten Figurensatz von Weiß. Den schwarzen König habe ich zusätzlich aufgestellt, der war im Diagramm nicht dabei.
Ich schaue mal nach, ob es etwas anderes gibt.

@toby: Je weniger schwarze Figuren, um so mehr Zugmöglichkeiten für weiß. Es geht einzig und allein erstmal um das Maximum der Zugm.

@gammapappa: ok ich bin gespannt ob es da noch was gibt

@brauna das ist schon klar. trotzdem ist es unmöglich, diese stellung aufs brett zu bekommen, also ist sie nicht regulär, wie zuvor behauptet wurde

Die Formel für die Zugmöglichkeiten lautet 2 hoch63+1. Man sagt, daß sogroh die Anzahlen auf dem Schachbrett möglichen Züge sei.

@hetral: wo hast du das denn her? oder soll das ein scherz sein? wenn auf sissa ibn dahir anspielst, sind es 2^63-1 ;)

Der Legende nach bedang sich der Erfinder des Schachspiels als Lohn ein Weizenkorn für das erste Feld des Brettes aus und die jeweils doppelte Menge für das jeweils nächste Feld. Die Summe der Weizenkörner, die auf diese Weise zustande kommt, ist 18 Trillionen 4467444 Billionen 73709 Millionen und 551615 Stück. 2hoch 63+1.

es sind 2 hoch 63 -1. das kann man sich auch leicht verständlich machen, wenn man sich die zahl anschaut. es ist die summe aller binärzahlen von 2^0 bis 2^63. das entspricht der binären zahl 11111... mit 63 ziffern. addiert man zu dieser zahl 1 hinzu, ist es 10000... mit 63 nullen, also 2^64

korrektur: es müssen natürlich 64 ziffern und 64 nullen sein

ich habe jetzt einfach mal geschaut was wikipedia dazu sagt, und da stehen tatsächlich ziemlich präzise angaben drin:

Schach ist eines der komplexesten Brettspiele. Die Zahl der möglichen Stellungen[5] wird auf über 1043 geschätzt. Bereits nach zwei Zügen können 72.084 verschiedene Stellungen entstehen. Die Zahl der möglichen Spielverläufe ist noch einmal um ein Vielfaches größer: Schon für die ersten 40 Züge belaufen sich die Schätzungen auf etwa 10^115 bis 10^120 verschiedene Spielverläufe.[6] Dabei wird im geometrischen Mittel über den Partieverlauf von etwa 30 möglichen Halbzügen pro Stellung ausgegangen.

eine hochzahl vergessen zu ändern: Schach ist eines der komplexesten Brettspiele. Die Zahl der möglichen Stellungen[5] wird auf über 10^43 geschätzt.

Ich hab mal gelesen: die Zahl der möglichen Stellungen übersteigt die Anzahl der Atome im Universum.
Ich setze hinzu: es ist aber nicht gemeint die Zahl der wahrscheinlichen oder einigermaßen sinnvollen Stellungen - was mich früher immer ernüchtern wollte - heute aber nicht mehr; mit wieder zunehmender Spielerfahrung. Ja, ich glaube wieder an die Unendlichkeit u. Unerschöpflichkeit des Schachs. :-)

ja, diese zahlen sind größer als die anzahl der atome im universum. wenn ich mich recht entsinne, waren es grob 10^60 atome im universum, aber da bin ich mir auch nicht mehr so sicher. ich könnte ja wieder nachschauen, aber jedes mal nachgucken ist ja auch langweilig.

selbst wenn die zahl der sinnvollen stellungen deutlich kleiner als die der möglichen ist, ist sie vermutlich immer noch recht groß :)

ach jetzt muss man wieder differenzieren. die anzahl der möglichen stellungen wäre demnach kleiner als die zahl der atome im universum, die zahl der möglichen spielverläufe deutlich größer. jetzt müsste man doch wieder nachschauen, ob die zahl aus meinem gedächtnis korrekt ist.

heute ist wirklich mein tag der nachträglichen ergänzungen...

Deswegen glaub ich auch nicht das der Computer das Schachspliel kaputt macht. Im Gegenteil. Vielleicht ähnlich wie bei der Statik. Der Computer erlaubt immer Komplexere Statische Gebilde. Wenn mann das Entsprechend zu nutzen weiss können sehr schöne Gebilde Entstehen.

Das mit der Verdopplung der Weizenkörner für jedes der 64 Schachfelder hat aber nun rein gar nix mit der Anzahl der Zugmöglichkeiten pro Zug zu tun. Dennoch ein interessanter Fakt! :-)

@Hasenrat: Unendlich kann die Zahl der möglichen Stellungen nicht sein, weil wir ja eben auf die 64 Felder und max. 32 Figuren begrenzt sind.

...sie ist sicher endlich, aber nicht mehr für unser kleines Hirn begreifbar.
Schaut man sich auf Wikipedia mal die Shannon-Zahl an, so ist dort von 10 hoch 120 möglichen Stellungen die Rede.
Da ziehe ich ehrfürchtig meinen Hut vor so einem Spiel....ist es das überhaupt? Schach ist fast schon eher eine Philosophie!

Es gibt mehr Zugmöglichkeiten als Atome im Universum.

... wobei man wegen der vermuteten dunklen Materie nicht so genau weiß, wieviele Atome es gibt.; aber es bleibt natürlich eine unvorstellbare Zahl, die ein Durchrechnen des Spiels unmöglich erscheinen lässt.

Bei den Zugmöglichkeiten muß man unterscheiden:
1.) Züge in einer bestimmten Stellung und
2.) Züge, die in einer Schachpartie vorkommen können.
Zu 2.) habe ich nachgelesen, gibt es 43732 Züge.
Folgende Kriterien sind dabei zu beachten:
Welche Figur zieht?
Ist die Figur schwarz oder weiß?
Welches sind die Anfangs-und Endfelder?
Welche Figur wird evtl. geschlagen?
In welche Figur erfolgt eine evtl. Umwandlung?
Sonderzüge wie Rochade und e.p.

Bei Stellungsmöglichkeiten ist die Sache weit schwieriger. Wenn aus einem kompletten Figurensatz eine beliebige Anzahl Figuren auf beliebige Felder gestellt werden soll, kann man das noch ausrechnen. Andernfalls für eine reguläre Stellung sind so viel Nebenbedingungen zu beachten, dass das sicher nur mit entsprechenden Computerprogrammen geht.

Hmm, wenn es ca. 10 hoch 120 mögliche Stellungen gibt, dann erscheint es mir sehr kühn zu behaupten, dass es exakt 43732 Züge gibt, die in einer Schachpartie vorkommen können.
Wie berechnet sich diese Zahl?

Einen hochinteressanten Artikel zu obigem Themengebiet hat schimanski in einem Nachbarthread eingestellt, der Antworten auf einige meiner Fragen gibt.
Voila:
sfbux.de/wp-content/uploads/artikel/berechenbarkeit.pdf

Damit ist klar (siehe Artikel): Aus heutiger Sicht ist die Anzahl der möglichen Stellungen selbst mit den besten Computern der Welt nicht berechenbar!
Mathematisch gesehen also nicht entscheidbar!

Damit ist aber eine Frage immer noch nicht beantwortet: Was ist die max. Anzahl von Zugmöglichkeiten in einem Zug in einem regulären Spiel?
(-> Die Antwort von gammapappa - nämlich 122 ist ja wie oben beschrieben offenbar nicht ganz korrekt)

@brauna: gammapappa bezieht sich auf mögliche züge, unabhängig von der stellung. die anzahl lässt sich relativ einfach ausrechnen, sogar von hand

@toby84: bitte sags mir, wie sie sich ausrechnen lässt! Und welchen Wert sie hat!

Meistens, wenn bei mathematischen Beweisen "relativ einfach" dabei stand, erwiesen die sich als unglaublich schwer ;-)

Stellung mit der max. Anzahl von Zugmöglichkeiten von Weiß und Schwarz in einer regulären Partie mit 324 Zugmöglichkeiten
Quelle ist wieder das Buch "Schach und Mathematik"

In Stellungen ohne umgewandelte Figuren und ohne Bauernumwandlungen sind es max. 181 Züge.
In Stellungen ohne umgewandelte Figuren, aber mit möglichen Bauernumwandlungen sind es max.223 Züge.
Bei Interessse kann ich die Diagramme noch reinsetzen.

...danke gammapappa!
Das Max. lautet also 324 Zugmöglichkeiten pro Zug.

Bin gespannnt, ob toby84 den Wert bestätigt.

Allerdings ist auch klar: Es ist nur ein theoretisch möglicher Wert, denn eine solche Stellung lässt sich - selbst wenn 2 Gegner es wollen - niemals auf's Brett zaubern.

über die zugmöglichkeiten pro zug habe ich nichts zu sagen. ich habe von der anzahl aller möglichen schachzüge gesprochen. exemplarisch zeige ich, wie man das berechnen kann:

auf jedem feld in der mitte des spielbrettes hat der könig 8 mögliche züge. auf jedem feld am rand hat er 5 mögliche züge, auf jedem eckfeld hat er 2 mögliche züge. bei jedem dieser züge kann er folgende figuren schlagen:
dame, springer, läufer, turm
auf allen außer 16 dieser felder kann er bauern schlagen

nun summiert man alle diese werte auf und hat sämtliche möglichen züge des königs gefunden. so macht man das mit jeder figur und hat die gesamtzahl aller möglichen schachzüge. das ergebnis ist offensichtlich 43732, dieser information will ich einfach mal glauben schenken.

üblicherweise wird in der notation sogar die information weggelassen, welche figur geschlagen wird. wenn man also nur unterscheidet zwischen schlagen und ziehen, wird die berechnung noch einfacher.

das klingt wirklich komisch. es ist gar nicht so einfach, sich in diesen fragen so auszudrücken, dass andere verstehen, was gemeint ist.

deine formulierung "zugmöglichkeiten pro zug": die gesamtzahl aller zugwahlmöglichkeiten in jeder möglichen schachstellung, die es gibt

"anzahl aller möglichen schachzüge": gesamtzahl aller züge, die die schachfiguren ausführen können

Tja, toby, Schach ist eben nicht-trivial.

Und ja, meine Anfangsfrage ganz oben entwickelte sich in unterschiedlichste - aber sehr interessante - Folgefragestellungen.

Und wenn ich die 10 hoch 120 möglichen Stellungen betrachte, dann ziehe ich ehrfürchtig meinen Hut und weiß, dass Schach für immer das für mich interessanteste und verblüffendste Spiel sein wird!

Wie kommt denn diese Zahl 10 hoch 120 zustande. Die erscheint mir völlig unlogisch.
Gilt die nur für reguläre Stellungen?

@gammapappa: geh mal in Wikipedia rein, und suche die Shannon-Zahl...da findest du Antworten.

da geht es um spielverläufe, nicht um stellungen

wobei man laut regeln eigentlich jede stellung im kontext der bisherigen partie betrachten muss. es gibt dinge wie rochaderecht, en passant recht, 50 züge regel, dreimalige zugwiederholung. insbesondere die letzten beiden regeln sorgen dafür, dass eigentlich zur bewertung einer stellung immer die komplette bisherige partie bis zum letzten bauernzug notwendig ist, was die anzahl der möglichen stellungen gerade aberwitzig vervielfältigt. allerdings sind beides regeln, die man nur für menschen braucht, um zu verhindern, dass eine partie sinnlos ins unendliche gezogen wird. für schachprogramme gäbe es hierfür andere lösungen. berücksichtigt man diese beiden regeln also nicht, sind die möglichen stellungen weit unter 10^120

Wie gesagt, die Anzahl der möglichen regulären Stellungen "explodiert" förmlich mit jedem Zug: Nach dem 1.Zug von Weiß sind es noch übersichtliche 20 mögliche Stellungen, nach dem Zug von Schwarz schon 20 x 20, also 400 .

@toby84: Nimm einfach nur einen riesigen Bruchteil davon, also z.B. 10 hoch 60, aber auch das sind noch unvorstellbar viele Stellungen ;-)

ja schon, aber was da letztendlich so viel wird ist die anzahl der möglichen spielverläufe. die anzahl der möglichen stellungen ist doch erheblich eingeschränkter, würde ich schätzen. allerdings ist mir vorhin eingefallen, dass bauernumwandlungen nochmal erheblich mehr stellungen erlauben. aber das sind alles spezialfälle, die mit real gespielten partien nichts zu tun haben, sondern einfach zufallskombinationen aus zügen abbilden. ich behaupte, dass real gespielte partien nur einen winzigen bruchteil der möglichen partien darstellen. du kannst auch mit nur 50 zufällig gewählten buchstaben mit satzzeichen und leerzeichen etwa 10^77 verschiedene buchstabenkombinationen herstellen (ich habe mit 35 verschiedenen zeichen gerechnet), aber der mit abstand größte teil davon ist absolut unsinnig. ähnlich verhält es sich mit diesen schachspielverläufen

Nun ja, aber es gilt aufgrund der möglichen 10 hoch 120 Stellungen: Jede gespielte Partie hier auf chessmail über 40 Züge ist ein Unikat, manchmal sogar ein Kunstwerk, und das sogar weltweit!
Seid stolz drauf! ;-)

ja, auf chessmail vermutlich schon. aber bei allen gespielten partien auf der welt? das halte ich für ausgeschlossen. dafür haben - wie an anderer stelle erwähnt - zu viele partien einen sehr ähnlichen verlauf

...na gut, toby84, vielleicht hast Du Recht.

Dann erhöhe ich mal und postuliere:
Jede bisher - weltweit - gespielte Partie über 50 Züge ist ein Unikat, es sei denn, die Partie wurde durch Fake verdoppelt.

Das behaupte ich aufgrund der bisherigen Erfahrungen in diesem Thread, insbesondere wegen der unglaublichen Zahl von 10 hoch 120 möglichen Stellungen.
Warum behaupte ich das: Nun, einfach aufgrund der Wahrscheinlichkeitsrechnung muss es m.E. so sein.

über die wahrscheinlichkeit bestimmer spielverläufe wurde bisher aber noch nicht gesprochen. ausgehend von der anzahl möglicher partieverläufe auf die wahrscheinlichkeiten realer spielverläufe zu schließen, halte ich für sehr fragwürdig. mal eine andere anschauliche zahl:

wieviele möglichkeiten gibt es, 32 voneinander unterschiedliche figuren auf einem schachbrett aufzustellen? es sind 64!/32!, also grob 10^54. dabei habe ich nicht berücksichtigt, dass es eigentlich nicht 32, sondern nur 12 verschiedene figurentypen gibt, die meist paarweise, bei den bauern in achtfacher ausführung auftreten. damit reduziert sich die anzahl der varianten erheblich.

wenn wir also vernachlässigen, dass bauern sich in andere figuren umwandeln können und dass regeln wie die 50-züge-regel für eine stellung eine rolle spielen, gibt es nicht einmal annähernd so viele verschiedene stellungen wie es spielverläufe gibt (diese einschränkung ist nicht so weit hergeholt, weil sich die angegebene zahl von 10^120 auf partien mit 40 zügen beschränkt, also nicht allzu viel zeit für bauernumwandlungen). was lässt sich daraus schließen? dass zahlreiche dieser 10^120 spielverläufe zu identischen stellungen führen, also praktisch nur zugumstellungen sind. die ersten vier zugumstellungspartien haben wir bereits nach dem zweiten zug von schwarz (exemplarisch eine davon: Sf3, Sf6, Sg1, Sg8), und auch diese zahl der partien mit identischen daraus resultierenden stellungen wächst mit der anzahl der züge stark an.

tatsächlich würde es mich jetzt interessieren, wieviele verschiedene eröffnungen bis zum zehnten zug tatsächlich gespielt werden im vergleich zu den tatsächlich möglichen. zumindest für partien in eröffnungsdatenbanken könnte man das überprüfen, wenn auch nicht ansatzweise für alle partien, die jemals gespielt wurden. die anzahl aller möglichen partieverläufe bis zum zehnten zug dürfte auch noch ganz gut berechenbar sein.

zusatz: es sind 16 zugumstellungspartien nach dem zweiten zug von schwarz, nicht 4. die springer haben ja jeweils zwei mögliche erste zielfelder

...wenn du sagst, bis zum 10.Zug, dann bin ich bei dir....da gibt es sicher unzählige Duplikate von Spielen. Allein aufgrund der Tatsache, dass viele Spieler die ersten 10 Züge, selbst auf unterschiedliche Reaktionen des Gegners hin, schon im Kopf haben.

Aber ich postulierte ja für Spiele über 50 Züge. ;-)

ja das ist schon klar ^^ aber für 50 züge werden wir das kaum bestimmen können. für die ersten 10 züge könnte man eine recht gute annäherung finden, schätze ich. freiwillige vor ;)

Oder besser: Mathematiker vor mit soliden Wahrscheinlichkeitstheorie-Kenntnissen.

Ich hab mal in einer Datenbank mit über 3 Mill. Partien immer den häufigsten Zug eingegeben, da landet man beim 10. Zug bei einer sizilianischen Variante mit rund 2500 gespielten Partien.
Gibt man im ersten Zug von Schwarz allerdings e5 ein, landet man bei einer spanischen Variante mit ca. 10.000 gespielten Partien.
Das zeigt auch, dass Sizilianisch variantenreicher ist als z. B. Spanisch.