Lösungsalgorithmus für Punkte und Felder

Dieses Spiel ist Nullsummenspiel , also ich ' Ich schlage vor, dafür den Min-Max-Algorithmus zu verwenden. Dieser Algorithmus wurde von deep-blue verwendet, um Kasparov im Schach zu gewinnen.

Erstellen Sie Ihre heuristische Funktion, die jeden Status des Spiels auswertet und als Bewertungsfunktion des Min-Max-Algorithmus verwendet.

Sie können auch die Min-Max-Werte verbessern, indem Sie alpha-beta prunning verwenden.

Die Idee von min-max besteht darin, alle möglichen Bewegungen

ps.

  

Das Gewinnen hat oberste Priorität: Effizienz des Algorithmus ist das nicht   wichtig.

Sie sind eng miteinander verbunden, denn je effizienter Ihr Algorithmus ist, desto besser können Sie die möglichen Lösungen prüfen und die Chancen, die Sie gewinnen werden, erhöhen. Beachten Sie, dass Sie mit unbegrenzter Zeit den gesamten Spielbaum erkunden und eine Gewinnstrategie für jeden Spielstatus entwickeln können. Allerdings ist es wahrscheinlich unrealistisch, den gesamten Spielbaum zu erforschen.

Ich denke, dass Minimax nicht die beste Wahl für Punkte-und-Boxen-Algorithmen ist. Für die vollständige Geschichte über dieses Spiel müssen Sie wirklich das Buch lesen Das Punkte- und Schachtelspiel: Sophisticated Child's Spielen von Elwyn R. Berlekamp , aber ich gebe dir hier eine kurze Zusammenfassung.

Berlekamp macht eine Reihe von starken Beobachtungen. Die erste ist die Doppelkreuzstrategie , von der ich annehme, dass Sie davon wissen (sie wird in der Wikipedia beschrieben Seite zum Spiel ).

Die zweite ist die Paritätsregel für lange Ketten . Dies ergibt sich aus drei Fakten über die Mehrheit der gut gespielten Spiele:

1. Die langen Ketten werden am Ende des Spiels gespielt.
2. Es wird ein Doppelkreuz in jeder Kette außer der letzten geben.
3. Der Spieler, der zuerst in einer langen Kette spielen muss, verliert das Spiel.

plus die Einschränkung, dass die Anzahl der Punkte, mit denen du beginnst, plus die Anzahl der Doppelkreuzungen gleich der Anzahl der Runden im Spiel ist. Wenn es also sechzehn Punkte gibt, und es gibt ein Doppelkreuz, gibt es siebzehn Züge. (Und in den meisten Spielen bedeutet dies, dass der erste Spieler gewinnt.)

Dies vereinfacht die Analyse von Mid-Game-Positionen enorm. Betrachten Sie zum Beispiel diese Position mit 16 Punkten und 11 gespielten Zügen (Problem 3.3 aus Berlekamps Buch). Was ist der beste Zug hier?

Nun, wenn es zwei lange Ketten gibt, wird es ein Doppelkreuz geben, das Spiel endet nach weiteren sechs Zügen (16 + 1 = 11 + 6), und der Spieler, der sich bewegt, verliert. Wenn es nur eine lange Kette gibt, gibt es kein Doppelkreuz und das Spiel endet nach weiteren fünf Zügen (16 + 0 = 11 + 5) und der Spieler, der sich bewegt, gewinnt. Wie kann der Spieler also sicherstellen, dass es nur eine lange Kette gibt? Der einzige Gewinnzug opfert zwei Felder:

Minimax hätte diesen Schritt gefunden, aber mit viel mehr Arbeit.

Die dritte und mächtigste Beobachtung ist, dass Punkte und Kästchen ein unparteiisches Spiel sind: Die verfügbaren Züge sind die gleichen, unabhängig davon, wessen Zug es ist, und an typischen Positionen, die im Laufe des Spiels entstehen (also solche, die lange Ketten von Kästchen enthalten), ist es auch ein normales Spiel : Der letzte Spieler, der sich bewegt, gewinnt. Die Kombination dieser Eigenschaften bedeutet, dass Positionen mithilfe der Sprague-Grundy-Theorie statisch analysiert werden können. p>

Hier ist ein Beispiel dafür, wie leistungsfähig dieser Ansatz ist, indem er Abbildung 25 aus Berlekamps Buch verwendet.

Es gibt 33 mögliche Züge in dieser Position, und ein gut gespieltes Spiel dauert ungefähr 20 weitere Züge, also wäre ich überrascht, wenn es für minimax machbar wäre, seine Analyse in einer vernünftigen Zeit abzuschließen. Aber die Position hat eine lange Kette (die Kette von sechs Quadraten in der oberen Hälfte), so dass sie statisch analysiert werden kann. Die Position teilt sich in drei Teile, deren Werte nimbers sind:

Diese Nimber können durch dynamische Programmierung in Zeit O (2 ⁿ ) für eine Position berechnet werden, wobei n Bewegungen übrig bleiben, und Sie werden wahrscheinlich wollen die Ergebnisse für viele gemeinsame kleine Positionen sowieso zwischenspeichern.

Nimbers addieren mit exklusiven oder: * 1 + * 4 + * 2 = * 7. Die einzige gewinnende Bewegung (eine Bewegung, die die Nim-Summe auf * 0 reduziert) besteht darin, * 4 zu * 3 zu ändern (so dass die Positionssumme * 1 + * 3 + * 2 = * 0 ist). Jeder der drei gepunkteten roten Züge gewinnt:

Bearbeitet um hinzuzufügen: Ich bin mir bewusst, dass diese Zusammenfassung nicht wirklich einen Algorithmus als solchen darstellt und viele Fragen unbeantwortet lassen. Für einige der Antworten können Sie Berlekamps Buch lesen. Aber es gibt eine kleine Lücke, wenn es um die Eröffnung geht: Chain-Counting und Sprague-Grundy-Theorie sind wirklich nur im Mittel- und Endspiel praktisch. Für die Eröffnung müssen Sie etwas Neues ausprobieren: Wenn ich es wäre, wäre ich versucht, Monte-Carlo-Baumsuche