A game with multiple stones on a board (Combinatorial Game)

Question

We have a game here. The game is played on a $10x10$ board. Here are the rules:

• Stones are placed on these squares as in the picture below.
• We have two players with alternating moves.
• As a legal move, we can move any stone by leftward, downward, and downward diagonal to any square. (Moves can be of any length greater than or equal to 1). Each stone has a role similar to that of a chess queen
• In any square, there can be any number of stones.
• At each turn, only one stone is allowed to move.
• Once all the stones are placed in the square located at the bottom left corner of the table, the game finishes.
• The one who plays the last legal move loses the game (misère convention).

Now we are asked to show the position above is a Normal position. And we are asked to find the all possible winning moves. Here is my attempt:

Edit: This initial attempt was WRONG as this is not a Normal game but a Misére one. So, I fixed this:

I know that I cannot continue forever by labeling as this.The game is more complex than it looks. I am open to any suggestions. Well, perhaps using Sprague-Grundy function can be useful but I don't know how to make use of it. Thanks in advance.

Normal Position (N-position): They are the positions which are winning for the Next player to move. Previous Position (P-position): Positions that are winning for the Previous player (the player who just moved):

So, the player aiming to win tries to make a move that puts the next player in a P-position.

Answer 1

Your game is known as the misere variatnnt Wythoff's game. In general, the Sprague-Grundy theorem does not hold for misere games, meaning you cannot always replace misere games in a sum by equivalent nim heaps. However, this is true for a subclass of games called tame games. According to Winning Ways, vol 2, page $427$, the positions of Wythoff's game are indeed tame.

There is no simple rule to determine the normal nim value of a Wythoff's game position, but we can calculate them recursively. Below are the results according to Winning Ways. Here, $n$ is an abbreviation for the firm genus $n^n$ (see Winning Ways vol 2 p. 413 and on for the definitions of these terms and the theory behind them). Using this, we solve this using Jorge's reasoning in a deleted answer. Namely, the position is equivalent to the misere-nim position

$$ 9\oplus5\oplus5\oplus5\oplus8\oplus4\oplus4\oplus11\oplus11\oplus16=9\oplus5\oplus8\oplus16=20 $$ This is nonzero, so we are looking at an $N$-position. Since all summands are firm, the winning move is to one where the nim sum of the normal-play Grundy values is zero. Since there are no options with a summand of $16$, the winning move must be to replace $16$ with $4$, so the unique winning move is to move the upper right counter diagonally one space.

$$\text{Genera for Wythoff's game}\\\begin{array}{|c|c|c|c|c|c|c|c|c|c|} \hline 9 & 10 & 11 & 12 & 8 & 7 & 13 & 14 & 15 & 16 \\ \hline 8 & 6 & 7 & 10 & 1 & 2 & 5 & 3 & 4 & 15 \\ \hline 7 & 8 & 6 & 9 & 0 & 1 & 4 & 5 & 3 & 14 \\ \hline 6 & 7 & 8 & 1 & 9 & 10 & 3 & 4 & 5 & 13 \\ \hline 5 & 3 & 4 & 0 & 6 & 8 & 10 & 1 & 2 & 7 \\ \hline 4 & 5 & 3 & 2 & 7 & 6 & 9 & 0 & 1 & 8 \\ \hline 3 & 4 & 5 & 6 & 2 & 0 & 1 & 9 & 10 & 12 \\ \hline 2 & 0^1 & 1^0 & 5 & 3 & 4 & 8 & 6 & 7 & 11 \\ \hline 1^0 & 2 & 0^1 & 4 & 5 & 3 & 7 & 8 & 6 & 10 \\ \hline 0^1 & 1^0 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline \end{array}$$

Answer 2

I'll just leave here as code to calculate the grundy values, which are an intermediate step to get the genus. See Mike's solution to see why this is useful for the actual problem ( I initially didn't see it was misere)

#include <bits/stdc++.h>
using namespace std;

const int n = 10;
int S[n][n];

int main(){
        cout << "$\\begin{array}{|c|c|c|c|c|c|c|c|c|c|}" << endl;
  cout << "\\hline" << endl;
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      map<int,int> M;
      if( i == 0  && j == 0) continue;
      for(int d=1; ;d++){
        if( i - d < 0) break;
        M[ S[i-d][j]]++;
      }
      for(int d=1; ;d++){
        if( j - d < 0) break;
        M[ S[i][j-d]]++;
      }
      for(int d=1; ;d++){
        if( i - d < 0 || j-d < 0) break;
        M[ S[i-d][j-d]]++;
      }
      for(int x=0; ;x++){
        if( M[x] == 0){
          S[i][j] = x;
          break;
        }
      }
    }
  }
  for(int i=n-1;i>=0;i--){
    for(int j=0;j<n;j++){
      cout   << S[i][j] << " ";
      if( j == n-1) cout << "\\\\ \\hline" << endl;
      else cout << "& ";
    }
  }
  cout << "\\end{array}$" << endl;
}

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

Answer 3

I have converted my comment about single stone strategy to an image

I assume here an empty board with a single stone in one of the $99$ cells excepted $(0,0)$.

I coloured in red losing starting position and in green the winning positions, assuming of course both players play an optimal strategy.

• If the stone is in $(0,1)$ or $(1,0)$ [red cells with index $1$] then I'm forced to move to $(0,0)$ and lose the game.

• If the stone is in one of the green cells with index $2$ then since the move can be any length, I can move it to either $(1,0)$ or $(0,1)$ and my opponent loses.

• If the stone is in red $3$ then legal moves lead only to green cells and next turn my opponent is winning, or to $(0,0)$ I lose directly. Either way, this cell is losing.

• And I extend the board recursively like this. Note that from red cells you can only reach green cells therefore this is a losing position. And green cells $n$ can always reach red cell $n-1$ on the next move, so it is a winning position.

This is how I understand the rules for just $1$ stone, and any length move in direction $\leftarrow,\downarrow,\swarrow$.