CSCI 3202: Artificial Intelligence, Fall 2000

Problem Set 5 Partial Solutions

5.1 There are many possible neural nets that compute the XOR function. Here's one: the units are "standard" 0/1 units. Arrows are labelled with their weights, and the hidden and output units are labelled with their threshold values.

5.2 When the junctions are examined in the order A, B, C, D, the answer is straightforward. Junction A must have a + label on the center edge (that's the only possible arrow with two boundary edges). This in turn implies that B (a Y-junction) must have three + edges; which in turn implies that C (an arrow junction) has a central - edge and another + edge on the other "arrow-barb"; which implies that D is another Y-junction with three + edges. When the junctions are examined in a different order, the labelling has to proceed by searching among the possibilities. (That is, we can treat this problem as an instance of search in which "moves" are allowable new label placements.) The resulting labelling would be the same, but it would in general require a more extensive search.

5.3a. RED will never play row A; and BLUE will never play column C, since both these choices are dominated by other choices of the two players. This leaves a 2 by 2 matrix in which neither player has a clear choice. We can solve for a mixed strategy for RED by noting that it should return a constant value to RED no matter what BLUE plays. Thus, if RED plays strategy B with a probability of p, then:

p * 0 + (1 - p) * 1 = p * 1 + (1 - p) * 0.75 = V

so

1 - p = 0.25 p + 0.75

or

0.25 = 1.25 p

so

p = 0.2 and V = 0.8

5.3b. This is not a prisoner's dilemma situation. For one thing, in a prisoner's dilemma situation, each player has a dominant strategy. But here, although BONNIE has a dominant strategy, CLYDE does not.

There is an equilibrium point -- i.e., a combination of strategies such that if the two players employ that combination in an iterated game, neither has the desire to switch unilaterally. The equilibrium point is represented by BONNIE's strategy B and CLYDE's strategy A.