A stone game - 2 players play perfectly

Question

Recently I have learned about the nim game and grundy number I am stuck on a problem. Please give me some ideas

Problem: A and B play a game with a pile of stone. A starts the game and they alternate moves. In each move, a player has to remove at least one and no more than sqrt of number stones from the pile. So, for example if a pile contains 10 stones, then a player can take 1,2,3 stones from the pile. Both A and B play perfectly. The player who cannot make a valid move loses. Now you are given the number of stone, you have to find the player who will win if both play optimally. Example

n=3 A win,

n=5 B win

n<=10^12

I can solve this problem with small number of stone by using Grundy number https://www.topcoder.com/community/data-science/data-science-tutorials/algorithm-games/?

grundy function is g(x) with x is the remain stones. call F(s) is set of number of remain stone that we can obtain from x stone. if s is a terminal position, g(s)=0

if s is not a terminal position, Let X = {g(t)| t in F(s)}. Then, grundy number of s is the smallest integer greater than or equal to 0 which is not in X.

for example x=10 so F(x)={9,8,7} by take 1,2 or 3 stones. (sqrt(10)<=3)

if g(n)>0 => the first player win

g(0)=0

g(1)=1

g(2)=0

g(3)=1

g(4)=2 ....

but this algorithm is to slow.

Thanks in advance.

Answer 1

I'm adding a second answer because my first answer provides the background theory without the optimization. But since OP clearly is looking for some optimization and for a very fast solution without a lot of recursion, I took my own advice:

Of course, the really fast way to do this is to do some more math and figure out some simple properties of n you can check that will determine whether or not it is a winner or a loser.

I'm going to use the terminology I defined there, so if this isn't making sense, read that answer! Specifically, n is the pile size, k is the number of stones to remove, n is a winner if there is a winning strategy for player A starting with a pile of size n and it is a loser otherwise. Let's start with the following key insight:

Most numbers are winners.

Why is this true? It isn't obvious for small numbers: 0 is a loser, 1 is a winner, 2 is a loser, 3 is a winner, so is 4, but 5 is a loser again. But for larger numbers, it becomes more obvious.

If some integer p is large and is a loser then p+1, p+2, ... p+k_m are all winners for some k_m that is around the size of sqrt(p). This is because once I find a loser, for any pile that isn't too much larger than that, I can remove a few stones to leave my opponent with that loser. The key is just determining what the largest valid value of k is, since k is defined in terms of the starting pile size n rather than the final pile size p.

So the question becomes, given some integer p, for which values of k is it true that k <= sqrt(n) where n = p+k. In other words, given p, what starting pile sizes n allow me to remove k and leave my opponent with p. Well, since n = p+k and the values are all nonnegative, we must have

k <= sqrt(n) = sqrt(p+k) ==> k^2 <= p + k ==> k^2 - k - p <= 0.

This is a quadratic equation in k for any fixed value of p. The endpoints of the solution set can be found using the quadratic formula:

k = (1 +- sqrt(1 + 4p))/2

So, the inequality is satisfied for values of k between (1-sqrt(1+4p))/2 and (1+sqrt(1+4p))/2. Of course, sqrt(1+4p) is at least sqrt(5) > 2, so the left endpoint is negative. So then k_m = floor((1+sqrt(1+4p))/2).

More importantly, I claim that the next loser after p is the number L = p + k_m + 1. Let's try to prove this:

Theorem: If p is a loser, then L = p + k_m + 1 is also a loser and every integer p < n < L is a winner.

Proof: We have already shown that every integer n in the interval [p+1, p+k_m] is a winner, so we only need to prove that L is a loser.

Suppose, to the contrary, that L is a winner. Then there exists some 1 <= k <= sqrt(L) such that L - k is a loser (by definition). Since we have proven that the integers p+1, ..., p+k_m are winners, we must have that L - k <= p since no number smaller than L and larger than p can be a loser. But this means that L <= p + k and so k satisfies the equation k <= sqrt(L) <= sqrt(p + k). We have already shown that solutions to the equation k <= sqrt(p + k) are no larger than (1+sqrt(1+4p))/2, so any integer solution must satisfy k <= k_m. But then L - k = p + k_m + 1 - k >= p + k_m + 1 - k_m = p + 1. This is a contradiction since p < L - k < L and we have already proved that there are no losers larger than p and smaller than L.

QED

The above theorem gives us a nice approach since we now know that winners fall into intervals of integers separated by a single loser and we know how to calculate the interval between two losers. In particular, if p is a loser, then p + k_m + 1 is a loser where

k_m = floor((1+sqrt(1+4p))/2).

Now we can rewrite the function in a purely iterative manner that should be fast and requires constant space. The approach is simply to compute the sequence of losers until we either find n (in which case it is a loser) or determine that n lies in the interval between two losers.

bool is_winner(int n) {
  int p = 0;
  // loop through losers until we find one at least as large as n
  while (p < n) {
    int km = floor((1+sqrt(1+4p))/2);
    p = p + km + 1;
  }

  /* if we skipped n while computing losers, 
   * it is a winner that lies in the interval 
   * between two losers. So n is a winner as 
   * long as it isn't equal to p.*/
  return (p != n);  
}