Your representation should be an internal representation used for evaluating positions in the game; it should not be the external representation shown in the pictures and used for communicating with a human player. You should note that states (a) and (b), as well as states (c) and (d), are equivalent to each other for the purpose of playing the game. (a) and (b) are equivalent because the cells that
are shown in blue and yellow have no subsequent eect on the play of the game. (c) and (d) are equivalent because the ordering of the groups of unmarked cells also has no eect. Your representation should represent equivalent states by identical terms.

In the remaining questions state means internal state.

 Write a Prolog predicate print state(X) which will print a state X to the terminal using an asterisk to represent a markable cell and a space to represent a gap between runs of markable cells.

 Write a Prolog predicate next(S,T) which will succeed if T is a state of the game that can be reached from S in one move. Backtracking should generate all such states T, and findall(T,next(S,T),U) should unify U to the list of all of these states.

Also write a predicate print next states(S) which will use your next predicate to nd and print out all states obtainable from S in one move.

 Write a Prolog predicate win(S), which will succeed for any game state S which is a winning position for the player to play, and will fail otherwise. win(S) is found to be true or false by a depth-rst search through the game tree. You should, if you can, make use of the assert
predicate to avoid the search exploring any position more than once (which will greatly speed it up).

Two tests you can use to check that your predicate is giving the right answers are that a run of markable cells of any odd length is always a win for the rst player, while a state consisting of two groups of markable cells of the same length is always a loss for the rst player.
Write a predicate test value(N), which will apply your win predicate to each of the starting states corresponding to boards of size 1; 2; : : : ;N and print a 1 if the predicate win succeeds and a 0 otherwise. For example:

?- test_value(60).
111011101111101111101110111011111011101110111111111110111011 true.

Write a Prolog predicate choose move(S,T), which will choose a winning move for a player faced with the position S, if there is one, the resulting position being T. Backtracking should generate all winning moves. If there are no winning moves the predicate should fail.

Write another Prolog predicate show winning moves(S), which, by using choose move, prints out all of the winning moves for the player whose turn it is to move from position S.

Write a predicate test winning moves(N), which will apply your show winning moves predicate to each of the starting states corresponding to boards of size 1; 2; 3; : : : ;N, printing out both the board size and the winning moves (if any) from that state. For example
?- test_winning_moves(20).
1 :empty
2 :empty
3 :empty
4 :
5 :* *
6 :****, * **
7 :****, ** **
8 :
9 :*** ***
10 :********, * ******
11 :********, * *******, ** ******, **** ****
12 :** *******
13 :***** *****
14 :
15 :**** ********, ****** ******
16 :**************, ****** *******
17 :**************, *** ***********, ***** *********, ******* *******
18 :*** ************, ***** **********
19 :******** ********
20 :
true.

here empty means a winning move without any cell left to mark for the next player, a blank ne means no winning move, and commas separate winning moves.