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:

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:

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