minimax para tic-tac-toe

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 en 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.

Nota 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 usted ya tiene su movimiento/4 predicado, me gustaría comenzar con la recogida de todos los movimientos que son posibles:

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

Y entonces es simplemente una cuestión de la evaluación de cada movimiento, no es ¿eso? 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.