Is chess a combinatorial game?

Yes, it is a combinatorial game as it is a two-player game, and the game is deterministic, which implies there is no luck or chance involved like a coin toss.

Can the Sprague grundy theorem be used to declare the winner in chess?

No, because the Sprague Grundy theorem is only used for impartial games, and chess is not an impartial game.

Table of contents

Introduction

Sprague Grundy Theorem

C++ Implementation

3.1.

Time Complexity

3.2.

Space Complexity

Frequently Asked Questions

Key Takeaways

Last Updated: Aug 13, 2025

Sprague Grundy Theorem

Author Yukti Kumari

Do you think IIT Guwahati certified course can help you in your career?

Yes

Introduction

In this article, we will learn Sprague Grundy Theorem which comes under the topic of Game Theory and questions based on game theory are quite frequent in competitive programming.

Why do we need game theory?
If I tell you that you can predict the winner of a game without even playing, then wouldn’t it be amazing. With the game theory concepts and theorem, we can determine this mathematically in combinatorial games.

Before stating a formal definition of the Sprague grundy theorem, I will introduce some terms which you need to know to understand the theorem.

Combinatorial games
The games in which there is no chance or luck involved and the outcome of winning or losing is deterministic are said to be combinatorial games. Now, since the outcome is deterministic, we can analyse these games mathematically. The players don’t play simultaneously, rather they play turn by turn. Examples can be chess, tic-tac-toe, checkers etc.

Chess Tic-Tac-Toe Checkers
Impartial Games
Impartial games are two-player games in which both the players play optimally and make moves in alternate turns. It is one of the types of combinatorial games. Additionally, the allowed moves for a player does not depend on the identity of the player but it just depends on the state of the game. The last player to move is the winner of the game.

For example, in chess, both the players are unique and have two different sets of pieces (black and white). So, they can only move those pieces which belong to them and not those of the opposite player. So, here the moves depend on the player’s identity, so it is not an impartial game. Next, Tic-tac-toe is also not an impartial game as the two players have different symbols (noughts and crosses).
One of the most famous examples of impartial games is Game of Nim.
MEX(Minimum Excluded)
For a set of non-negative integers, MEX is defined as the smallest non-negative value that does not belong to the set.
Example -
Grundy Numbers
A grundy number is used to define the entire game state. Every impartial game has a grundy number. Grundy number is equal to the MEX of all the possible states we can reach from the current state by the allowed moves. If the resultant grundy value is non-zero, then the current player wins; otherwise, the current player loses if it is zero.

For example, in the game of nim, if there are 4 coins initially in a pile, then we will find Grundy(4) to determine which player will win. In the game of nim, a player can remove 1 or 2 or 3 coins at a time.

Grundy(4) = MEX { Grundy(4-1), Grundy (4-2), Grundy(4-3) } = MEX{ Grundy(3), Grundy(2), Grundy(1) }

As you can see, we got a recursive relation. So, now we need to calculate Grundy(3), Grundy(2) and Grundy(1).
What is the base case of this recursion?
If, in the game of nim, the number of coins in a pile is zero initially, then it means the first player can’t move, and thus he loses while the second player wins. So, Grundy(0) is 0.

Grundy(1) = MEX{ Grundy(0) } = MEX{ 0 } = 1
Grundy(2) = MEX{Grundy(1) , Grundy(0) } = MEX{ 1, 0} = 2
Grundy(3) = MEX{Grundy(2), Grundy(1) , Grundy(0)} = MEX{2,1,0} = 3

So, Grundy(4) = MEX{ Grundy(3), Grundy(2), Grundy(1) } = MEX{ 3,2,1} = 0

Since Grundy(4) is zero so the first player will lose the game.

Now, if we modify the game of nim such that now instead of only one pile, we have N piles, how to determine the winner?

This is where we will use Sprague Grundy Theorem.

Sprague Grundy Theorem

The theorem states that in a composite game if the XOR of the grundy values of each of the sub-games is non-zero, the player starting first will win. And if the XOR value is zero, then the first player will lose.
Example - Consider three piles with 3, 4 and 5 coins in each pile, respectively.

Xor value = Grundy(3) xor Grundy(4) xor Grundy(5)
= 3 xor 0 xor 1
= 2

Since the xor value is non-zero, so the player who starts first will win the game.

Let’s see the code implementation in the next section.

C++ Implementation

/*C++ code to implement the Sprague Grundy theorem to find the
winner of impartial game*/

#include <bits/stdc++.h>
using namespace std;
#define firstPlayer 1
#define secondPlayer 2

// function to find MEX of a set
int calculateMex(unordered_set<int> s)
{
    int MEX = 0;
    while (s.find(MEX) != s.end())
        MEX++;

    return MEX;
}

// function to compute grundy number
int findGrundyNum(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;

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

    Grundy[n] = calculateMex(Set);

    return Grundy[n];
}

// function to declare the winner of the game
void findWinner(int turn, int piles[],
                int Grundy[], int n)
{
    int xor_Val = Grundy[piles[0]];

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

    if (xor_Val != 0)
    {
        if (turn == firstPlayer)
            printf("First player will win.\n");
        else
            printf("Second Player will win.\n");
    }
    else
    {
        if (turn == firstPlayer)
            printf("Second Player will win\n");
        else
            printf("First player will win\n");
    }

    return;
}

int main()
{
    int n = 3;
    int piles[n] = {3, 4, 5};

    // the maximum element from the array piles[]
    int maximum = *max_element(piles, piles + n);

    /*Array to store the grundy numbers*/
    int Grundy[maximum + 1];
    memset(Grundy, -1, sizeof(Grundy));

    /*calculate and store grundy value of piles[i]*/
    for (int i = 0; i <= n - 1; i++)
        findGrundyNum(piles[i], Grundy);

    findWinner(firstPlayer, piles, Grundy, n);
}

You can also try this code with Online C++ Compiler

Run Code

Output

First player will win.

Time Complexity

O(n^2), as for all the n piles, we find their grundy number and in the worst case, the complexity to find grundy number is O(n). Hence, the total complexity is O(n^2).

Space Complexity

O(n), as we use an array of size n to store the grundy number of each pile.

Frequently Asked Questions

Is chess a combinatorial game?
Yes, it is a combinatorial game as it is a two-player game, and the game is deterministic, which implies there is no luck or chance involved like a coin toss.
Can the Sprague grundy theorem be used to declare the winner in chess?
No, because the Sprague Grundy theorem is only used for impartial games, and chess is not an impartial game.

Key Takeaways

In this article, we learnt in detail about the key concepts in game theory like combinatorial games, MEX operation, impartial games, grundy numbers and finally, the Sprague Grundy theorem.

Follow up questions in Game theory that you can solve to make your understanding rock solid:

You can also consider our Competitive Programming Course to give your career an edge over others!

Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? Attempt our Online Mock Test Series on Coding Ninjas Studio now!