Sign in to follow this  
HeavenX

Prolog and games

Recommended Posts

Hi, I have to code this game in Prolog langage : this game is a play with 2 players which exploits a square of 5 times 5 boxes. Each player, in turn, chooses a line or a column and notches there with several white boxes. You cant by passe your turn,i mean you must play: at least a box should be notched. The notched boxes must be aligned horizontally or vertically. Thus, progressively, there are more and more notched boxes. The goal of the play is to notch the last box. Have you ever heard about this game ??? PS: http://atif.atif.free.fr/game.JPG

Share this post


Link to post
Share on other sites
Did some Prolog-type programming in the uni, but cant remember it at all anymore... this might be a good place to start for you:
http://ktiml.mff.cuni.cz/~bartak/prolog/learning.html

PS. Just google "prolog programming", theres a lot of tutorials around ;)

Share this post


Link to post
Share on other sites
I assume you want to program the AI player that can play this game.

In this case using the MinMax algorithm seems like the only reasonable choice. (http://en.wikipedia.org/wiki/Minmax) Luckily inplementing the MinMax search itself is rather trivial in prolog.

The tricky part is building the list of all possible moves in a given situation. The 'setof' predicate can prove most helpful in this case.

I hope this is enough to get you started.

Share this post


Link to post
Share on other sites
Basically what you want to do is a reursive predicate (I named it minmax in this case) that is aware of the situation on the board, and in each step does something along the lines of:

minmax:
* Generate all possible moves from this situation.
* If no such move exists this situation means an ended game, and the active player loses. Return a value (1000/-1000 depending if it was the min or max players turn)
* If possible moves exist, call minmax for the situation of the board after each move.
* When all the subsequent calls returned, chose the one with the highest/lowest score, and return it.

This would be the ideal case, where you have enough resources to serch through the whole game tree. This is not probable. (might be though, since your game doesn't seem to have a high branching factor or a deep game tree). You'll probably have to limit the depth of your search, and use heuristics to guess a value for the node in the limit depth.

To give you an idea how this should look like in Prolog, I'll paste here a part of our (me + a fellow student) solution on checkers that was a project for our logical programming class:


minmax(Board,Player,BestSucc) :-
minmax(Board,Player,BestSucc,_,4),!,if(BestSucc=[],fail,true).

minmax(Board,Player,BestSucc,Value,Depth) :-
allMoves(Board,Player,MoveList),
executeAll(Board,Player,MoveList,BestSucc,Value,Depth).

%===============================================================================

% if possible moves list is empty, current player loses:
executeAll(_,1,[],_,1000,_).
executeAll(_,2,[],_,-1000,_).

% if depth of recursion reaches limit, value is approximated
executeAll(Board,1,_,_,Value,1) :- countStone(Board,X,Y), Value is -(2*X)+(2*Y).
executeAll(Board,2,_,_,Value,1) :- countStone(Board,X,Y), Value is -(2*X)+(2*Y).

executeAll(Board,Player,[Move|MoveList],BestSucc,Value,Depth) :-
executeMove(Player,Board,Move,NewBoard),
swap(Player, NextPlayer),
D is Depth - 1, minmax(NewBoard,NextPlayer,_,Value1,D),
executeAll(Board,Player,MoveList,BestSucc2,Value2,Depth), if(BestSucc2=Move,true,true),
if(better(Player,Value1,Value2),(Value=Value1, BestSucc=Move),(Value=Value2, BestSucc=BestSucc2)).



Hope this helped.

Share this post


Link to post
Share on other sites
Well, what you want to build is not a tree of moves, but a set of the possible moves in the current turn. You need to implement allMoves(Board,Player,MoveList) from my previous code, with Board being the current situation, Player being the player on the move, and MoveList being a free variable for the output. That is the part where the generating of the possible moves is called by MinMax.

One possible move would be a list of the fields that are marked, so the MoveList in the end should be a list of lists.

For this, you'll need to write a predicate that succeeds exactly for every valid move. If you call setof( yourpredicate(whatever) ) then Prolog takes care of the rest, and collects all the cases where your predicate succeeded into a list.

Sorry I don't have code for this part, as it's quite game specific, you'll probably need to figure it out yourself. Hope I was of some help.

Share this post


Link to post
Share on other sites
Night Crawler's reply should be really helpful for you, but I wanted to add if you manage to find a constraint satisfaction problem(CSP) formulation for the game, you can implement it in another way. And maybe you find it easier. (www.lirmm.fr/~bessiere/stock/cp06ws-scsp.pdf)

HTH,
Hesham

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this