Alice and Bob play a game on the following irregular chessboard. (Note the blacked out squares are not legal moves.)

The game board.

  • Alice starts the game by placing a knight on any square she chooses.
  • They then take turns, starting with Bob, moving the knight as a knight moves in chess.
  • Immediately reversing the previous move is not allowed. That is, if one player moves the knight from square $x$ to square $y$, the next player is not allowed to move to square $x$ during the immediate next turn.
  • The winner is the first player to move to a square that has been previously occupied sometime during the game.

Who wins with optimum play and why?

  • $\begingroup$ Do we need to provide a winning strategy or is a proof enough? $\endgroup$ – VicAche Dec 12 '15 at 12:08
  • $\begingroup$ I'm expecting a proof without any specific winning strategy. $\endgroup$ – Tyler Seacrest Dec 12 '15 at 17:20
  • $\begingroup$ So I guess proving that a) no draw is possible and b) every possible winning strategy for Bob can be mimicked by Alice (or Alice by Bob) would do? $\endgroup$ – VicAche Dec 12 '15 at 17:25
  • $\begingroup$ @VicAche I think the "strategy stealing" argument won't work here, for the same reason as in this question. $\endgroup$ – Sleafar Dec 12 '15 at 18:10
  • $\begingroup$ @Sleafar the problem might apply but it may still be easier using that than through brute-force. $\endgroup$ – VicAche Dec 13 '15 at 10:19

Alice wins.

Suppose for contradiction that Bob has a winning strategy.

Claim: If Alice makes the first move on square X, then on the next turn (Bob's), there is exactly one square Y among the neighbors of X on which Bob must make his (first) move to win.

Assuming the claim, for each square X, let f(X) denote the Y as in the claim. Then since there are more W squares than B, there must be two W squares $X_1,X_2$ and a B square Y such that $f(X_1)=f(X_2)=Y$.

Now this gives a strategy for Alice to win by starting at $Y$: if Bob places the knight on a square other than $X_1$, Alice steals Bob's strategy by pretending that Bob already made a move at $X_1$; if Bob places the knight on $X_1$, Alice pretends that the first move was Bob's at $X_2$ and again wins by strategy-stealing.

Proof of the claim:

Suppose for contradiction that Y, Z are two squares both adjacent to X and such that when Alice starts at X, then Bob has a winning strategy by placing his knight at Y or at Z.

Let Alice begin a game by placing the knight at Y. Now if Bob doesn't place the knight at X, then Alice can pretend to be the second-player where the game began with Bob starting at X; this is a contradiction so Bob must place the knight at X.

But in this case Alice can place the knight on Z and by strategy-stealing again, go on to win. This proves the claim.

  • 2
    $\begingroup$ In regards to the proof of claim, what if the winning strategies through Y and Z both end (or can be made to end) with a winning move back to X? Strategy-stealing would just end up with Alice moving to X and Bob winning on Y/Z. $\endgroup$ – Zandar Dec 13 '15 at 18:26
  • $\begingroup$ @Zandar, I don't understand. Since Y and Z are winning for Bob, how can the winning move finish at X? $\endgroup$ – Aravind Dec 13 '15 at 18:34
  • $\begingroup$ I mean the winning move in Bob's original strategy where Alice starts at X. If that winning move is back to X, then it no longer applies if Alice starts at Y or Z instead. $\endgroup$ – Zandar Dec 13 '15 at 18:40
  • $\begingroup$ This is very close! What I don't understand is, just before you start to prove the claim: It's true that if Alice starts on $X_2$ that Bob needs to move to $Y$. You say if the game starts $X_1, Y, X_2$ that Bob would need to move to $Y$ to win. But now the board is changed so that $Y$ has already been visited, maybe this opens another winning option for Bob? $\endgroup$ – Tyler Seacrest Dec 14 '15 at 16:02
  • $\begingroup$ @Zandar: I think the proof of the claim is okay. Imagine the board is colored like a chessboard with alternating black and white squares. If Alice starts at X and Bob ends up winning, then the winning move can't be X because (say) X is a black square, and whenever Bob moves he moves to white squares. $\endgroup$ – Tyler Seacrest Dec 14 '15 at 16:06

Your Answer

