Exercises: $5\mathrm{.}8$

Figure $5\mathrm{.}17$ The starting position of a simple game. Player A moves first. The two players

take turns moving, and each player must move his token to an open adjacent space in either

direction. If the opponent occupies an adjacent space, then a player may jump over the

opponent to the next open space if any. $($For example, if $A$ is on $3$ and $B$ is on $2,$ then A may

move back to $1.)$ The game ends when one player reaches the opposite end of the board. If

player A reaches space $4$ first, then the value of the game to $A$ is $1$ if if player $B$ reaches

space $1$ first, then the value of the game to $A$ is $-1.$

$5\mathrm{.}8$ Consider the two$-$player game described in Figure $5\mathrm{.}17.$

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

Write each state as $(s,1,s_B),$ where is and sin denote the token locations.

Put each terminal state in a square box and write its game vatue in a circle.

Put loop states $($states that already appear on the path to the root$)$ in double square

boxes. Since their value is unclear, annotate each with a $"?""$ in a circle.

b$.$ Now mark each node with its backed$-$up minimax value $($also in a circle$).$ Explain how

you handled the $"?"$ values and why.

c$.$ Explain why the standard minimax algorithm would fail on this game tree and briefly

sketch how you might fix it$,$ drawing on your answer to $($b$).$ Does your modified algo$-$

rithm give optimal decisions for all games with loops?

d$.$ This $4-$square game can be generalized to $n$ squares for any $n>2.$ Prove thait A wins

if $n$ is even and loses if $n$ is odd.