Einfache tic-tac-toe AI

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

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

(1) Mit minimax mit alpha-beta-pruning. Dies scheint kompliziert zu mir und eventuell unnötig, für so ein einfaches Spiel? Ist es wohl zu kompliziert? Wenn nicht, würde ich tun müssen, eine Menge von hard-Codierung oder bin ich Missverständnis der Algorithmus?

(2) Schreiben Sie Ihren code mit dem pseudocode-Strategie von Wikipedia... ich bin mir nicht genau sicher, wie Sie diese umsetzen. Zum Beispiel, es sagt nur "check für Gabeln". Würden die meisten diese Kontrollen durchgeführt werden, indem ein array von winningLines und überprüfen, ob Sie möchte ausgefüllt werden oder sowas? Wenn nicht, kann mir jemand Hinweise auf das, was Datenstrukturen oder irgendwelche grundlegenden Tipps, wie die Umsetzung der Kontrollen stellte in der pseudocode hier: http://en.wikipedia.org/wiki/Tic-tac-toe#Strategy . Ich habe auch gesehen, algorithmen, geben Sie einen numerischen Wert ein " X " Quadrat und einem 'O' square und verwenden Sie dann die Summe um den Gewinner zu entscheiden, aber ich sehe nicht ein, warum dies besonders nützlich.

Andere angemessenen Lösungen?

Für so ein kleines Spiel Baum, nur brute-force-it. Es würde überhaupt keine Zeit zu simulieren, die jedes mögliche Spiel.
scheint nicht makellos (gewinnt immer) = normal scheint. ich Gewinne immer bei tic tac toe. oder im schlimmsten Fall Unentschieden. jeder intelligenten person, das gleiche Ergebnis. das ist, warum spielt man nicht, tic tac toe nach dem Alter von 10 Jahren. es ist kein Spaß, wenn niemand gewinnt.
Auch ja, "immer zu gewinnen" ist nicht ein Gültiger Anforderung (immer). Stell dir vor, dein Algorithmus spielt gegen sich selbst.
Ich meinte nie verliert
Dann sollten Sie vielleicht Bearbeiten Sie Ihre Frage.

InformationsquelleAutor user1136342 | 2013-04-01

9

Um ehrlich zu sein, beim Umgang mit AI und Heuristiken, die einfachen Aufgaben kann kompliziert werden, sehr schnell. Der minimax-Ansatz wird Ihnen die besten Ergebnisse, und es sollte nicht allzu schwierig sein angesichts der Tatsache, dass Sie die AI. Es ist ein etablierter standard mit 2-Spieler-rundenbasierten-gaming-Logik.

Check-out dieser website... es gibt einige gute Einblicke in tic-tac-toe AI und die minimax-Umsetzung.

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

Edit:

Bemerken, dass jemand schrieb "Brute-Force"... das wird am Ende wird eine ineffiziente Art und Weise der Implementierung der Heuristiken beteiligt minimax. Iteration durch jeden möglichen Zug auf der Basis der anderen Spieler der Letzte Zug ist nur ein weiterer Weg für die Implementierung einer Heuristik.. außer es zu sein scheint, meiner Meinung nach, mehr Arbeit. Minimax Umsetzung einfach und effektiv.

Edit2:

"Einfachere Umsetzung" ist etwas relativ. Minimax ist der standard und wie ich schon in dem Kommentar, auf den Sie manipulieren können, die Heuristik entsprechend den Fällen, die Sie suchen...

Ich wünschte, ich könnte Ihnen sagen, die einfachste Weg, aber es gibt so viele Variablen, abhängig von der implantation des Spiels im code.

Nehmen Sie die Anregungen, schauen Sie Spiel-Umsetzung, und dann sehen, was Ihnen am besten passt!

Was ist einfacher, eine person möglicherweise kompliziert sein, um zu einem anderen. Ich versuche nur, um Ihnen Möglichkeiten und minimax ist ziemlich solide. Vielleicht versuchen Sie, es an Ihre Bedürfnisse anzupassen.

Edit3:

Lassen Sie mich wissen, wenn Sie brauchen mehr Richtung. Ich bin glücklich zu helfen.
- Klar, werden Sie sagen, dass minimax tatsächlich endet als einfacher als die überprüfung aller Fälle aus dem wikipedia-Eintrag, oder werden Sie sagen, dass es nicht viel mehr kompliziert und ermöglicht gleichzeitig mehr Effizienz und eleganten code?
- Ich sage, wenn Sie möchten, dynamisches Spiel, verwenden Sie den Effekt "minimax". Im Falle von tic-tac-toe mit den Fällen aus dem wiki könnte man codieren Sie diese Optionen, und befolgen Sie Sie in einem "brute-force" wenn du willst. Es würde funktionieren und garantieren gewinnen in bestimmten Fällen. Ich wurde sagen, wenn Sie wollen, eine Allgemeine Heuristik, Fälle zu behandeln, Sie könnte Umsetzung der minimax mit Ihren spezifischen Heuristik. Man könnte schließen diejenigen ein, die "definitive Sieg" Fällen, in die Heuristik zu versichern, dass Sie bedeckt sind und dann fallen zurück auf mehr Allgemeine Selektionen, wenn nötig. Ich denke, ein hybrid-Heuristik einschließlich der beiden dienen Ihnen am besten.
- Was meinst du mit "Garantie-Gewinn in bestimmten Fällen". Wäre es nicht garantieren, gewinnen in allen Fällen?
- Ja. Sorry, wenn ich mich nicht völlig klar. Semantik...
InformationsquelleAutor AnxGotta

Verwenden Sie das format Ihrer Wahl auf "encode" dieses Bild in einer Reihe von Zügen. Die KI wird immer gewinnen oder zu binden.

Beispielsweise könnten Sie codieren 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();
    }
}

InformationsquelleAutor Niet the Dark Absol

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.