Assigned: Nov. 17

Due: Nov. 24

X gets --

Infinity if X has won.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.

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.

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

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 }If the player then tries guessing point C,4 and gets answer OUT, then the algorithm proceeds as follows:

S: { A-C x 1-4, G-J x 1-4, G-J x 4-10 }

In G:The next state of the algorithm is therefore

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.

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