## Artificial Intelligence: Problem 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?

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

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?

Note: You need not show the entire game tree for any part of this
problem. Use your common sense to choose the moves worth considering.

### 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.)