Five coins on a 15x15 board

Question

[Note: this puzzle is derived from a coding contest question at HackerRank. The question is no longer in active use there. It was originally posted with content copied-and-pasted directly from there, but now it has been rewritten.]

Two players are playing a game on a 15x15 chessboard. There is only a single kind of piece; let's suppose they're using coins. The rules are:

• Players take turns.
• If (and only if) you can't move, then you immediately lose.
• A move consists of moving a coin by a "northwesterly" knight's move. That is, if we number the squares on the board in the "obvious" way with lower numbers to the north and east, you can move from $(x,y)$ to $(x-2,y\pm1)$ or $(x\pm1,y-2)$.
• You are not allowed to move a coin off the board.
• You are allowed to move one coin on top of another.

(So the game will end when all coins are in the top-left 2x2 region of the board, from which none of those moves can be made.)

If we begin with five coins at positions (15,4), (8,12), (14,14), (10,3), (1,15) -- in coordinates where the top left corner of the board is at (1,1) -- then who wins with best play on both sides? What should the first player do?

Answer 1

I assume that it's possible to put a coin on top of another coin. In this case,

we can apply the theory of so-called "impartial games". The game is the "sum" of five instances of the simpler game that uses just one coin; to play in a sum of games, you pick one of them and move in that. Every game-position has a non-negative integer value, sometimes called its "Nim-value"; it's equivalent in a certain sense to a game of Nim with one pile of that size. We can find Nim-values by what is sometimes called the "mex rule", short for "minimal excludant"; the value of a position is the smallest non-negative integer that isn't the value of any position you can move to.

Accordingly

we can compute those values incrementally, starting with positions from which there are no legal moves (i.e., the top-left 2x2 region of the board); these have value zero. (You can see this directly -- there are no legal moves from such a position, just as there are no legal moves from a Nim game with a single pile of size zero -- or via the "mex rule", since the smallest non-negative integer is zero.)

And

you can compute the value of a sum of game-positions by computing the values of the individual positions, and taking what computer people call their bitwise exclusive-or. In other words, write each as a sum of distinct powers of 2; put those all together; cancel out any pairs of equal powers of 2; and add up the rest.

What remains is mere calculation, so let's do it. ... Actually,

you can find the numbers already worked out on page 58 of volume 1 of Winning Ways, if you happen to have a copy. You may notice certain regularities in the table, which I have emphasized by adding some grid lines.

$$\begin{array}{r|rrrr|rrrr|rrrr|rrr} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 \\ \hline 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 \\ 2 & 0 & 0 & 2 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 \\ 3 & 1 & 2 & 2 & 2 & 3 & 2 & 2 & 2 & 3 & 2 & 2 & 2 & 3 & 2 & 2 \\ 4 & 1 & 1 & 2 & 1 & 4 & 3 & 2 & 3 & 3 & 3 & 2 & 3 & 3 & 3 & 2 \\ \hline 5 & 0 & 0 & 3 & 4 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 \\ 6 & 0 & 0 & 2 & 3 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 \\ 7 & 1 & 1 & 2 & 2 & 1 & 2 & 2 & 2 & 3 & 2 & 2 & 2 & 3 & 2 & 2 \\ 8 & 1 & 1 & 2 & 3 & 1 & 1 & 2 & 1 & 4 & 3 & 2 & 3 & 3 & 3 & 2 \\ \hline 9 & 0 & 0 & 3 & 3 & 0 & 0 & 3 & 4 & 0 & 0 & 1 & 1 & 0 & 0 & 1 \\ 10 & 0 & 0 & 2 & 3 & 0 & 0 & 2 & 3 & 0 & 0 & 2 & 1 & 0 & 0 & 1 \\ 11 & 1 & 1 & 2 & 2 & 1 & 1 & 2 & 2 & 1 & 2 & 2 & 2 & 3 & 2 & 2 \\ 12 & 1 & 1 & 2 & 3 & 1 & 1 & 2 & 3 & 1 & 1 & 2 & 1 & 4 & 3 & 2 \\ \hline 13 & 0 & 0 & 3 & 3 & 0 & 0 & 3 & 3 & 0 & 0 & 3 & 4 & 0 & 0 & 1 \\ 14 & 0 & 0 & 2 & 3 & 0 & 0 & 2 & 3 & 0 & 0 & 2 & 3 & 0 & 0 & 2 \\ 15 & 1 & 1 & 2 & 2 & 1 & 1 & 2 & 2 & 1 & 1 & 2 & 2 & 1 & 2 & 2 \\ \end{array}$$

Now, the initial positions are (15,4),(8,12),(14,14),(10,3),(1,15)

where we find the numbers 2, 3, 0, 2, 1 respectively. The Nim-sum or exclusive-or of these is 2, so this game (at a high enough level of abstraction!) plays like a Nim-heap of size 2. In particular, like a Nim-heap of size 2, this is a first-player win. The first player should move to 2,1,0,2,1 by moving the coin from (8,12) to (6,11).