How can I code a specific game in Prolog?

Question

I have a problem with coding the program described below

Consider the following game. A board with three black stones, three white stones and an empty space is given. The goal of the game is to swap places of black pawns with white pawns. Moving rules define the following sentences: Move the white and black pieces alternately. Each pawn can move vertically or horizontally taking up an empty space. Each piece can jump vertically or horizontally over another piece (of any color). Write a program in Prolog to find all possible ways to find a winning sequence. For example, if we ask the question:

? - play (w, s (w, w, w, e, b, b, b), s (b, b, b, e, w, w, w), S, R ). 

The prologue should answer, for example:

S = [s (w, w, w, e, b, b, b), s (w, e, w, w, b, b, b), ..., s (b, b, b, e, w, w, w)] R = [[w, 2,4], [b, 6,2], [w, 4,6], ..., [w, 4,6]] 

Here [ w, 2,4] means moving the white pawn from position 2 to position 4. Of course Prolog should return both letters S and R in full (without "...").

What is the maximum number of different pawn settings possible on the board? Check the query:

? - play (_, s (w, w, w, e, b, b, b), s (b, b, e, w, w, b, w), _, _).

What does Prolog's answer mean? Hint: solve the problem for play/4 without R first

There's also a game board that looks like this:

I have no clue at all even where to start? How can I do that? Could you guys, help me with this one?

Answer 1

This is a standard state space search, a standard paradigm of GOFAI since the mid 50s at least.

The barebones algorithm:

search(State,Path,Path) :- is_final(State),!.  % Done, bounce "Path" term
search(State,PathSoFar,PathOut) :- 
   generate_applicable_operators(State,Operators),
   (is_empty(Operators) -> fail ; true),   
   select_operator(Operators,Op,PathSoFar),
   apply_operator(State,Op,NextState), % depth-first / best first 
   search(NextState,[[NextState,Op]|PathSoFar],PathOut).

% Called like this, where Path will contain the reverse Path through
% State Space by which one may reach a final state:

search(InitialState,[[InitialState,nop]],Path).

First you need to represent a given state in this case the state of the board (at some time t).

We can either list the board positions and their content (w for white, b for black, e for empty token) or list the tokens and their positions. Let's list the board positions.

In Prolog, a term that can be easily pattern-matched is appropriate. The question already provides something: (w, w, w, e, b, b, b). This seems to be inspired by LISP and is not well adapted to Prolog. Let's use a list instead: [w, w, w, e, b, b, b]

The mapping of board positions to list positions shall be:

       +---+---+
       | 0 | 1 |
   +---+---+---+
   | 2 | 3 | 4 |
   +---+---+---+
   | 5 | 6 |
   +---+---+

And we are done with setting up a state description!

Then you need to represent/define the operators (operations?) that can be applied to a state: they transform a valid state into another valid state.

An operator corresponds to "moving a token" and of course not all operators apply to a given state (you cannot move a token from field 1 if there is no token there; you cannot move a token to field 1 if there already is a token there).

So you want to write a predicate that links a board state to the operators applicable to that state: generate_applicable_operators/2

Then you need to select the operator that you want to apply. This can be done randomly, exhaustively, according to some heuristic (for example A*), but definitely needs to examine the path taken through the state space till now to avoid cycles: select_operator/3.

Then you apply the operator to generate the next state: apply_operator/3.

And finally recursively call search/3 to find the next move. This continues until the "final state", in this case [b, b, b, e, w, w, w] has been reached!

You can also use Iterative Deepening if you want to perform "breadth-first search" instead, but for that the algorithm structure must be modified.

And that's it.