Neuronale Netze gegen genetische Algorithmen in Spielen wie Tic Tac Toe?

9

Derzeit mache ich ein Projekt, bei dem es darum geht, eine KI zu erstellen, um das Spiel Gomoku zu spielen (es ist wie Tic Tac Toe, wird aber auf einem 15 * 15-Brett gespielt und erfordert 5 in einer Reihe, um zu gewinnen). Ich habe bereits erfolgreich eine perfekte Tic Tac Toe-KI implementiert, indem ich Q-Learning verwendet und Spielzustände / Aktionen in einer Tabelle gespeichert habe, aber für ein 15 * 15-Brett werden die möglichen Spielzustände zu groß, um dieses Projekt umzusetzen.

Meine Frage ist, sollte ich für dieses Problem neuronale Netze oder genetische Algorithmen verwenden? Und genauer gesagt, wie soll ich das umsetzen?

Conway
quelle
2
Willkommen bei AI! Ausgezeichnete Frage imho.
DukeZhou

Antworten:

7

Für Gomoku scheint es ein bisschen übertrieben zu sein, neuronale Netze oder den genetischen Algorithmus zu verwenden, da beide eine Weile dauern und meistens nicht so laufen, wie Sie es möchten. Der Gomoku-Spielbaum ist ziemlich groß, aber Sie können eine anständige KI durch Minimax, Beschneiden des Spielbaums und eine gute heuristische Funktion (einschließlich des Zählens von halben und vollen 2s, 3s, 4s usw.) im Gegensatz zum Mapping erhalten aus dem vollen Raum.

Wenn Sie mit Alpha-Beta-Bereinigung und Minimax nicht vertraut sind, lesen Sie https://www.cs.cornell.edu/courses/cs312/2002sp/lectures/rec21.htm

Wenn Sie wirklich neuronale Netze oder genetische Algorithmen verwenden möchten, können Sie für die Lernerfahrung. In Bezug auf neuronale Netze gibt es folgende Möglichkeiten:

  • Definieren Sie eine heuristische Funktion, die eine Eingabe für den Kartenstatus empfängt (Folge von 0,1,2 für leer, schwarz, weiß) und einen Wert für die Güte des Kartenstatus ausgibt. Das neuronale Netzwerk ist unsere heuristische Funktion.
  • Angenommen, die Züge in diesem Spiel sind optimal, trainieren Sie den Unterschied zwischen dem derzeit besten Zug (anhand Ihrer aktuellen Parameter) und dem Zug, von dem Ihre Daten sagen, dass er der beste ist. So definieren wir unsere Fehlerfunktion! Auf diese Weise minimieren Sie diesen Unterschied, sodass die Bewegung, die Ihr neuronales Netzwerk als die stärkste bezeichnet, idealerweise die stärkste Ihrer Spieldaten ist (die Optimierung dieser Fehlerfunktion kann über Backpropagation oder genetischen Algorithmus erfolgen).
  • Idealerweise können Sie zu diesem Zeitpunkt jetzt Ihre ("starke") auf einem neuronalen Netzwerk basierende Bewertungsfunktion für Ihre Spielbaum-Bewegungsbewertungen anstelle von fest codierten Heuristiken verwenden.

Dies ist natürlich nur eine Möglichkeit, und Sie müssten zuerst die Spieldaten finden.

Eine Randnotiz zur Anwendung eines genetischen Algorithmus kann auf verschiedene Arten erfolgen, z. B. zur Parameteroptimierung in einem neuronalen Netzwerk wie oben erwähnt oder zur Suche nach Spielbäumen. Stellen Sie also sicher, dass Sie klar sind, wie Sie die Problemeinstellung damit definieren! Gleiches gilt für alternative Möglichkeiten zum Anwenden eines neuronalen Netzwerks.

Schließlich ist es hilfreich zu wissen, dass Gomuku gelöst ist. Unter /programming/6952607/ai-strategy-for-gomoku-a-variation-of-tic-tac-toe finden Sie die Gedanken und Ideen anderer.

sma
quelle
2
Netter Punkt über Gomoku als gelöstes Spiel. Dies macht es einfach, die Stärke der KI zu überprüfen (dh löst sie das Spiel und drückt ein perfektes Spiel aus, oder spielt sie nur optimaler als ein Gegner, wie im Fall von AlphaGo.)
DukeZhou