Exercise 13.1 The aim of this exercise is to explore multiple representations for the same domain.

Tic-tac-toe is a game played on a 3 × 3 grid. Two players, X and O, alternately place their marks in an unoccupied position. X wins if, during its turn, it can place an X in an unoccupied position to make three X’s in a row. For example, from the state of the game X O O X

X O X can win by moving into the left middle position.

Fred, Jane, Harold, and Jennifer have all written programs to determine if, given a state of the game, X is able to win in the next move. Each of them has decided on a different representation of the state of the game. The aim of this question is to compare their representations.

Fred decides to represent a state of the game as a list of three rows, where each row is a list containing three elements, either x, o, or b (for blank). Fred represents the above state as the list

[[x, o, o], [b, x, b], [x,

b, o]].

Jane decides that each position on the square could be described by two numbers, the position across and the position up. The top left X is in position pos(1, 3), the bottom left X is in position pos(1, 1), and so forth. She represents the state of the game as a pair ttt(XPs, OPs) where XPs is the list of X’s positions and OPs is the list of O’s positions. Thus, Jane represents the above state as ttt([pos(1, 3), pos(2, 2), pos(1, 1)], [pos(2, 3), pos(3, 3), pos(3, 1)]).

Harold and Jennifer both realize that the positions on the tic-tac-toe board could be represented in terms of a so-called magic square:

6 7 2 1 5 9 8 3 4 The game is transformed into one where the two players alternately select a digit.
No digit can be selected twice, and the player who first selects three digits summing to 15 wins.
Harold decides to represent a state of game as a list of nine elements, each of which is x, o, or

b, depending on whether the corresponding position in the magic square is controlled by X, controlled by O, or is blank. Thus, Harold represents the game state above as the list [b, o,

b, o, x, x, o, x, b].
Jennifer decides to represent the game as a pair consisting of the list of digits selected by X and the list of digits selected by O. She represents the state of the game above as magic([6, 5, 8], [7, 2, 4]).

(a) For each of the four representations, write the relation to determine whether X has won based on that representation, such as x won fred(State), with the intended interpretation that X has won the game in state State based on Fred’s representation (and similarly for the other three representations).

(b) Which representation is easier to use? Explain why.

(c) Which representation is more efficient to determine a win?

(d) Which representation would result in the simplest algorithm to make sure a player does not lose on the next move, if such a move exists?

(e) Which do you think is the best representation? Explain why. Suggest a better representation.