Consider the two-player game described in Figure.

a. Draw the complete game tree, using the following conventions:

• Write each state as (SA, SB) where SA and 5B denote the token locations.

• Put each terminal state in square boxes and write its game value in a circle.

• Put loop states (states that already appear on the path to the root) in double square boxes. Since it is not clear how to assign values to loop states, annotate each with a “?” in a circle.

b. Now mark each node with its backed-up mini max value (also in a circle). Explain how you handled the “?” values and why.

c. Explain why the standard mini max algorithm would fail on this game tree and briefly sketch how you might fix it, drawing on your answer to (b). Does your modified algorithm give optimal decisions for all games with loops?

d. This 4-square game can be generalized to n squares for any n > 2. Prove that A wins if n is even and loses if n is odd.

Transcribed Image Text:

1 2 34