Tron LightCycles ai en Prolog

Question

Tengo el problema de escribir la IA en el juego (como Tron LightCycles). Escribo todos los gráficos y movimientos en C usando NCURSES. Ahora necesito escribir la IA de Bot en el Prólogo. Estoy usando SWI Prolog.

Guardo el campo de juego actual (toda la matriz), la posición humana actual y la posición de bot actual (como las células de matriz I, J). Guarda como predicatos en el archivo .pl de c.

Mi campo de juego es una matriz que contiene 1 y 0 (1 - visitado, 0 - no visitado). Como esto:

human_current_position(0,1).
bot_current_position(1,2).
matrix([[1,1,0,0],
[1,1,1,0],
[0,0,0,0],
[0,0,0,0]]).

Entonces necesito analizar esta matriz como:

analyze(matrix).

Por lo tanto, la función de análisis en Prolog devolverá alguna dirección (izquierda, abajo, hacia arriba o hacia la derecha) guardar en el archivo y mi programa C lee este archivo y moverá el bot.

Así que tengo la pregunta: cómo puedo analizar esta matriz en Prolog. Leí algo sobre el algoritmo Min-Max, pero no puedo darme cuenta de esto en Prolog. ¿Alguien puede ayudar o mostrar la dirección sobre cómo hacer el trabajo Min Max Algoritmo con mi matriz y posiciones actuales en Prolog?

Answer 1

No estoy seguro de si Min-Max conduce a un buen resultado para Tron. Dado que en una cuadrícula, uno tiene muchos movimientos conmutativos, explotando el espacio de búsqueda. Tal vez para un campo pequeño y/o una pequeña profundidad de búsqueda. Pero podría intentar usar la negación como falla para Min-Max y obtendrá la poda de Alfa-Beta de forma gratuita (supongo que sí).

En los juegos sin incertidumbre, el algoritmo Min-Max calcula la ganancia mínima del oponente supuestamente que el oponente, por otro lado, trata de maximizar su ganancia. Deje que atraviese los movimientos de los jugadores y J sobre los movimientos del oponente. Esto lleva a una fórmula recursiva de la siguiente manera:

Worst-Opponents-Gain = min_i (max_j ( Worst-Opponents-Gain_i_j) )

Dado que tratamos con un juego de suma cero que ganan los oponentes es nuestra victoria. Para que tengamos oponentes -ganancia = - gane. Podemos volver a formular la búsqueda Min-Max en una búsqueda máxima. Cada jugador es un maximizador.

Best-Win = max_i ( - Best-Win_i).

Cuando sus valores de ganancia están en el rango {-1, 0, 1}, puede usar la negación como falla. Simplemente implie los siguientes predicados para modelar su juego:

% move(+Board,+Player,-Board)  
% init(+Board)  
% win(+Board,+Player)  
% oposite(+Player,-Player)  
% tie(+Board,+Player)

Los predicados anteriores modelarán el juego por completo en los argumentos, por lo que se almacenará un estado del juego en una variable local. El juego se "analiza" a través del siguiente predicado:

% best(+Board,+Player,-Board)  
best(X,P,Y) :-  
  move(X,P,Y),  
  (win(Y,P) -> true;  
    oposite(P,Q),  
    \+ tie(Y,Q),  
    \+ best(Y,Q,_)).

Es posible que desee agregar parámetros adicionales para limitar la profundidad de búsqueda o para devolver una repesentación simbólica del movimiento.

Adiós

PD: Encuentra un ejemplo de tic-tac-toe aquí.