The Path Game. Alice and Bob alternately place a checker on an unoccupied square of an initially empty eight-by-eight checkerboard (see the figure here). The rule is that after Alice places her initial checker, every new checker must be (orthogonally) adjacent to the most recently placed checker. The players are in effect constructing a path of checkers. The last player to make a legal move wins the game. Your mission: find a winning strategy for Bob.
The Match Game. Suppose that Alice, when it is her turn, is no longer obliged to play next to Bob’s last checker and may instead place her checker on any unoccupied square. Bob is still constrained to “match” Alice, that is, to play next to Alice’s last move. As in the Path Game, the last player to make a legal move wins the game. So who wins now, with best play?
General graphs. Either the Path Game or the Match Game can be played on any finite graph. Alice begins by marking any vertex, and, subsequently, Bob and Alice alternate in marking vertices. In the Path Game, each marked vertex must be adjacent to the most recently marked vertex. In the Match Game, each vertex marked by Bob must be adjacent to the most recently marked vertex, but Alice can mark any unmarked vertex when it is her turn. As in the checkerboard versions, the last player to make a legal move wins the game. Now find a graph on which, with best play, Bob wins the Path Game and Alice wins the Match Game… if there is one.
Join the Discussion (0)
Become a Member or Sign In to Post a Comment