Before we get into the SG function and the SG theorem let’s introduce the winning points and the losing points.

Concepts of winning points and losing points:

Point P: the losing point, in other words, whoever is in this position will lose if both parties do the right thing.

N point: the winning point. In this case, both sides must win if their operations are correct.

The nature of winning points and losing points:

1. All endpoints are defeat point P. (We reason from this base premise, in other words, we assume from it.)

2. From any winning point N, there is at least one way to enter losing point P.

3, no matter how to operate, the losing point P can only enter the winning point N.

We study the goal time of the winning point and the losing point to simplify the topic, which is helpful to our analysis. We usually analyze the winning points and the losing points in reverse order of the endpoints. We started with HDU 1847 Good Luck in CET-4 Everybody! For example:

When n = 0, it’s obviously a fail-safe point, because you can’t do anything anymore

When n = 1, because you can pick up all the cards at once, that’s the winning point

When n = 2, also can be taken in one time, so when is the winning point

When n is equal to 3, there’s either one card left or two cards left, and either way they’re going to face the winning point, so this is the losing point.

And so on and so forth, and you end up with;

N: 0 1 2 3 4 5 6…

Position: P N N P N P…

Did you see anything? Yeah, they just did it in a regular way, using P/N to analyze it, did it make the problem easier?

Now for a slightly more complicated one: HDU 2147 Kiki’s Game

Now let’s introduce today’s protagonist. Composing the sum of games is often complex, but there is a new tool that makes composing problems simple ————SG functions and SG theorems.

Sprague-grundy theorem (SG theorem) :

The SG function of the game sum is equal to the Nim sum of the SG functions of each game. This makes it easier to divide and conquer each subgame. The Bouton theorem is the direct application of Sprague-Grundy theorem in Nim games, because SG(x) = x of a single heap of Nim games. The game is not very clear, please refer to http://www.cnblogs.com/ECJTUACM-873284962/p/6398385.html for further understanding.

SG function:

First define mex(minimal excludant), which is an operation imposed on a set to represent the smallest non-negative integers that do not belong to the set. For example, mex{0,1,2,4}=3, mex{2,3,5}=0, mex{}=0.

For any state x, define SG(x) = mex(S), where S is the set of SG function values for the succeeding states of X. There are three subsequent state such as x SG (a), respectively, SG (b), the SG (c), the SG (x) = tex-mex {SG (a), the SG (b), SG (c)}. Thus the final state of the set S must be empty, so the final state of the SG function is SG(x) = 0, if and only if x is the defeatable point P.

[Example] The problem of taking stones

If there is a pile of n stones, only {1, 3, 4} stones can be taken at a time. The one who takes all stones first wins. What is the SG value of each number?

SG [0] = 0 f [] = {1, 4},

SG[1] = mex{SG[0]}= mex{0} =1; SG[1] = mex{0} =1; SG[1] = mex{0} =1;

SG[2] = mex{SG[1]}= mex{1} = 0; SG[2] = mex{1} = 0; SG[2] = mex{1} = 0;

X = 3, you can take 3 – f {1, 3} a pebble, {2, 0} a rest, so SG [3] = tex-mex {SG [2], SG [0]} = tex-mex {0, 0} = 1;

X = 4, you can take 4 – f {4} 1 a pebble, remaining {0} 3 a, so the SG [4] = tex-mex {SG SG [3], [1], SG [0]} = tex-mex {0} 1 = 2;

X = 5, you can take 5 – f {4} 1 a pebble, remaining {4, 2, 1}, so SG [5] = tex-mex {SG [4], SG [2], SG [1]} = tex-mex {2, 1} = 3;

And so on…..

   x        0  1  2  3  4  5  6  7  8….

SG[x]    0  1  0  1  2  3  2  0  1….

From the above examples, we can obtain the steps for calculating the SG function value. Then, the steps for calculating the SG function value of 1~n are as follows:

1. Use the array f to record how the current state can be changed.

2. We then use another array to mark the successor states of the current state X.

3. Finally, simulate mex operation, that is, we search the minimum value of unmarked value in the marked value and assign it to SG(x).

4. By repeating steps 2-3, we have completed the calculation of the function values from 1 to n.

The code implementation is as follows:

2 //SG[]: SG function value from 0 to N 3 //S[]: set of x subsequent states 4 int f[N],SG[MAXN],S[MAXN]; 4 int f[N],SG[MAXN]; 5 void getSG(int n){ 6 int i,j; 7 memset(SG,0,sizeof(SG)); 8 // Because SG[0] is always equal to 0, so I start at 1 9 for(I = 1; i <= n; I++){10 memset(S,0,sizeof(S)); 12 for(j = 0; f[j] <= i && j <= N; j++) 13 S[SG[i-f[j]]] = 1; For (j = 0; j++) if(! S[j]){// select * from SG[I] = j; 16 break; 17} 18} 19}Copy the code

Now let’s have a practical exercise:

As long as the above ideas, to solve this is a minute problem.

The code is as follows:

1 #include <stdio.h> 2 #include <string.h> 3 #define MAXN 1000 + 10 4 #define N 20 5 int f[N],SG[MAXN],S[MAXN]; 6 void getSG(int n){ 7 int i,j; 8 memset(SG,0,sizeof(SG)); 9 for(i = 1; i <= n; i++){ 10 memset(S,0,sizeof(S)); 11 for(j = 0; f[j] <= i && j <= N; j++) 12 S[SG[i-f[j]]] = 1; 13 for(j = 0;; j++) if(! S[j]){ 14 SG[i] = j; 15 break; 16 } 17 } 18 } 19 int main(){ 20 int n,m,k; 21 f[0] = f[1] = 1; 22 for(int i = 2; i <= 16; i++) 23 f[i] = f[i-1] + f[i-2]; 24 getSG(1000); 25 while(scanf("%d%d%d",&m,&n,&k),m||n||k){ 26 if(SG[n]^SG[m]^SG[k]) printf("Fibo\n"); 27 else printf("Nacci\n"); 28 } 29 return 0; 30}Copy the code

If you haven’t had enough, I’m going to give you some combinatorial games:

POJ 2234 Matches Game

HOJ 4388 Stone Game II\

POJ 2975 Nim HOJ 1367 A Stone Game POJ 2505 A multi Game ZJU 3057 Beans Game POJ 1067 Play A Funny POJ 2484 A Funny Game POJ 2425 A Chess Game POJ 2960 S-Nim POJ 1704 Georgia and Bob POJ 1740 A New Stone Game POJ 2068 Nim POJ 3480 John POJ 2348 Euclid’s Game HOJ 2645 WNim POJ 3710 Christmas Game POJ 3533 Light Switching Game