# Let's revisit this later (a two player knight's game)

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

• 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?

• Do we need to provide a winning strategy or is a proof enough? – VicAche Dec 12 '15 at 12:08
• I'm expecting a proof without any specific winning strategy. – Tyler Seacrest Dec 12 '15 at 17:20
• 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? – VicAche Dec 12 '15 at 17:25
• @VicAche I think the "strategy stealing" argument won't work here, for the same reason as in this question. – Sleafar Dec 12 '15 at 18:10
• @Sleafar the problem might apply but it may still be easier using that than through brute-force. – 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.

• 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. – Zandar Dec 13 '15 at 18:26
• @Zandar, I don't understand. Since Y and Z are winning for Bob, how can the winning move finish at X? – Aravind Dec 13 '15 at 18:34
• 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. – Zandar Dec 13 '15 at 18:40
• 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? – Tyler Seacrest Dec 14 '15 at 16:02
• @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. – Tyler Seacrest Dec 14 '15 at 16:06