Estoy construyendo un juego de tres en raya para una experiencia de aprendizaje divertida. He construido un algoritmo minimax para devolver el movimiento óptimo para la computadora, pero de alguna manera me estoy equivocando y obtengo un resultado extraño como este
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: PLAYERPuede ver que la computadora eligió la esquina inferior izquierda en lugar de cortar al jugador. Mi código intenta voltear recursivamente entre turnos a través de todos los estados de juego posibles, sumando el puntaje de cada victoria o pérdida a la que puede conducir el turno, luego devuelve el movimiento con el puntaje máximo. La impresión es el puntaje de cada turno antes de que se realice (puedes ver que elige el más alto), entonces, ¿por qué no estoy cortando al jugador? ¿Cómo puedo arreglar esto? Aquí está mi código.
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; }El concepto del algoritmo minmax es «minimizar la pérdida máxima» ( Wikipedia ), por lo que lo primero que falla en su algoritmo es su suma.
Para cualquier estado S del juego, y para cualquier movimiento M disponible para el jugador actual (digamos jugador 1 P1 ), el valor de minmax (S + M, P2) es la salida máxima posible para P2 si P1 juega M Entonces, si P1 quiere maximizar su oportunidad de ganar, debe reducir tanto como sea posible la producción máxima para P2 , es decir, debe encontrar la mínima de las salidas.
En tictactoe minmax , es posible probar todo el juego (como máximo 9 movimientos), lo que significa que siempre sabrás si PX gana (1), pierde (-1) o empata (0). Entonces minmax (state, PX) devolverá solo uno de estos tres valores.
En muchos juegos, no puede jugar todo el juego (borradores, por ejemplo), por lo que el valor devuelto es una indicación del estado, por ejemplo, -oo si pierde, +oo si gana, de lo contrario, la diferencia entre su número de borradores y tu oponente.
Según tengo entendido, en la implementación de compMoveScoreRecursive , la puntuación calculada recursivamente se agrega a través de
score += compMoveScoreRecursive(boardCopy, dimension, i, j, nextTurn); en lugar de maximizar o minimizar el valor. Sin embargo, el valor que se devolverá debe maximizarse o minimizarse, según el argumento turn , que también es la razón por la cual el enfoque se llama MinMax.
Parece que el concepto detrás de su algoritmo es defectuoso. Según la forma en que lo describiste, estás considerando cada línea de juego, en lugar de asumir que el oponente hará el movimiento correcto. Por eso, el hecho de que el oponente pueda ganar con el siguiente movimiento tiene muy poco peso, porque también consideras todas las opciones que ofrecen los otros 4 movimientos (a pesar de que, obviamente, esos nunca se realizarán). Tendrás que refinar tu algoritmo a min-max correctamente en lugar de hacer una búsqueda de todo el conjunto de estados del tablero.