## Artificial Intelligence: Solution Set 6

Assigned: Mar. 19

Due: Mar. 26

### Problem 1

Consider the game of 5x5 Tic-Tac-Toe. Suppose that the current board is
as follows:

It is X's turn to play.

Suppose that player P uses the following evaluation function:

- 100 points if P has won.
- -100 points if P has lost.
- Add 2 points for each line (row, column, or major diagonal)
where P has two pieces and Q has none.
- Add 3 points for each line where P has three pieces and Q has none.
- Add 4 points for each line where P has four pieces and Q has none.
- Subtract 2 points for each line where Q has two pieces and P has none.
- Subtract 3 points for each line where Q has three pieces and P has none.
- Subtract 4 points for each line where Q has four pieces and P has none.

Thus the value of the current board for X is -1:
2 for row E minus 3 for row A.

A. If X does a one-ply search (i.e. to just after he plays), where will he
play?

** Answer: ** To D2, giving value 5 (2 for row D + 2 for row E + 2 for
2 for col 2 + 2 for diagonal - 3 for row A.)

B. If X does a two-ply search (to just after X responds), where will he play?

** Answer: **
Still to D2. If X plays
to D2, then O's best play is to C3 or D4, giving the board the value -1
(2 for row D + 2 for row E + 2 for col 2 - 3 for row A - 2 for diagonal -
2 for col 3).
By contrast if X plays to E5, then O can reply to C3, giving the board value -2
(2 for row E - 2 for col 3 - 2 for diagonal.)

C. Consider the following alternative evaluation function:

- 100 points if P has won.
- -100 points if P has lost.
- Add 1 point for each line
where P has two pieces and Q has none.
- Add 5 points for each line where P has three pieces and Q has none.
- Add 10 points for each line where P has four pieces and Q has none.
- Subtract 1 point for each line where Q has two pieces and P has none.
- Subtract 5 points for each line where Q has three pieces and P has none.
- Subtract 10 points for each line where Q has four pieces and P has none.

Where will X play if he does a one-ply search? A two-ply search?

** Answer: ** One-ply: Either to A2 or to A5, giving value 2 (1 for row E +
1 for column 2 / diagonal. Two-ply: To A2. O's best responses are to B2,
to C3 or to E5, any of which give a final value of 0.
has value -1.)

### Problem 2

Suppose that the game tree shown below is evaluated left-to-right using
alpha-beta pruning. Show which branches become pruned. (You may
do this on the problem set sheet, if you want.)