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

I've never heard of the game but the description and link make sense.

What is your question about it?

-me

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

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 ;)

Do you have any idea to how to start coding this game ? strategie ....

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.

"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 .. ?

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:



Hope this helped.

Before this, how can i build the tree with all possible situations ... ?

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.