Artificial Intelligence: Problem Set 6

Assigned: Nov. 17
Due: Nov. 24

Problem 1

Suppose that the game tree below is evaluated left to right using alpha-beta pruning. Show which branches are pruned. What is the correct move at the top?

Problem 2

Consider playing 5x5 Tic-Tac-Toe. Suppose we are using the following evaluation function for X.

X gets --

Infinity if X has won.
10 points for each row, column or main diagonal where X has 4 and O has none.
3 points for each row, column or main diagonal where X has 3 and O has none.
1 point for each row, column or main diagonal where X has 2 and O has none.
Minus infinity if O has won.
-10 points for each row, column or main diagonal where O has 4 and X has none.
-3 points for each row, column or main diagonal where O has 3 and X has none.
-1 point for each row, column or main diagonal where O has 2 and X has none.
For example, on the board shows below, the evaluation function returns -1 (1 for row C plus 1 for column Y minus 1 for row E minus 1 for column Z minus 1 for the diagonal AV-EZ.

A. Suppose X does 1-ply look-ahead (i.e. considers only his next move.) What is returned as the value of the board below? What is returned as the best move?

B. Suppose X does 2-ply look-ahead (i.e. considers his next move and O's response.) What is returned as the value of the board below? What is returned as the best move?

(Note: You do not have to draw out the game tree.)

Problem 3.

Consider the following game, somewhat along the lines of ``Battleship": The game is played on a 10x10 grid. Each player has his own private copy of the grid. The first player secretly draws a horizontal and a vertical line on the grid. He then chooses one quadrant as ``IN" and the remaining quadrants as ``OUT.'' The second player then asks about a series of sample points, and the first player says whether each one is IN or OUT. The object of the second player is to figure out where the lines are. For instance, one possible choice for the first player is shown below. This board can be abbreviated ``A-B x 1-6.''

As a degenerate case, the first player is allowed to draw only a single line, horizontal or vertical, and pick one side or another as ``IN''; or to draw no lines at all, and pick either the whole board to be ``IN'' or the whole board to be ``OUT''. The second player decides to apply the Version Spaces (Candidate Elimination) algorithm to this problem. A ``rule'' is a pair of lines and a choice of quadrant, describing the set of IN points. Thus, an answer of IN corresponds to ``true'' while OUT corresponds to false. One rule is more general than another if the IN points in the first are a superset of the IN points in the second. For example, at some stage of a game on the above board, the state of the version spaces algorithm might be:
G: { A-J x 1-5, A-D x 1-10 }
S: { A-C x 1-4, G-J x 1-4, G-J x 4-10 }
If the player then tries guessing point C,4 and gets answer OUT, then the algorithm proceeds as follows:
In G:
Rule A-J x 1-5 gives a false positive for point C,4:OUT. There are three maximal specializations that exclude this point: A-B x 1-5, D-J x 1-5, and A-J x 1-3.
Rule E-J x 1-10 is correct for point C,4:OUT. Rule remains unchanged.

In S:
Rule A-C x 1-4 gives a false positive for point C,4:OUT. Rule is dropped.
Rule G-J x 1-4 is correct on C,4:OUT. Rule remains unchanged.
Rule G-J x 4-10 is correct on C,4:OUT. Rule remains unchanged.

The next state of the algorithm is therefore
G: { A-B x 1-5, D-J x 1-5, A-J x 1-3, E-J x 1-10 }.
S: { G-J x 1-4, G-J x 4-10 }

Now, suppose that, at the beginning of a new game on a different board, the first three tries of the second player are as follows:

C,5 : IN
F,3 : OUT
E,8 : OUT

Trace the evolution of the two sets G,the maximally general rules consistent with the data, and S, the maximally specific rules consistent with the data, after each of the above three tries. Assume that initially (before any examples are seen) G is the set containing the single rule ``All points are IN'', and S is the set containing the single rule ``All points are OUT.''