Search Game in Prolog

Question

I was wondering if someone can help me, I have done a lot of work on the 8 Piece puzzle program, and now I want to stretch this out, however I am struggling.

So here is the board.

The idea of this is to try and get a piece for instance P1 which is currently residing at a1 to end up at b1. There can be anywhere up to 5 other pieces on the board and each piece can only occupy and move 1 space at a time.

What I want to be able to do is calculate the moves that are needed to get, for example P1 at position B1, to P1 at position A3 (Or any finishing position to be honest) if it can only move 1 space at a time. No two pieces can occupy the same space, and no pieces can cross over to the other side if their is a piece in the t zone. How can I code it so that when I input something like

?- pmove([at(a1,p3),at(b1,p1),at(b3,p2)], 
         [at(a1,p1),at(b1,p3),at(b3,p2)],M). 

which inputs the starting states of all the positions and where they should all end up It will output something along the lines of:

M = [move(p3,a1,t),move(p1,b1,b2),move(p3,t,b1), 
     move(p1,b2,t),move(p1,t,a1)] 

Showing all of the moves it took to get the piece from start to finish, as well as the moves the other pieces had to take to get to their positions. I believe it would be best to use Breadth First Search for this, but I am not all too sure where to go from there.

Answer 1

This is an excellent problem and working through it will be an excellent way to improve at Prolog! So I commend your choice of problem.

This answer is a sketch, not a complete solution, and I hope that is sufficient for your needs.

What you want to do next is to write a predicate that expresses a single valid move from one state to another, something that looks like this:

singlemove(StartBoardState, Move, NextBoardState) :- ...

So we're going to regard lists of at(Place, Piece) as a board state, and structures like move(Piece,From,To) as a move; the former will unify with StartBoardState and NextBoardState and the latter with Move.

The rules of your game should be encoded in singlemove/3. You could think of it as the relationship between a given board state, every valid move and the resultant states.

I think once you have this, at least one inefficient way to solve your problem will become apparent to you, using a brute-force search. Once you have that working (slowly, possibly only for two-move games), you can begin to see how to improve the performance by making the search more intelligent.

How to Implement singlemove/3

From the question, the rules of this game are:

...it can only move 1 space at a time. No two pieces can occupy the same space, and no pieces can cross over to the other side if their is a piece in the t zone.

So first, let's state some facts about the board. What are the spaces called?

boardspace(b1).
boardspace(b2).
boardspace(b3).
boardspace(t).
boardspace(a1).
boardspace(a2).
boardspace(a3).

Now we need some positional information.

:- op(300, xfx, left_of).
:- op(300, xfx, right_of).    

b1 left_of b2.
b2 left_of b3.
a1 left_of a2.
a2 left_of a3.

row(b1, upper).
row(b2, upper).
row(b3, upper).
row(a1, lower).
row(a2, lower).
row(a3, lower).

X right_of Y :- Y left_of X.

adjacent(X, Y) :- X left_of Y.
adjacent(X, Y) :- X right_of Y.
adjacent(t, X) :- boardspace(X), X \= t.
adjacent(X, t) :- boardspace(X), X \= t.

I'm not sure yet if I'm going to need all of this, but this seems like a plausible start. Now let's address the rules.

There are thus three rules to the game:

1. Only one piece may move per turn.
2. A piece can only move one space per turn.
3. No two pieces can occupy the same space.
4. No pieces can "cross over to the other side" if there is a piece in the t-zone.

I feel like #1 is handled adequately by having a predicate singlemove/3 at all. We call it once, we get one move.

For #2, we can construct the list of nearby spaces based on what is adjacent to the piece right now. Assuming p1 is to move and I have a board as defined above, member(at(StartLocation, p1), Board), adjacent(StartLocation, EndLocation) will unify EndLocation with places that p1 can move. Let's try it:

?- Board = [at(a1,p3),at(b1,p1),at(b3,p2)], 
   member(at(StartLocation, p1), Board), 
   adjacent(StartLocation, EndLocation).
Board = [at(a1, p3), at(b1, p1), at(b3, p2)],
StartLocation = b1,
EndLocation = b2 ;

Board = [at(a1, p3), at(b1, p1), at(b3, p2)],
StartLocation = b1,
EndLocation = t ;
false.

So this seems correct; the adjacent locations to b1 are b2 and t.

Now let's codify the next rule, no two pieces can occupy the same space.

unoccupied(Board, Location) :-
    \+ member(at(Location, _), Board).

Now we can combine these two things into a good start at singlemove/3:

singlemove(Board,
       move(Piece,StartLocation,EndLocation),
       [at(EndLocation,Piece)|RemainingLocations]) :-
    select(at(StartLocation,Piece), Board, RemainingLocations),
    adjacent(StartLocation, EndLocation),
    unoccupied(Board, EndLocation).

Let's try it:

?- Board = [at(a1,p3),at(a2,p1),at(a3,p2)], 
   singlemove(Board, Move, NextBoard).
Board = [at(a1, p3), at(a2, p1), at(a3, p2)],
Move = move(p3, a1, t),
NextBoard = [at(t, p3), at(a2, p1), at(a3, p2)] ;

Board = [at(a1, p3), at(a2, p1), at(a3, p2)],
Move = move(p1, a2, t),
NextBoard = [at(t, p1), at(a1, p3), at(a3, p2)] ;

Board = [at(a1, p3), at(a2, p1), at(a3, p2)],
Move = move(p2, a3, t),
NextBoard = [at(t, p2), at(a1, p3), at(a2, p1)] ;

false.

So what's interesting about this? I'm using select/3 to chop the list into candidates and remainders. I'm building the results in the head of the clause. But otherwise, I'm really just taking your rules, translating them into Prolog, and listing them. So you can see you just need one more predicate to implement your fourth rule and it will go right after unoccupied/2, to further filter out invalid moves.

Hopefully, you get the gist of the process. My data model may be too much, but then again, you may find you need more of it than it seemed at first. And the search strategy is weak. But this is the underpinning of the overall solution, the base case. The inductive case will be interesting—I again suggest you try it with the built-in depth-first strategy and see how horrible it is before resorting to BFS. You will probably want to use trace/0 and see when you get stuck in a trap and how you can circumvent it with better explicit reasoning. But I think this is a good start and I hope it's helpful to you.