## Artificial Intelligence: Problem Set 6: Solutions

### Problem 1.

The best move from the root is to the left.
### Problem 2:

- A. The best move is CY, with value 3 (3 for Y + 3 for C - 1 for E
- 1 for Z - 1 for diagonal AV-EZ.) In contrast, EZ has a value of 2 (1 for C
+ 1 for Y).
- B. The best move is EZ, with value 2 (1 for C + 1 for Y). Player O will
respond with CY, attaining a board with value 0. By
contrast, if X plays to CY, then O will repond to EZ, attaining a board with
value
-3. (3 for Y + 3 for C - 3 for E - 3 for Z - 3 for
the diagonal.)

### Problem 3:

Initially,
G = { A-J X 1-10 }

S = { emptyset }

On encountering the point C,5: IN:

The rule in G, A-J X 1-10, is correct, so unchanged.

The rule in S is a false negative and must be generalized.
There are four minimal generalizations that include C,5:
A-C X 1-5,
A-C X 5-10,
C-J X 1-5,
C-J X 5-10.

Therefore the new values of G and S are

G: { A-J X 1-10 }

S: { A-C X 1-5, A-C X 5-10, C-J X 1-5, C-J X 5-10 }.

On encountering the point F,3: OUT.

The rule A-J X 1-10 in G is a false positive. There are four
maximal specializations that exclude F,3: A-E X 1-10,
G-J X 1-10, A-J X 1-2, A-J X 4-10. However, the
rules G-J X 1-10 and A-J X 1-2 are inconsistent with the
previous point C,5 : IN.

The rule A-C X 1-5 in S gives the correct answer, and so is unchanged.

The rule A-C X 5-10 in S gives the correct answer, and so is unchanged.

The rule C-J X 1-5 in S is a false positive and so is dropped.

The rule C-J X 5-10 in S gives the correct answer, and so is unchanged.

Therefore,

G = { A-E X 1-10, A-J X 4-10 }

S = { A-C X 1-5, A-C X 5-10, C-J X 5-10 }.

On encountering the point E,8 : OUT.

The rule A-E X 1-10 in G is a false positive. The maximal
specializations of this rule that
exclude point E,8 are A-D X 1-10, A-E X 1-7,
and A-E X 9-10. However, the last of these is inconsistent with the
previous point C,5 : IN.

The rule A-J X 4-10 gives a false positive for E,8. The maximal
specializations of this rule that exclude E,8 are A-D X 4-10, F-J
X 4-10, and A-J X 9-10. However, all but the first of these
is inconsistent with the previous point C,5 : IN.

The rule A-C X 1-5 in S gives the correct answer, and so is unchanged.

The rule A-C X 5-10 in S gives the correct answer, and so is unchanged.

The rule C-J X 5-10 in S is a false positive, and so is dropped.

Therefore,

G = { A-D X 1-10, A-E X 1-7, A-D X 4-10 }

S = { A-C X 1-5, A-C X 5-10 }