Tron lightcycles AI in Prolog

Question

I have the problem to write the AI to game(like tron lightcycles). I write all the graphics and movements on C using ncurses. Now i need to write the bot's ai on the prolog. I'm using swi prolog.

I save the current game field(all matrix), current human position and current bot position(like matrix cells i, j). They saves like predicats in the .pl file from c.

My game field is a matrix which contains 1 and 0( 1 - visited, 0 - unvisited ). Like this:

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

Then i need to analyze this matrix like:

analyze(matrix).

So the analyze function in prolog will return some direction(left, down, up or right) save into file and my c program read this file and move the bot.

So I have the question - How i can analyze this matrix in Prolog. I read something about min-max algorithm, but i can't realize this in Prolog. Can anyone helps or show the direction how to make work min max algorithm with my matrix and current positions in Prolog?

Answer 1

I am not sure whether min-max leads to good result for tron. Since on a grid one has usually many commutative moves, blowing up the search space. Maybe for a small field and/or a small search depth. But you could try to use negation as failure for min-max and you get alfa-beta pruning for free (I guess so).

In games without uncertainty the min-max algorithm computes the minimal opponent gain supposed the opponent on the other hand tries to maximize his gain. Let i range over the players moves and j over the opponent moves. This leads to a recursive formula as follows:

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

Since we deal with a zero sum game the opponents gain is our win. So that we have Opponents-Gain = - Win. We can re-formulate the min-max search into a max search. Each player is a maximizer.

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

When your win values are in the range {-1, 0, 1} then you can use negation as failure. Just implement the following predicates to model your game:

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

The above predicates will model the game completely in the Arguments, thus a game state will be stored in a local variable. The game is then "analyzed" via the following predicate:

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

You might want to add additional parameters to limit the search depth, or to return a symbolic repesentation of the move.

Bye

P.S.: You find a tic-tac-toe example here.