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:

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:

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