Tron Lightcycles AI in Prolog

Question

Ho il problema di scrivere l'IA al gioco (come Tron LightCycles). Scrivo tutte le grafiche e i movimenti su C usando ncurses. Ora ho bisogno di scrivere l'IA del bot sul prolog. Sto usando SWI Prolog.

Salvo l'attuale campo di gioco (tutta la matrice), l'attuale posizione umana e la posizione di bot attuale (come le celle della matrice I, j). Salvano come predicati nel file .pl da c.

Il mio campo di gioco è una matrice che contiene 1 e 0 (1 - visitato, 0 - non visitato). Come questo:

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]]).

Allora ho bisogno di analizzare questa matrice come:

analyze(matrix).

Quindi la funzione di analisi in Prolog restituirà una direzione (a sinistra, giù, in alto o a destra) salva nei file e il mio programma C leggi questo file e sposterà il bot.

Quindi ho la domanda: come posso analizzare questa matrice in Prolog. Ho letto qualcosa sull'algoritmo Min-Max, ma non riesco a renderlo conto in Prolog. Qualcuno può aiutare o mostrare la direzione su come fare il lavoro minimo algoritmo con la mia matrice e le posizioni attuali in Prolog?

Answer 1

Non sono sicuro che Min-Max porti a un buon risultato per Tron. Poiché su una griglia si ha di solito molte mosse commutative, facendo esplodere lo spazio di ricerca. Forse per un piccolo campo e/o una piccola profondità di ricerca. Ma potresti provare a usare la negazione come fallimento per Min-Max e ottieni la potatura Alfa-Beta gratuitamente (immagino di sì).

Nei giochi senza incertezza, l'algoritmo Min-Max calcola il guadagno minimo dell'avversario supposto che l'avversario d'altra parte cerca di massimizzare il suo guadagno. Lascia che io vada sulle mosse dei giocatori e J sulle mosse dell'avversario. Questo porta a una formula ricorsiva come segue:

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

Dal momento che ci occupiamo di una partita di somma zero, il guadagno degli avversari è la nostra vittoria. In modo che abbiamo avversari -gain = - vittoria. Possiamo riformulare la ricerca Min-Max in una ricerca massima. Ogni giocatore è un massimizzatore.

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

Quando i valori di vittoria sono nell'intervallo {-1, 0, 1}, puoi usare la negazione come errore. Basta implementare i seguenti predicati per modellare il tuo gioco:

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

I predicati sopra modelleranno il gioco completamente negli argomenti, quindi uno stato di gioco verrà archiviato in una variabile locale. Il gioco viene quindi "analizzato" tramite il seguente predicato:

% 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,_)).

Potresti voler aggiungere ulteriori parametri per limitare la profondità di ricerca o per restituire una ripetizione simbolica della mossa.

Ciao

PS: trovi un esempio tic-tac-toe qui.