• Advertisement
Sign in to follow this  

Prolog and games

This topic is 4009 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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
Advertisement
I've never heard of the game but the description and link make sense.

What is your question about it?

-me

Share this post


Link to post
Share on other sites
Hi,
My question is how to code this game using prolog !
As i'm newbie, i dont know how to do it ...
So can you help me on this please ?

Regards

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
"The tricky part is building the list of all possible moves in a given situation."
I have done this, then how can i apply MinMax .. ?

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
Sign in to follow this  

  • Advertisement