10

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?

f''
  • 33,665
  • 4
  • 120
  • 165
Tyler Seacrest
  • 9,174
  • 2
  • 28
  • 62
  • 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
  • @VicAche Actually it's pretty simple to brute force (especially having a half of the code already). I know the solution but I have (once again) no idea how to explain it. – Sleafar Dec 13 '15 at 10:22
  • @Sleafar I meant hand-bruteforcing. I think it's very uneleguant to use a computer to solve a chess problem. – VicAche Dec 13 '15 at 10:24
  • There being one W square more than B, it is likely that Alice should win by placing a knight on the W square in the bottom row that completes symmetry. – Aravind Dec 13 '15 at 15:30

1 Answers1

4

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.

Aravind
  • 1,718
  • 1
  • 14
  • 17
  • 2
    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
  • @TylerSeacrest, you are right. I changed Alice's strategy by starting at Y and it seems to work. – Aravind Dec 14 '15 at 17:31
  • I think you can expand on why "then Alice can pretend to be the second-play where the game began with Bob starting at X" is a contradiction, by saying, "because the result is the same as when Alice make a winning move from X to Y in the previous move, which, being a winning move by stealing Bob's strategy, should end in Alice's win". And perhaps also add what Tyler said in the comment on black-white squares argument. I was initially confused as how is that a contradiction. Otherwise, seems correct to me! – justhalf Dec 14 '15 at 22:09
  • Assuming winning condition was inverted and there were only tiles a1, b3, c2, d4; no matter which square is picked by A, B has 2 winning moves. Strategy stealing does not work. Besides, in the linked question on another similar game, B wins on 8x8 while A wins on 6x6. So, I don't think this really proves anything. – Zizy Archer Mar 12 '21 at 22:10