Beim Reversi (Für diejenigen, die das Spiel nicht kennen: http://www.playsite.com/games/board/reversi) sind pro Partie maximal 60 Züge möglich, was bedeutet, daß es endlich viele verschiedene Partieen geben muß. Zunächst brachte mich das auf die verrückte Idee, einfach alle Partieen zu berechnen und abzuspeichern um einen schnellen und unbesiegbaren Computergegner zu entwickeln. Diese Idee habe ich aber schnell fallen lassen, weil die Zahl ganz sicher astronomisch hoch ist. Es bleibt aber die Frage, ob und wie man berechnen kann, wie viele Möglichkeiten es genau sind.
Um es zumindest abzuschätzen habe ich das geplante Programm doch geschrieben und begonnen gnadenlos alle Kombinationen der Reihe nach durchzuprobieren. Nach 10 Mrd. Partieen und einer Spieltiefe zwischen 15 und 16 Zügen habe ich meinen Computer erlöst und auf 60 Züge extrapoliert, wobei ich auf einen Wert von 1050 kam. Die Unsicherheit ist allerdings sehr hoch - es könnten ebensogut 1040 oder 1060 sein.
Meiner Meinung nach ist diese Frage extrem schwer zu beantworten, selbst wenn man nur eine ganz gute Abschätzung sucht, da es wohl schwierig wird, einen systematischen (mathematischen, also ohne Einsatz von brutaler Rechenpower) Ansatz zu finden, der Dir bei einer gegebenen Spiel-Konfiguration die weiteren Zugmöglichkeiten in halbwegs geschlossener Darstellung liefert. Außerdem müßte man noch bedenken, daß zwei Äste des Konfigurationsbaums u. U zu einer gleichen Konfiguration führen; Drehsymmetrien bestehen auch noch, usw…
Interessiert’s Dich jetzt nur noch rein akademisch oder geht’s Dir um das Programmieren eines Computergegners, dann würde ich einen anderen Ansatz benutzen, alles komplett durchzurechnen ist eben halt zu aufwendig (hast Du ja selbst geschrieben), das macht die Sache aber auch erst interessant, sonst wär’s ja langweilig…
Also wenn man davon ausgeht, daß man beliebig die „Reihen“ vollmacht, also zuerst direkt an die 4 ersten Steine anlegt, dann an den 16ner Block u.s.w., dann ergebn sich 12!+20!+28!= 3,04888E+29 Möglichkeiten, Symmetrien werde dabei als verschiedene Spielpartien betrachtet.
Gruß
Tyll
Hmmm, addieren darf man doch wohl nur, wenn es für den weiteren Verlauf des Spieles egal wäre, was in den ersten Zügen geschehen ist. Da dies aber nicht der Fall ist, müßte man die Fakultäten wohl eher multiplizieren und erhält 12!*20!*28!. Außerdem kann man mit dem füllen des 36er-Blocks bereits beginnen, wenn der 16er noch nicht ganz voll ist, woraus sich weitere Möglichkeiten ergeben.
Die Symmetrieen kann man berücksichtigen, indem man die Zahl aller möglichen Partieen durch 4 (2 Spiegelachsen + 2 Drehspiegelachsen) dividiert.
Also wenn man davon ausgeht, daß man beliebig die „Reihen“
vollmacht, also zuerst direkt an die 4 ersten Steine anlegt,
dann an den 16ner Block u.s.w., dann ergebn sich 12!+20!+28!=
3,04888E+29 Möglichkeiten, Symmetrien werde dabei als
verschiedene Spielpartien betrachtet.
Ja, das stimmt. Aber unter anderen Annahmen kommt man mit Kombinatorik nicht weit, fürchte ich.
Am Rande: Im Grunde sind doch zwei Partien verscheiden, wenn nach 60 Zügen das „S/W-Muster“ der einen sich nicht durch Drehung in ein anderes überführen läßt, oder?
dann ist das größte Problem die Änderung des Musters während des Spiels. Man müßte dann jene Spielzüge „streichen“, die zwar verschieden sind, aber am Ende dasselbe Muster erzeugen.
Ich muß allerdings nicht zugeben, daß ich nie REVERSI gespielt habe, also kann ich da gut irren.
Hmm, ich warte mal auch deine Antwort und überlegen derweil weiter…
Tyll
Man müßte dann jene Spielzüge „streichen“, die
zwar verschieden sind, aber am Ende dasselbe Muster erzeugen.
Im Prinzip schon. Bei einem konkreten Spielstand ist es unerheblich, wie man dazu gekommen ist. Führen also zwei Spielzüge zu einem gemeinsamen Zwischenergebnis, bräuchte man die Berechnung aller weiteren möglichen Spielzüge nur noch einmal zu machen. Dabei ist allerdings zu berücksichtigen, daß es sich bei unterschiedlichen Eröffnungen, aber gleicher Fortsetzung immer noch um unterschiedliche Partien handelt.
Allerdings ist die Zahl der möglichen Muster ein weiteres Problem, welches in diesem Zusammenhang von Interesse ist. Beispielsweise bräuchte man sich bei der Entwicklung eines ultimativen Computergegners nicht unbedingt alle möglichen Spielverläufe zu merken, sondern könnte alternativ auch alle möglichen Muster speichern. Ganz davon abgesehen, daß beides unrealistisch ist, besteht die Frage, welche Methode den geringsten Speicherplatz erfordert.
Hmmm, vom Programmieren hab ich nicht so viel Ahnung. Die maximale anzahl der Spielstände nach 60 Zügen ist natürlich
SUMME(i=0 bis i=60)(60 über i) = 260, also irgendetwas um den Dreh von 1019, wenn man i weiße Steine auf dem Brett verteilt und mit den schwarzen auffüllt. Dann muß man nch die Symmetrien abziehen, also durch vier teilen, aber das ändert dann auch nicht mehr viel.
Ich gehe mal von der Regel aus,daß der gewonnen hat, der am Ende am meisten Stein auf dem Brett hat. Dann reicht sogar eine Betrachtung von SUMME(i=32 bis i=60)(60 über i),
mit i=32 ist Patt-Situation.
Um nun noch deinen perfekten Computer zu erschaffen mußt du also alle Züge kennen, die ein solches Ergebnis erzeugen können, ausgehend von einem beliebigen Spielzug.
Hmmm, das wird aber echt viel.
Tyll
maximale anzahl der Spielstände nach 60 Zügen ist natürlich
SUMME(i=0 bis i=60)(60 über i) = 260
Es sind viel weniger, da ja lange nicht alle Zuege erlaubt sind. Die ersten vier Zuege fallen schonmal weg, da sie vorgeben sind - also eine Moeglichkeit. Beim ersten Zug hat man dann vier Moeglichkeiten, im Laufe des Spiels werden es mehr und am Ende wieder weniger. Wenn der Gegner gut spielt hat man sogar oft das ganze Spiel ueber nur ein paar Moeglichkeiten.
Ich vermute, wenn man versucht eine Spielsituation mit moeglichst vielen Moeglichkeiten zu finden, dann kann man annehmen, dass die Zahl der Moeglichkeiten von vier (?) am Anfang linear zunimmt und gegen ende wieder auf eins (letzter Zug) abfaellt. Bildet man einen Baum mit dieser Reiher hat man eine konservative schaetzung, wieviele Spiele es hoechstens gibt - beweisen kann ich das natuerlich nicht, ist nur eine Idee.