artificial intelligence and algorithmics

08 Jun artificial intelligence and algorithmics

Your work for this coursework exercise should be submitted through Blackboard in the form of a Prolog le that can be loaded by SWI-Prolog. Where questions ask you to write ordinary English text, this should be included in the le in the form of Prolog comments.

Your answers will be assessed not only on the correctness of the code, but also for clarity of pro-gramming, documentation, and presentation.

Dawson’s game starts with a row of unmarked cells. Players take it in turns to mark cells, and the player loses who cannot play. A player can mark a cell only if it is not next to a marked cell. So, if the starting position is

the rst player can mark the middle cell, leaving the con guration

where the blue cell is the marked cell and the yellow cells can no longer be marked. Then, whatever the second player does can be mirrored by the rst player. For instance, if the second player mark the cell before last, to get

then the rst player can play the second cell and wins

Clearly the strategy used above generalises to any board with an odd number of cells. When the size of the board is even things are a bit more complicated. However, the game can be fully analysed

 

CMP 1 University of East Anglia

 

CMPSMA24 Arti cial Intelligence and Algorithmics coursework exercise	2013/14

using mathematics. Even if you are good at maths and know this analysis you should not exploit it in your answers to the coursework questions. Besides, at present mathematicians cannot help in solving the misere version of the game | i.e. when you change the termination rule so that the last player who plays loses instead of wins | for sizes that are within the reach of computer implementation of the game.

1. Describe how you would represent a state of the game as a Prolog term. Illustrate your answer by giving the Prolog terms you would use to represent the following states:

(a)

(b)

(c)

(d)

(e)

The nal state, with no cell that can be marked.

 

CMP 2 University of East Anglia

 

CMPSMA24 Arti cial Intelligence and Algorithmics coursework exercise	2013/14

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 commu-nicating 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 e ect on the play of the game. (c) and (d) are equivalent because the ordering of the groups of unmarked cells also has no e ect. Your representation should represent equivalent states by identical terms. [10 %]

In the remaining questions state means internal state.

2. 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. [10 %]

3. 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. [20 %]

4. 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. [40 %]

5. 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 pred-icate 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

 

CMP 3 University of East Anglia

 

CMPSMA24 Arti cial Intelligence and Algorithmics coursework exercise	2013/14
4	:
5	:* *
6	:****, * **
7	:****, ** **
8	:
9	:*** ***
10	:********, * ******
11	:********, * *******, ** ******, **** ****
12	:** *******
13	:***** *****

14 :

15 :**** ********, ****** ******

16 :**************, ****** *******

17 :**************, *** ***********, ***** *********, ******* *******

18 :*** ************, ***** **********

19 :******** ********

20 :

true.

where empty means a winning move without any cell left to mark for the next player, a blank line means no winning move, and commas separate winning moves. [20 %]

 

CMP 4 University of East Anglia