einfachste MiniMax-Algorithmus für TicTacToe AI in Java

Question

Ich habe versucht, den MiniMax-Algorithmus zu verstehen, und habe es gelesen. Mein erster Ansatz bestand darin, einen einfachen MiniMax-Algorithmus zu implementieren und dann Alpha-Beta-Beschneidung hinzuzufügen. Doch dies ist mein aktueller Code:

public int miniMax(char[] node, int playerNum) 
{ 
    int victor = checkWin(node); // returns 0 if game is ongoing, 1 for p1, 2 for p2, 3 for tie. 
    if(victor != 0) //game over . 
     return score(victor); 

    if(playerNum == 2) //AI 
    { 
     int bestVal = Integer.MIN_VALUE; 
     int bestSpot = 0; 
     for(int i = 0; i < node.length; i++) 
     { 
      if(node[i] != '-') 
       continue; 
      node[i] = getSymbol(playerNum); 
      int value = miniMax(node, 1); 
      if(value > bestVal) 
      { 
       bestVal = value; 
       bestSpot = i; 
      } 

      node[i] = '-'; 
     } 
     return bestSpot; 
    } 
    else 
    { 
     int bestVal = Integer.MAX_VALUE; 
     int bestSpot = 0; 
     for(int i = 0; i < node.length; i++) 
     { 
      if(node[i] != '-') 
       continue; 
      node[i] = getSymbol(playerNum); 
      int value = miniMax(node, 2); 
      if(value < bestVal) 
      { 
       bestVal = value; 
       bestSpot = i; 
      } 
      node[i] = '-'; 
     } 
     return bestSpot; 
    } 
} 

Und meine Score-Funktion

private int Score(int gameState) 
{ 
    if(gameState ==2) //O wins. 
     return 10; 
    else if(gameState==1) //X wins 
     return -10; 
    return 0; 
} 

Nun, ich habe eine funktionierende KI, die meine Bewegung versucht, zu blockieren und gewinnen, aber manchmal ist es macht nicht-intelligente Entscheidungen Zum Beispiel ist dies die Ausgabe, die ich bekomme, wenn meine Eingabe von der Konsole 6,7,8 in dieser Reihenfolge gelesen wird. Es versucht nicht, meinen Sieg zu blockieren. Aber in anderen Fällen tut es das.

---

| O | O | |

---

| | | |

---

| X | X | X |

---

In meinem zweiten Versuch versuchte ich 4,3 und es blockierte meine gewinnende Bewegung.

---

| | O | |

---

| X | X | O |

---

| | | |

---

Ich fragte mich, jemand könnte darauf hinweisen, was ist falsch mit meiner Implementierung?

Answer 1

Das Verhalten des Codes für die gezeigten Beispiele ist korrekt!

Warum wird die Bedrohung in der folgenden Position nicht blockiert? Warum spielt das Programm 1 statt 6?

O . .         O 1 2 
. . .  numbering available moves:  3 4 5 
X X .         X X 6 

Es ist, weil, wenn das Spiel auf perfektes Spiel verloren geht das Programm nur die erste verfügbare Bewegung spielt.

Der Algorithmus kümmert sich nur um Gewinn oder Verlust und nicht um die Anzahl der Züge.

Sehen Sie, was passiert, wenn die Bedrohung blockiert ist:

O . .  O . . 
. . .  . X .  and X wins on his next move 
X X O  X X O