Was ist falsch mit meinem Minimax-Algorithmus für Tictactoe

Question

Ich baue ein Tic Tac Toe-Spiel für eine unterhaltsame Lernerfahrung. Ich habe einen Minimax-Algorithmus konstruiert, um die optimale Bewegung für den Computer zurück, aber irgendwie falsch, ich werde und wierd Ausgabe wie diese

TIC TAC TOE V1.0 
--- 
--- 
--- 
Enter row, column of your move 
1,1 
--- 
-X- 
--- 
... 
0, 0: -1038 
0, 1: -1470 
0, 2: -1038 
1, 0: -1470 
1, 2: -1470 
2, 0: -1038 
2, 1: -1470 
2, 2: -1038 
O-- 
-X- 
--- 
Enter row, column of your move 
1,2 
O-- 
-XX 
--- 
... 
0, 1: -15 
0, 2: -9 
1, 0: -10 
2, 0: -1 
2, 1: -29 
2, 2: -41 
O-- 
-XX 
O-- 
Enter row, column of your move 
1,0 
O-- 
XXX 
O-- 
WINNER: PLAYER 

Sie zu sehen bekommen, dass der Computer die linke untere Ecke wählte anstatt das Abschneiden Spieler. Mein Code versucht, den Flop zwischen den Runden rekursiv durch alle möglichen Spielstände zu drehen, den Punktestand für jeden Sieg aufsummieren zu lassen oder den Verlust, zu dem der Spielzug führen könnte, und gibt dann den Zug mit der maximalen Punktzahl zurück. Der Ausdruck ist der Punktestand jeder Runde bevor er gemacht wird (Sie können sehen, dass er den höchsten Wert wählt), also warum schneide ich den Spieler nicht ab? Wie kann ich das beheben? Hier ist mein Code.

int compMoveScoreRecursive(state_t **board, int dimension, int row, int col, state_t turn) { 
    board[row][col] = turn; 
    state_t winner = checkWinner(board, dimension); 
    if (winner == COMPUTER) { 
     return 1; 
    } else if (winner == PLAYER) { 
     return -1; 
    } else { 
     int score = 0; 
     state_t nextTurn = turn == COMPUTER ? PLAYER : COMPUTER; 
     for (int i = 0; i < dimension; i++) { 
      for (int j = 0; j < dimension; j++) { 
       if (board[i][j] == NIL) { 
        state_t **boardCopy = copyBoard(board, dimension); 
        score += compMoveScoreRecursive(boardCopy, dimension, i, j, nextTurn); 
        destroyBoard(boardCopy, dimension); 
       } 
      } 
     } 
     return score; 
    } 
} 

move_t optimalCompMove(state_t **board, int dimension) { 
    move_t optMove; 
    int optScore = INT_MIN; 
    for (int row = 0; row < dimension; row++) { 
     for (int col = 0; col < dimension; col++) { 
      if (board[row][col] == NIL) { 
       state_t **boardCopy = copyBoard(board, dimension); 
       int score = compMoveScoreRecursive(boardCopy, dimension, row, col, COMPUTER); 
       printf("%d, %d: %d\n", row, col, score); 
       if (score > optScore) { 
        optMove.row = row; 
        optMove.col = col; 
        optScore = score; 
       } 
       destroyBoard(boardCopy, dimension); 
      } 
     } 
    } 
    return optMove; 
} 

Answer 1

Das Konzept des minmax Algorithmus ist «Minimieren Sie den maximalen Verlust» (Wikipedia), so ist das erste, was falsch mit Ihrem Algorithmus ist Ihre Summe.

Für jeden Zustand S des Spiels, und für jede Bewegung M avaialble für den aktuellen Spieler (sagen wir mal, Spieler 1 P1), wird der Wert von minmax (S + M, P2) die für P2 wenn P1 spielt Mmaximal möglich ausgegeben wird. Wenn also P1 seine Gewinnchance maximieren möchte, sollte er die maximale Ausgabe für P2 so weit wie möglich reduzieren, d. H. Er muss die Minimum der Ausgänge finden.

In tictactoe minmax, es möglich ist, das ganze Spiel zu testen (höchstens 9 bewegt), immer jetzt die Sie bedeutet, wenn PX Sieg (1), verliert (-1) oder ein Unentschieden machen (0). So gibt minmax (state, PX) nur einen dieser drei Werte zurück.

In vielen Spiel, können Sie nicht das ganze Spiel (Entwürfe zum Beispiel) spielen, so dass der zurückgegebene Wert eine Anzeige des Staates, zum Beispiel -oo wenn Sie verlieren, +oo wenn Sie gewinnen, Otherwize den Unterschied zwischen Ihrem Anzahl der Entwürfe und dein Gegner.

Answer 2

Es scheint, als ob das Konzept hinter Ihrem Algorithmus fehlerhaft ist. Je nachdem, wie Sie es beschrieben haben, betrachten Sie jede einzelne Spiellinie, anstatt davon auszugehen, dass der Gegner den richtigen Zug macht. Aus diesem Grund hat die Tatsache, dass der Gegner mit dem nächsten Zug gewinnen kann, sehr wenig Gewicht, weil Sie auch alle Optionen berücksichtigen, die die anderen 4 Züge bieten (trotz der Tatsache, dass diese offensichtlich nie gemacht werden). Sie werden Ihren Algorithmus richtig min-max eine Suche des gesamten Satzes von Bord Staaten zu tun

Answer 3

Zu meinem Verständnis, bei der Umsetzung der compMoveScoreRecursive, die rekursiv berechnet Punktzahl hinzugefügt wird über

im Gegensatz verfeinern müssen

score += compMoveScoreRecursive(boardCopy, dimension, i, j, nextTurn); 

statt den Wert zu maximieren oder zu minimieren. Der Wert, der zurückgegeben werden soll, sollte jedoch minimiert werden, abhängig vom Argument turn, was auch der Grund dafür ist, dass der Ansatz als MinMax bezeichnet wird.