# 组合博弈论 4（Sprague – Grundy定理）

2021年3月11日17:51:07 发表评论 632 次浏览

## 本文概述

1. 将复合游戏分为子游戏。
2. 然后, 对于每个子游戏, 计算该位置的脏号码。
3. 然后计算所有计算出的脏数的异或。
4. 如果XOR值不为零, 那么将要转牌的玩家(第一个玩家)将获胜, 否则他注定会失败。

``````Grundy(3) = 3
Grundy(4) = 0
Grundy(5) = 1``````

3, 0, 1 = 2的XOR

## C ++

``````/*  Game Description-
"A game is played between two players and there are N piles
of stones such that each pile has certain number of stones.
On his/her turn, a player selects a pile and can take any
non-zero number of stones upto 3 (i.e- 1, 2, 3)
The player who cannot move is considered to lose the game
(i.e., one who take the last stone is the winner).
Can you find which player wins the game if both players play
optimally (they don't make any mistake)? "

A Dynamic Programming approach to calculate Grundy Number
and Mex and find the Winner using Sprague - Grundy Theorem. */

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

/* piles[] -> Array having the initial count of stones/coins
in each piles before the game has started.
n       -> Number of piles

Grundy[] -> Array having the Grundy Number corresponding to
the initial position of each piles in the game

The piles[] and Grundy[] are having 0-based indexing*/

#define PLAYER1 1
#define PLAYER2 2

// A Function to calculate Mex of all the values in that set
int calculateMex(unordered_set< int > Set)
{
int Mex = 0;

while (Set.find(Mex) != Set.end())
Mex++;

return (Mex);
}

// A function to Compute Grundy Number of 'n'
int calculateGrundy( int n, int Grundy[])
{
Grundy[0] = 0;
Grundy[1] = 1;
Grundy[2] = 2;
Grundy[3] = 3;

if (Grundy[n] != -1)
return (Grundy[n]);

unordered_set< int > Set; // A Hash Table

for ( int i=1; i<=3; i++)
Set.insert (calculateGrundy (n-i, Grundy));

// Store the result
Grundy[n] = calculateMex (Set);

return (Grundy[n]);
}

// A function to declare the winner of the game
void declareWinner( int whoseTurn, int piles[], int Grundy[], int n)
{
int xorValue = Grundy[piles[0]];

for ( int i=1; i<=n-1; i++)
xorValue = xorValue ^ Grundy[piles[i]];

if (xorValue != 0)
{
if (whoseTurn == PLAYER1)
printf ( "Player 1 will win\n" );
else
printf ( "Player 2 will win\n" );
}
else
{
if (whoseTurn == PLAYER1)
printf ( "Player 2 will win\n" );
else
printf ( "Player 1 will win\n" );
}

return ;
}

// Driver program to test above functions
int main()
{
// Test Case 1
int piles[] = {3, 4, 5};
int n = sizeof (piles)/ sizeof (piles[0]);

// Find the maximum element
int maximum = *max_element(piles, piles + n);

// An array to cache the sub-problems so that
// re-computation of same sub-problems is avoided
int Grundy[maximum + 1];
memset (Grundy, -1, sizeof (Grundy));

// Calculate Grundy Value of piles[i] and store it
for ( int i=0; i<=n-1; i++)
calculateGrundy(piles[i], Grundy);

declareWinner(PLAYER1, piles, Grundy, n);

/* Test Case 2
int piles[] = {3, 8, 2};
int n = sizeof(piles)/sizeof(piles[0]);

int maximum = *max_element (piles, piles + n);

// An array to cache the sub-problems so that
// re-computation of same sub-problems is avoided
int Grundy [maximum + 1];
memset(Grundy, -1, sizeof (Grundy));

// Calculate Grundy Value of piles[i] and store it
for (int i=0; i<=n-1; i++)
calculateGrundy(piles[i], Grundy);

declareWinner(PLAYER2, piles, Grundy, n);   */

return (0);
}``````

## Java

``````import java.util.*;

/* Game Description-
"A game is played between two players and there are N piles
of stones such that each pile has certain number of stones.
On his/her turn, a player selects a pile and can take any
non-zero number of stones upto 3 (i.e- 1, 2, 3)
The player who cannot move is considered to lose the game
(i.e., one who take the last stone is the winner).
Can you find which player wins the game if both players play
optimally (they don't make any mistake)? "

A Dynamic Programming approach to calculate Grundy Number
and Mex and find the Winner using Sprague - Grundy Theorem. */

class GFG {

/* piles[] -> Array having the initial count of stones/coins
in each piles before the game has started.
n     -> Number of piles

Grundy[] -> Array having the Grundy Number corresponding to
the initial position of each piles in the game

The piles[] and Grundy[] are having 0-based indexing*/

static int PLAYER1 = 1 ;
static int PLAYER2 = 2 ;

// A Function to calculate Mex of all the values in that set
static int calculateMex(HashSet<Integer> Set)
{
int Mex = 0 ;

while (Set.contains(Mex))
Mex++;

return (Mex);
}

// A function to Compute Grundy Number of 'n'
static int calculateGrundy( int n, int Grundy[])
{
Grundy[ 0 ] = 0 ;
Grundy[ 1 ] = 1 ;
Grundy[ 2 ] = 2 ;
Grundy[ 3 ] = 3 ;

if (Grundy[n] != - 1 )
return (Grundy[n]);

// A Hash Table
HashSet<Integer> Set = new HashSet<Integer>();

for ( int i = 1 ; i <= 3 ; i++)

// Store the result
Grundy[n] = calculateMex (Set);

return (Grundy[n]);
}

// A function to declare the winner of the game
static void declareWinner( int whoseTurn, int piles[], int Grundy[], int n)
{
int xorValue = Grundy[piles[ 0 ]];

for ( int i = 1 ; i <= n - 1 ; i++)
xorValue = xorValue ^ Grundy[piles[i]];

if (xorValue != 0 )
{
if (whoseTurn == PLAYER1)
System.out.printf( "Player 1 will win\n" );
else
System.out.printf( "Player 2 will win\n" );
}
else
{
if (whoseTurn == PLAYER1)
System.out.printf( "Player 2 will win\n" );
else
System.out.printf( "Player 1 will win\n" );
}

return ;
}

// Driver code
public static void main(String[] args)
{

// Test Case 1
int piles[] = { 3 , 4 , 5 };
int n = piles.length;

// Find the maximum element
int maximum = Arrays.stream(piles).max().getAsInt();

// An array to cache the sub-problems so that
// re-computation of same sub-problems is avoided
int Grundy[] = new int [maximum + 1 ];
Arrays.fill(Grundy, - 1 );

// Calculate Grundy Value of piles[i] and store it
for ( int i = 0 ; i <= n - 1 ; i++)
calculateGrundy(piles[i], Grundy);

declareWinner(PLAYER1, piles, Grundy, n);

/* Test Case 2
int piles[] = {3, 8, 2};
int n = sizeof(piles)/sizeof(piles[0]);

int maximum = *max_element (piles, piles + n);

// An array to cache the sub-problems so that
// re-computation of same sub-problems is avoided
int Grundy [maximum + 1];
memset(Grundy, -1, sizeof (Grundy));

// Calculate Grundy Value of piles[i] and store it
for (int i=0; i<=n-1; i++)
calculateGrundy(piles[i], Grundy);

declareWinner(PLAYER2, piles, Grundy, n); */

}
}

// This code is contributed by PrinciRaj1992``````

## Python3

``````'''  Game Description-
"A game is played between two players and there are N piles
of stones such that each pile has certain number of stones.
On his/her turn, a player selects a pile and can take any
non-zero number of stones upto 3 (i.e- 1, 2, 3)
The player who cannot move is considered to lose the game
(i.e., one who take the last stone is the winner).
Can you find which player wins the game if both players play
optimally (they don't make any mistake)? "

A Dynamic Programming approach to calculate Grundy Number
and Mex and find the Winner using Sprague - Grundy Theorem.

piles[] -> Array having the initial count of stones/coins
in each piles before the game has started.
n       -> Number of piles

Grundy[] -> Array having the Grundy Number corresponding to
the initial position of each piles in the game

The piles[] and Grundy[] are having 0-based indexing'''

PLAYER1 = 1
PLAYER2 = 2

# A Function to calculate Mex of all
# the values in that set
def calculateMex( Set ):

Mex = 0 ;

while (Mex in Set ):
Mex + = 1

return (Mex)

# A function to Compute Grundy Number of 'n'
def calculateGrundy(n, Grundy):

Grundy[ 0 ] = 0
Grundy[ 1 ] = 1
Grundy[ 2 ] = 2
Grundy[ 3 ] = 3

if (Grundy[n] ! = - 1 ):
return (Grundy[n])

# A Hash Table
Set = set ()

for i in range ( 1 , 4 ):

# Store the result
Grundy[n] = calculateMex( Set )

return (Grundy[n])

# A function to declare the winner of the game
def declareWinner(whoseTurn, piles, Grundy, n):

xorValue = Grundy[piles[ 0 ]];

for i in range ( 1 , n):
xorValue = (xorValue ^
Grundy[piles[i]])

if (xorValue ! = 0 ):

if (whoseTurn = = PLAYER1):
print ( "Player 1 will win\n" );
else :
print ( "Player 2 will win\n" );
else :

if (whoseTurn = = PLAYER1):
print ( "Player 2 will win\n" );
else :
print ( "Player 1 will win\n" );

# Driver code
if __name__ = = "__main__" :

# Test Case 1
piles = [ 3 , 4 , 5 ]
n = len (piles)

# Find the maximum element
maximum = max (piles)

# An array to cache the sub-problems so that
# re-computation of same sub-problems is avoided
Grundy = [ - 1 for i in range (maximum + 1 )];

# Calculate Grundy Value of piles[i] and store it
for i in range (n):
calculateGrundy(piles[i], Grundy);

declareWinner(PLAYER1, piles, Grundy, n);

''' Test Case 2
int piles[] = {3, 8, 2};
int n = sizeof(piles)/sizeof(piles[0]);

int maximum = *max_element (piles, piles + n);

// An array to cache the sub-problems so that
// re-computation of same sub-problems is avoided
int Grundy [maximum + 1];
memset(Grundy, -1, sizeof (Grundy));

// Calculate Grundy Value of piles[i] and store it
for (int i=0; i<=n-1; i++)
calculateGrundy(piles[i], Grundy);

declareWinner(PLAYER2, piles, Grundy, n);   '''

# This code is contributed by rutvik_56``````

## C#

``````using System;
using System.Linq;
using System.Collections.Generic;

/* Game Description-
"A game is played between two players and there are N piles
of stones such that each pile has certain number of stones.
On his/her turn, a player selects a pile and can take any
non-zero number of stones upto 3 (i.e- 1, 2, 3)
The player who cannot move is considered to lose the game
(i.e., one who take the last stone is the winner).
Can you find which player wins the game if both players play
optimally (they don't make any mistake)? "

A Dynamic Programming approach to calculate Grundy Number
and Mex and find the Winner using Sprague - Grundy Theorem. */

class GFG
{

/* piles[] -> Array having the initial count of stones/coins
in each piles before the game has started.
n -> Number of piles

Grundy[] -> Array having the Grundy Number corresponding to
the initial position of each piles in the game

The piles[] and Grundy[] are having 0-based indexing*/

static int PLAYER1 = 1;
//static int PLAYER2 = 2;

// A Function to calculate Mex of all the values in that set
static int calculateMex(HashSet< int > Set)
{
int Mex = 0;

while (Set.Contains(Mex))
Mex++;

return (Mex);
}

// A function to Compute Grundy Number of 'n'
static int calculateGrundy( int n, int []Grundy)
{
Grundy[0] = 0;
Grundy[1] = 1;
Grundy[2] = 2;
Grundy[3] = 3;

if (Grundy[n] != -1)
return (Grundy[n]);

// A Hash Table
HashSet< int > Set = new HashSet< int >();

for ( int i = 1; i <= 3; i++)

// Store the result
Grundy[n] = calculateMex (Set);

return (Grundy[n]);
}

// A function to declare the winner of the game
static void declareWinner( int whoseTurn, int []piles, int []Grundy, int n)
{
int xorValue = Grundy[piles[0]];

for ( int i = 1; i <= n - 1; i++)
xorValue = xorValue ^ Grundy[piles[i]];

if (xorValue != 0)
{
if (whoseTurn == PLAYER1)
Console.Write( "Player 1 will win\n" );
else
Console.Write( "Player 2 will win\n" );
}
else
{
if (whoseTurn == PLAYER1)
Console.Write( "Player 2 will win\n" );
else
Console.Write( "Player 1 will win\n" );
}

return ;
}

// Driver code
static void Main()
{

// Test Case 1
int []piles = {3, 4, 5};
int n = piles.Length;

// Find the maximum element
int maximum = piles.Max();

// An array to cache the sub-problems so that
// re-computation of same sub-problems is avoided
int []Grundy = new int [maximum + 1];
Array.Fill(Grundy, -1);

// Calculate Grundy Value of piles[i] and store it
for ( int i = 0; i <= n - 1; i++)
calculateGrundy(piles[i], Grundy);

declareWinner(PLAYER1, piles, Grundy, n);

/* Test Case 2
int piles[] = {3, 8, 2};
int n = sizeof(piles)/sizeof(piles[0]);

int maximum = *max_element (piles, piles + n);

// An array to cache the sub-problems so that
// re-computation of same sub-problems is avoided
int Grundy [maximum + 1];
memset(Grundy, -1, sizeof (Grundy));

// Calculate Grundy Value of piles[i] and store it
for (int i=0; i<=n-1; i++)
calculateGrundy(piles[i], Grundy);

declareWinner(PLAYER2, piles, Grundy, n); */

}
}

// This code is contributed by mits``````

``Player 1 will win``

https://en.wikipedia.org/wiki/Sprague%E2%80%93Grundy_theorem

"一场比赛是由两名玩家使用N个整数A1, A2, .., AN进行的。在回合中, 玩家选择一个整数, 将其除以2、3或6, 然后发言。如果整数变为0, 则将其删除。最后一个移动的玩家获胜。如果双方都发挥最佳状态, 哪个玩家会赢得比赛？"

。如果你喜欢lsbin并希望做出贡献, 那么你也可以写一篇文章并将你的文章邮寄到contribution@lsbin.org。查看你的文章出现在lsbin主页上, 并帮助其他Geeks。