0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Are you sure your movement diagram is correct? Your sample coin moves appear to have their y values inverted. $\endgroup$ – Reibello Feb 10 '17 at 21:58
  • $\begingroup$ yeah they are correct $\endgroup$ – akhilesh Feb 10 '17 at 22:05
  • $\begingroup$ I'm not seeing it. I'm also not convinced it changes the answer though. Assuming X to be horizontal & Y vertical - since Y increases moving down: your sample moves appear to be (in clockwise order) (x-2,y+1), (x-2,y-1), (x-1,y-2), (x+1,y-2). $\endgroup$ – Reibello Feb 10 '17 at 22:08
  • $\begingroup$ I think Reibello is right. $\endgroup$ – Gareth McCaughan Feb 10 '17 at 22:10
  • 1
    $\begingroup$ See meta.puzzling.stackexchange.com/questions/1348/… for the SE policy on copying other people's stuff without acknowledgement. I'm not sure whether at this point a combination of (1) saying where it came from and (2) rewording it (and losing the diagram stolen from them) would solve the problem, or whether this just has to be deleted now. $\endgroup$ – Gareth McCaughan Feb 10 '17 at 22:31
6
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ can you put the answer whether its player 1 or 2 $\endgroup$ – akhilesh Feb 10 '17 at 22:15
  • $\begingroup$ I'm working on it! $\endgroup$ – Gareth McCaughan Feb 10 '17 at 22:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.