Tron lightcycles AI in Prolog

Question

I have a problem writing an AI for a game (e.g. tron ​​lightcycles). I write all the graphs and movements in C using ncurses. Now I need to write bot ai in the prolog. I use prog. Swi.

I save the current field of the game (the entire matrix), the current position of the person and the current position of the bot (for example, the cells of the matrix i, j). They are saved as predicates in the .pl file from c.

My field of play is a matrix containing 1 and 0 (1 - visited, 0 - unaffected). 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 as:

 analyze(matrix). 

Thus, the analysis function in the prolog will return some direction (left, down, up or right) to save to a file and my program c read this file and moved the bot.

So, I have a question: how can I parse this matrix in Prolog. I read something about the min-max algorithm, but I cannot figure it out in Prolog. Can someone help or show direction, how to make the min max algorithm work with my matrix and current positions in Prolog?

Answer 1

I am not sure if min-max produces a good result for tron. Since there are usually many commutative movements on the grid, inflating the search space. Maybe for a small field and / or a small search depth. But you can try to use negation as a rejection for min-max, and you get alpha-beta cropping for free (I think so).

In games without uncertainty, the min-max algorithm calculates the minimum gain of the opponent, who, on the other hand, tries to maximize his gain. Let me run along the players and j move over the opponent. This leads to a recursive formula as follows:

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

Since we are dealing with a zero-sum game, the victory of our opponents is our victory. So we have Opponents-Gain = - Win. We can reformulate the min-max search to the maximum search. Each player is a maximizer.

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

When your winnings are in the range {-1, 0, 1}, you can use negation as a failure. Just follow these predicates to simulate your game:

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

The above predicates will fully simulate the game in the Arguments, so the state of the game will be stored in a local variable. The game is then “parsed” using 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 depth of your search or return a symbolic reflection of movement.

Bye

PS: You will find an example of tic-tac-toe here .