Einfache Tic-Tac-Toe AI

Question

Ich weiß, das wurde viel gefragt und ich habe anderen Code gesucht, aber das meiste von dem, was ich gesehen habe, scheint nicht makellos (verliert nie) und einfach, elegant und effizient. Und ich bin nicht in der Lage zu entscheiden, welche Art von Lösung zu dieser Beschreibung passen würde.

Die Lösungen, die ich gesehen habe, sind:

(1) Unter Verwendung von Minimax mit Alpha-Beta-Suche. Das scheint mir kompliziert und möglicherweise unnötig für solch ein einfaches Spiel? Ist es wahrscheinlich zu kompliziert? Wenn nicht, müsste ich viel hart codieren oder missverstehe ich den Algorithmus?

(2) Schreiben Sie Ihren Code mit der Pseudocode-Strategie von Wikipedia ... Ich bin mir nicht sicher, wie dies zu implementieren ist. Zum Beispiel sagt es nur "check for forks". Würden die meisten dieser Überprüfungen mit einem Array von Gewinnlinien durchgeführt werden und prüfen, ob sie ausgefüllt werden oder so ähnlich? Wenn nicht, kann mir jemand Hinweise geben, welche Datenstrukturen oder grundsätzliche Hinweise zur Umsetzung der im Pseudocode gestellten Checks hier zu finden sind: http://en.wikipedia.org/wiki/Tic-tac-toe#Strategy. Ich habe auch Algorithmen gesehen, die einem X-Quadrat und einem O-Quadrat einen numerischen Wert geben und dann die Summe verwenden, um den Gewinner zu bestimmen, aber ich sehe nicht, warum das besonders nützlich ist.

Irgendwelche anderen vernünftigen Lösungen?

Answer 1

Um ehrlich zu sein, können die einfachsten Aufgaben im Umgang mit KI und Heuristiken sehr schnell kompliziert werden. Der Minimax-Ansatz wird Ihnen die besten Ergebnisse liefern und sollte angesichts der Tatsache, dass Sie KI implementieren, nicht allzu schwierig sein. Es ist ein etablierter Standard mit 2 Spieler Turn Logik.

Schauen Sie sich diese Website an ... sie gibt einen guten Einblick in die Tic-Tac-Toe KI und die Minimax-Implementierung.

http://www.ntu.edu.sg/home/ehchua/programming/java/JavaGame_TicTacToe_AI.html

Edit:

merken, dass jemand schrieb „Brute Force“ ... das wird sein ein ineffizienter Weg der Umsetzung der beteiligten Heuristik in Minimax enden. Iteration durch jede mögliche Bewegung basierend auf dem letzten Zug der anderen Spieler ist nur eine andere Art, eine Heuristik zu implementieren .. außer dass es meiner Meinung nach mehr Arbeit zu sein scheint. Die Minimax-Implementierung wird einfach und effektiv sein.

Edit2:

"Einfachere Implementierung" ist etwas relativ. Minimax ist der Standard, und wie ich im Kommentar gesagt habe, können Sie die Heuristik an die Fälle anpassen, die Sie suchen ...

Ich wünschte, ich könnte Ihnen den einfachsten Weg sagen, aber es gibt so viele Variablen abhängig von der Implantation deines Spiels im Code.

Nehmen Sie die Vorschläge, sehen Sie sich die Implementierung des Spiels an und sehen Sie dann, was Ihnen am besten passt!

Was für eine Person einfach ist, kann für eine andere Person kompliziert sein. Ich versuche nur, dir Optionen zu geben und minimax ist ziemlich solide. Vielleicht versuchen Sie es an Ihre Bedürfnisse anzupassen.

Edit3:

Lassen Sie mich wissen, wenn Sie mehr Richtung benötigen. Ich bin glücklich zu helfen.

Answer 2

Verwenden Sie das Format Ihrer Wahl, um this image in eine Reihe von Zügen zu "kodieren". Die KI wird immer gewinnen oder binden.

Zum Beispiel könnten Sie es kodieren wie folgt:

var turns = { 
    "mefirst":{ 
    "move":0, 
    "next":[ 
     null, 
     { 
     "move":4, 
     "next":[ 
      null, 
      null, 
      {"move":8}, // win 
      {"move":8}, // win 
      null, 
      {"move":8}, // win 
      {"move":8}, // win 
      {"move":8}, // win 
      { 
      "move":6, 
      "next":[ 
       null, 
       null, 
     /* AND SO ON... */ 
    ] 
    } 
}; 

Dann können Sie beginnen mit:

if(ai_goes_first) { 
    game = turns.mefirst; 
    makeMove(game.move); 
} 
else game = turns.themfirst; 
playerTurn(); 

Wo playerTurn ist so etwas wie:

function playerTurn() { 
    when player clicks a valid squeare { 
     game = game.next[chosenSquare]; 
     makeMove(game.move); 
     if(game.next) playerTurn(); 
    } 
}