algorithm - ultimate - minimax para tic-tac-toe

tic tac toe minimax java

Question

Estoy tratando de resolver el tic-tac-toe con un algoritmo minimax simple. Simple, pero debe cubrir gran parte del idioma. Lo que tengo hasta ahora

La placa se representa como una matriz de 9 variables (sin consolidar), que se configuran como x o o .

La condición de victoria es básicamente: win(Player, [X1,X2,X3|_]) :- X1==Player,X2==Player,X3==Player. etc. para las ocho variantes. dibujar es solo una simple comprobación de si todas las variables están vinculadas.

Las cláusulas move también son simples: move(Player, [X|_], 0, 0) :- var(X), X=Player. , de nuevo para todas las posiciones posibles (dejaré abierta la reutilización de código para un programa posterior :)).

Ahora puedo generar todos los movimientos posibles por retroceso simple: move(Player, Board, X, Y). que básicamente debería ser todo lo que necesito para minimax (obviamente una función de utilidad simple que devuelve 1 si la computadora gana, 0 en caso de empate y -1 si el humano gana, eso es fácil). Simplemente no tengo idea de cómo implementarlo y todos los ejemplos que encuentro en la red son bastante complicados y no están bien explicados.

Tenga en cuenta que estoy bien con n ^ 2 o peor comportamiento en el tiempo de ejecución, realmente no se trata de eficiencia. Y sí, sé cómo escribir minimax en lisp, python, java, simplemente no tengo idea de cómo "portar" ese código a prolog.

Answer 1

Bueno, como ya tienes tu predicado move / 4, comenzaría coleccionando todos los movimientos que sean posibles:

findall(XY, move(Player, Board, X, Y), Moves)

Y luego es simplemente una cuestión de evaluar cada movimiento, ¿no es así? Para eso escribiría un predicado como board_player_move_value/4 que, dado un tablero y un movimiento de un jugador determinado, determina qué tan bueno es el movimiento para este jugador. Es este predicado el que probablemente dependa de los movimientos posteriores que sean posibles (para el otro jugador) en esta etapa, y aquí es donde tiene lugar el minimax. Por ejemplo, si este movimiento gana el juego, es un buen movimiento. Si el otro jugador puede ganar en el próximo movimiento, es un mal movimiento, etc. Usaría este predicado para crear una colección de términos de la forma Value-Move, usar keysort / 2 para ordenarlos, y luego elegir uno de los movimientos con el mejor valor, donde "lo mejor" depende de si estoy tratando de encontrar un movimiento para minimizar o maximizar al jugador.