SWI-Prolog depth-first search?

Question

My aim is to develop a simple program to run a game called 'Kayles' which is similar to Skittles. You have a row of bottles, 2 players knock them down in turns, and the player to knock the last bottle(s) down wins. You can knock 1 or 2 bottles down only, and they have to be next to each other.

The first part of this program was to decide how to represent a bottle, and an empty space. I have decided to use a list, where 1 represents a bottle and 0 represents an empty space.

The second part of this program was to print the current state to the terminal where a bottle is represented by an asterisk * and an empty space is represented by a gap.

The third part of this program was to list and print all the possible next states reachable from a current state. For example, if you have 3 bottles [1,1,1], one possible next state is [0,1,1] as the first bottle was knocked down. So this predicate is supposed to print a list of all possible next states, again represented by * and space.

I have successfully done the above, and this is my code so far:

printstate([]) :- nl.
printstate([B|L]) :- (B=0 -> write(' '); write('*')), printstate(L).

next([1|S], [0|S]).
next([1,1|S], [0,0|S]).
next([0|S], [0|T]) :- next(S,T).
next([1|S], [1|T]) :- next(S,T).

printnextstates(S,T) :- next(S,T), printstate(T), fail.

The next bit is the bit I am stuck on! So the aim is to define the value of a state to be 1 if the first player to move can force a win, and 0 otherwise. I am to write a predicate value(S,X) which will compute the value X of any game state S by a depth-first search through the game tree. I should use assert if possible to avoid the search exploring any position more than once.

I have no idea how to do this!

So far this is what I can come up with:

value(S,X) :- S = 1, ([S,T] = 1); 0.

But I'm sure it's not that simple, yet I have no idea how to begin this question! I've researched depth-first search but I don't really understand it enough to write this... does anyone have any idea how one may go about in starting this question?

Any help is much appreciated!

CapelliC CapelliC · Accepted Answer · 2013-03-07T17:56:25

Since a player is free to pick elements at any position, a remarkable simplification results from an appropriate data representation of the problem: let's say that we keep a list of available bottles. Then you could do just declaring the logic:

win(P) :-
    move(P, P1),
    \+ win(P1).
win(P) :- move(P, []).

move([_|R], R).
move([_,_|R], R).

Here a dumb test, up to some arbitrary length, without noting that a simple recurrence formula gives the result

?- setof(N, L^(between(1,20,N),length(L,N),win(L)), Wins).
Wins = [1, 2, 4, 5, 7, 8, 10, 11, 13|...].

SWI-Prolog depth-first search?

1 Answers