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