Cosa c'è di sbagliato con il mio algoritmo minimax per tictactoe

Question

Sto costruendo un gioco di tic tac toe per una divertente esperienza di apprendimento. Ho costruito un algoritmo minimax per restituire la mossa ottimale per il computer, ma in qualche modo sto andando male e ottenere l'output strano come questo

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 

Si può vedere che il computer ha scelto l'angolo in basso a sinistra, piuttosto che tagliare la giocatore. Il mio codice tenta di capovolgere in modo ricorsivo tra virate attraverso tutti i possibili gamestates, sommando il punteggio per ogni vincita o perdita a cui il turno può portare, quindi restituisce il movimento con il punteggio massimo. La stampa è il punteggio di ogni turno prima che sia fatto (puoi vedere che sceglie il più alto), quindi perché non sto tagliando il giocatore? Come posso risolvere questo? Ecco il mio codice.

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

Il concetto dell'algoritmo minmax è quello di «ridurre al minimo la perdita massima» (Wikipedia), quindi la prima cosa che non va con l'algoritmo è la somma.

per qualsiasi stato S del gioco, e per qualsiasi mossa M avaialble per il giocatore di turno (diciamo giocatore 1 P1), il valore della minmax (S + M, P2) è il massimo possibile uscita per P2 se P1 giochi M. Quindi se P1 vuole massimizzare le sue possibilità di vincere, dovrebbe ridurre il più possibile l'output massimo per P2, cioè deve trovare lo minimo delle uscite.

In tictactoe MinMax, è possibile testare l'intero gioco (al massimo 9 si muove), il che significa l'hai sempre ora se PX vittoria (1), perdono (-1) o fare un pareggio (0). Quindi minmax (state, PX) restituirà solo uno di questi tre valori.

In molti gioco, non si può giocare tutta la partita (bozze per esempio), in modo che il valore restituito è un un'indicazione dello stato, per esempio -oo se si perde, +oo se si vince, Otherwize la differenza tra il vostro numero di bozze e il tuo avversario.

Answer 2

Sembra che il concetto dietro l'algoritmo sia difettoso. In base al modo in cui l'hai descritto, stai prendendo in considerazione ogni singola linea di gioco, invece di supporre che l'avversario farà la mossa giusta. Per questo motivo, il fatto che l'avversario possa vincere con la mossa successiva ha un peso molto piccolo, perché anche tu consideri tutte le opzioni che le altre 4 mosse offrono (nonostante il fatto che ovviamente non saranno mai fatte). Dovrete per raffinare l'algoritmo correttamente min-max in contrapposizione a fare una ricerca su l'intero set di bordo stati

Answer 3

Per la mia comprensione, nella realizzazione di compMoveScoreRecursive, è aggiunto il punteggio in modo ricorsivo calcolato tramite

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

invece di massimizzare o minimizzare il valore. Tuttavia, il valore da restituire deve essere ingrandito al minimo, a seconda dell'argomento turn, che è anche il motivo per cui l'approccio è chiamato MinMax.