Game Theory For Competitive Programming

Game Theory is an interesting topic in Competitive Programming. It is great to read and ponder upon but is not that often asked in programming contests. Usually, problems come up revolving around this in short contests with a mixture of other topics like Range QueryingGreedy or Dynamic programming.

Very few Competitive Programmers are aware of Game Theory. The reason is lack of good resources on the internet about the Game Theory. But don’t worry, through this blog you will clear you’re all the doubts related to game theory.

This topic is more of an intuitive topic. I shall try my best to develop your intuition in the same.

Combinatorial Game Theory

Combinatorial games are two-person games with perfect information and no chance moves (no randomization like coin toss is involved that can affect the game). These games have a win-or-lose or tie outcome and determined by a set of positions, including an initial position, and the player whose turn is to move.

Player moves from one position to another, with the players usually alternating moves, until a terminal position is reached. A terminal position is one from which no moves are possible. Then one of the players is declared the winner and the other the loser, or there is a tie (Depending on the rules of the combinatorial game, the game could end up with a tie).

The only thing that can be stated about the combinatorial game is that the game should end at some point and should not be stuck in a loop. But one of the looping game is a game like chess

In order to prevent such looping situation in chess (consider the case of both the players just moving their queen’s to-and-fro from one place to the other), there is actually a “50-move rule” according to which the game is considered to be drawn if the last 50 moves by each player have been completed without the movement of any pawn and without any capture. Source: Stackexchange.

Especially the coding part of Combinatorial Game Theory (CGT) is relatively very small and easy. The key to the Game Theory problems is that hidden observation, which can be sometimes very hard to find.

Some of the following games those come under the category of Combinatorial Game Theory:

  1. Chess game.
  2. Tic-Tac-Toe.
  3. Game of Nim.

I know that you are very well aware of both the first and second games, but you are thinking about the third game.

What is this game?
How to play this game?

But don’t worry I will clear your all doubts later in this Blog. Let us leave that for now and move forward. We can divide combinatorial games into two categories as shown below:

Impartial Games:
In impartial Games, the possible moves from any position of the game are the same for the players.

Partisan Games:
In Partisan Games the possible moves from any position of the game are not the same for the players.

Let’s understand these Games (Impartial and Partisan) with an Example one by one.

1. Given a number of piles in which each pile contains some numbers of stones/coins. In each turn, the player chooses one pile and remove any number of stones (at least one) from that pile. The player who cannot move is considered to lose the game (i.e., one who takes the last stone is the winner).

As it can be clearly seen from the rules of the above game that the moves are the same for both the players. There is no restriction on one player over the other. Such a game is considered to be an impartial Game.

The above-mentioned game is famous by the name Game of Nim which will be discussed in detail later in this blog.

2. Let us take an example of Chess Game in this game, one player can only move the black pieces and the other one can only move the white ones. Thus, there is a restriction on both the players. Their set of moves are different and hence such a game is classified under the category of Partisan Games.

Partisan Games are much harder to analyze than Impartial Games as in such games we can’t use the Sprague-Grundy Theorem (will explain later in this blog).

Game of Nim (Nim-Game)

Now, we already know what is Game of Nim (given in the previous section).

Here, I will explain to you how to solve the problem of (Game of Nim) in the Competitive Programming.

Here, I will take an example, consider that there are two players- Alice and Bob, and initially there are three piles of coins having 3, 4, 5 coins in each of them as shown below. We assume that first move is made by A. See the below figure for the clear understanding of the whole gameplay.

Here, Both Alice and Bob are expert in this game, they will not do any mistake during the game.

In this game, we will take both scenarios, when Alice takes the first move or Bob takes the first move.

Alice makes the first move:

Here, Alice means A and Bob means B

Bob makes the first move:

Here, Alice means A and Bob means B

After seeing both figures, it must be clear that the game depends on one important factor – Who starts the game first?

Here, one question may come to your mind. Does the player who starts first will win every time?

 Let us again play the game, starting with Alice, and this time with a different initial configuration of piles.

The piles have 1, 4, 5 coins initially.

Will Alice win again as he has started first? Let us see.

Here, we can see in the figure, Alice has lost. But how? We know that this game depends heavily on which player starts first. Thus, there must be another factor which dominates the result of this simple-yet-interesting game. That factor is the initial configuration of the stones/piles. This time the initial configuration was different from the previous one.

So, we can conclude that this game depends on two factors:

  1. The player who starts first.
  2. The initial configuration of the piles/heaps.

But wait.  How to solve this problem, how to find the winner of this game, when this problem comes Competitive Programming.

In fact, we can predict the winner of the game before even playing the game! This helps the Competitive Programmer to solve this problem.

To solve this problem, we need to calculate the Nim sum.

Nim sum: The cumulative XOR value of the number of coins/stones in each pile/heaps at any point of the game is called Nim-Sum at that point.

“If both Alice and Bob play optimally (i.e.- they don’t make any mistakes), then the player starting first is guaranteed to win if the Nim-Sum at the beginning of the game is non-zero. Otherwise, if the Nim-Sum evaluates to zero, then player Alice will lose definitely.”

For the proof of the above theorem, see: Wikipedia

Let us apply the above theorem in the games played above. In the first game, Alice started first and the Nim-Sum at the beginning of the game was, 3 XOR 4 XOR 5 = 2, which is a non-zero value, and hence Alice won. Whereas in the second game-play, when the initial configuration of the piles was 1, 4, and 5 and Alice started first here Nim sum, 1 XOR 4 XOR 5 = 0, through the above theorem Alice will Lose the game.

C++ implementation of the above Theorem:

But Competitive Programming is not a sport for kids, in good programming contests, you will not find Game Theory problems as simple as above. To solve good problems, I will cover some important topics in Game Theory below.

(Grundy Numbers/Nimbers and Mex)

Grundy Number is a number that defines a state of a game. We can define any impartial game (example: nim game) in terms of Grundy Number.

Grundy Numbers or Nimbers determine how any Impartial Game (not only the Game of Nim) can be solved once we have calculated the Grundy Numbers associated with that game using Sprague-Grundy Theorem (will explain later in this blog).

But before calculating Grundy Numbers, we need to learn about another term- Mex.

What is Mex?
‘Minimum excludant’ also known as ‘Mex’ of a set of numbers is the smallest non-negative number not present in the set.

The Grundy Number/ number is equal to 0 for a game that is lost immediately by the first player and is equal to Mex of the numbers of all possible next positions for any other game.

Below are three example games and programs to calculate Grundy Number and Mex for each of them. Calculation of Grundy Numbers is done basically by a recursive function called as calculate_Grundy() function which uses calculate_Mex() function as its sub-routine.

Through these examples, you will able to know that how Grundy Numbers and Mex is helpful to solve the problems.

Example 1
The game starts with a pile of n stones, and the player to move may take any positive number of stones. Calculate the Grundy Numbers for this game. The last player to move wins. Which player wins the game?

Answer:
Since if the first player has 0(n=0) stone, he will lose immediately, so Grundy (0) = 0

 If a player has 1 stone, then he can take all the stones and win. So the next possible position of the game (for the other player) is (0) stones.

Hence, Grundy (1) = Mex (0) = 1 [According to the definition of Mex]

Similarly, if a player has 2 stones, then he can take only 1 stone or he can take all the stones and win. So the next possible position of the game (for the other player) is (1, 0) stones respectively.

Hence, Grundy (2) = Mex (0, 1) = 2 [According to the definition of Mex]

Similarly, if a player has ‘n’ stones, then he can take only 1 stone, or he can take 2 stones……. or he can take all the stones and win. So the next possible position of the game (for the other player) is (n-1, n-2,.1) stones respectively.

Hence, Grundy(n) = Mex (0, 1, 2, …. n-1) = n [According to the definition of Mex]

We summarize the first the Grundy Value from 0 to 10 in the below table:

Optimized Dynamic Programming Code in (C++):

Example 2:
The game starts with a pile of n stones, and the player to move may take any positive number of stones up to 3 only. The last player to move wins. Which player wins the game? This game is 1 pile version of Nim.

Answer:
Since if the first player has 0 stones, he will lose immediately, so Grundy (0) = 0

If a player has 1 stone, then he can take all the stones and win. So the next possible position of the game (for the other player) is (0) stone

Hence, Grundy (1) = Mex (0) = 1 [According to the definition of Mex]

Similarly, if a player has 2 stones, then he can take only 1 stone or he can take 2 stones and win. So the next possible position of the game (for the other player) is (1, 0) stones respectively.

Hence, Grundy (2) = Mex (0, 1) = 2 [According to the definition of Mex]

Similarly, Grundy (3) = Mex (0, 1, 2) = 3 [According to the definition of Mex]

But what about 4 stones?

If a player has 4 stones, then he can take 1 stone or he can take 2 stones or 3 stones, but he can’t take 4 stones (see the constraints of the game). So the next possible position of the game (for the other player) is (3, 2, 1) stones respectively.

Hence, Grundy (4) = Mex (1, 2, 3) = 0 [According to the definition of Mex]

So we can define Grundy Number of any n >= 4 recursively as-

Grundy(n) = Mex [Grundy (n-1), Grundy (n-2), Grundy (n-3)]

We summarize the first the Grundy Value from 0 to 10 in the below table-

Optimized Dynamic Programming Code in (C++):

Example 3:
The game starts with a number- ‘n’ and the player to move divides the number- ‘n’ with 2, 3 or 6 and then takes the floor. If the integer becomes 0, it is removed. The last player to move wins. Which player wins the game?

Answer:
Suppose, we take n=7, Now the first player can divide the n with (2,3 or 6).

If first player divide n by 2   n=floor(n/2), n=3

If first player divide n by 3   n=floor(n/2), n=2

If first player divide n by 6   n=floor(n/2), n=1

Then for the second player n could be 3,2 or 1.

So Grundy (7) =Mex (1,2,3) =0 [According to the definition of Mex]

We summarize the first the Grundy Value from 0 to 10 in the below table:

Optimized Dynamic Programming Code in (C++):

Above we have learned how to find Grundy Numbers through the examples. For solving tough problems, we have to learn (Sprague – Grundy Theorem).

Sprague – Grundy Theorem

Suppose there is a composite game (more than one sub-game) made up of N sub-games and two players, Alice and Bob. Then Sprague-Grundy Theorem says that if both Alice and Bob play optimally (i.e., they don’t make any mistakes), then the player starting first is guaranteed to win if the XOR of the Grundy numbers of position in each sub-games at the beginning of the game is non-zero. Otherwise, if the XOR evaluates to zero, then player A will lose definitely, no matter what.

How to apply Sprague Grundy Theorem?
We can apply the Sprague-Grundy Theorem in any impartial game and solve it. The basic steps are listed as follows:

  1. Break the composite game into sub-games.
  2. Then for each sub-game, calculate the Grundy Number at that position.
  3. Then calculate the XOR of all the calculated Grundy Numbers.
  4. If the XOR value is non-zero, then the player who is going to make the turn (First Player) will win else he is destined to lose, no matter what.

Now, we take an example and understand how to apply Sprague Grundy Theorem to find the winner, we will follow every four steps one by one.

Example:
The game starts with 3 piles having 3, 4 and 5 stones, and the player to move may take any positive number of stones up to 3 only from any of the piles [Provided that the pile has that much amount of stones]. The last player to move wins. Which player wins the game assuming that both players play optimally?

Answer:  we will follow each step.

First Step: The sub-games can be considered as each pile.

Second Step: We see from the below table that

We have already seen how to calculate the Grundy Numbers of this game above in this blog.

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

Third Step: The XOR of 3, 4, 5 = 2.

Fourth Step: Since XOR is a non-zero number, so we can say that the first player will win.

C++ program that implements above all four steps:

References: Wikipedia
I will explain to you one more very good Problem based on Nim-game, that will seriously boost your skill in Game Theory.

Example (composite game):
N x N chessboard with K knights on it. Unlike a knight in a traditional game of chess, these can move only as shown in the picture below (so the sum of coordinates is decreased in every move). There can be more than one knight on the same square at the same time. Two players take turns moving and when it is a player’s, turn he chooses one of the knights and moves it. A player who is not able to make a move is declared the loser.

Answer:
This is the same as if we had K chess boards with exactly one knight on every chessboard. This is the ordinary sum of K games and it can be solved by using the Grundy numbers. We assign Grundy number to every subgame according to which size of the pile in the Game of Nim it is equivalent to. When we know how to play Nim we will be able to play this game as well.

Here, Pseudocode for generating Grundy numbers for each position on the ChessBoard.

How to find the Grundy numbers in this game?
We use the same concept to find the Grundy Number as we did in the Game of Nim.

Grundy number(m) for each position on chess board:

Suppose you are calculating for the position x.

G(m)= Mex(G(X1), G(X2) …. G(xm))

Where m= {number of possible moves from position x of the knight}.

G(X1), G(X2), G(X3) …. and G(xm) are the Grundy Numbers for all the position where a knight can move from x. These Grundy numbers are already calculated by you.

The following table shows Grundy numbers for an 8 x 8 board:

A better approach is to compute Grundy numbers for an N X N chessboard in O(n^2) time and then XoR these K (one for every horse) values. If their xor is 0 then we are in a losing position, otherwise, we are in a winning position.

Why is the pile of Nim equivalent to the subgame if its size is equal to the Grundy number of that subgame?

  • If we decrease the size of the pile in Nim from A to B, we can move also in the sub-game to the position with the Grundy number B. (Our current position had Grundy number A so it means we could move to positions with all smaller Grundy numbers, otherwise the Grundy number of our position would not be A.)
  • If we are in the subgame at a position with a Grundy number higher than 0, by moving in it and decreasing its Grundy number we can also decrease the size of the pile in the Nim.
  • If we are in the subgame at the position with Grundy number 0, by moving from that we will get to a position with a Grundy number higher than 0. Because of that, from such a position it is possible to move back to 0. By doing that we can nullify every move from the position from Grundy number 0.

Other composite games:
It doesn’t happen often, but you can occasionally encounter games with a slightly different set of rules. For example, you might see the following changes:

Q. When it is a player’s move he can choose some of the horses (at least one) and move with all the chosen ones?
Solution: You are in a losing position if and only if every horse is in a losing position on his own chess board (so the Grundy number for every square, where the horse is, is 0).

Problems for Practice:

MMMGAME — M&M Game [SPOJ]

QCJ3 — The Game [SPOJ]

GAME3 — Yet Another Fancy Game [SPOJ]

GAME31 — The game of 31 [SPOJ]

Stone Game [CodeChef]

Advanced details in competitive programming, Check my GitHub repo:

Awesome-competitive-programming

Happy coding

 

You might also like More from author