Has Not Appeared
 0/16

Game Theory

Authors: Benjamin Qi, Mihnea Brebenel

Contributor: Salma J

Solving games that are usually two-player to find the winner.

Edit This Page

Nim

Focus Problem – try your best to solve this problem before continuing!

Rules

Nim might be one of the most well-known examples in game theory. In this game there are considered nn piles of some item. The problem uses sticks, while some others use stones; we'll be using sticks to stay consistent with the CSES problem. Regardless, players take turns removing a nonzero number of sticks from a certain pile, and the player who takes the last stick wins.

Let's represent the current state of the piles with [x1,x2,x3,,xn][x_1, x_2, x_3, \ldots, x_n], where xix_i is the number of sticks in pile ii. You'll soon see that it doesn't matter whether we include empty piles in our array.

We now propose something that may seem unintuitive at first:

The player who moves first can always win if the xor-sum of the sizes of the piles is nonzero.

Proof

For our own sanity, we'll refer to a state with a xor-sum of 0 as a "losing state" and a state with a nonzero xor-sum as a "winning state."

To prove this, we have to show that from a losing state, any move we make will result in a winning state, and from a winning state, at least one move that we can make will result in a losing state. Notice that when we make our move, the game switches to a "sub-game" of sorts where the second player becomes the first player. Thus, moving to a winning state for the next turn means that they win and we lose.

However, it's probably good to prove our base cases first. [0][0] is a losing state, since the first player can't make any moves and thus loses. On the other hand, [x][x] where xx is any positive integer is a winning state since we can take xx sticks from the only pile. As we can see, the first state has a xor-sum of 00 while the second has a xor-sum of xx which is nonzero.

Losing \rightarrow Winning

Let's first prove that any losing state will move to a winning state for the other player.

Since XOR is a commutative and associative operation, we can assume WLOG that the move we make is on pile 11.

The current xor-sum of the state is x1x2xn=0x_1 \oplus x_2 \oplus \cdots x_n=0. Notice that this can be thought of x1x_1 XOR the xor-sum of the rest of the numbers. Let's call that xor-sum of everything else yy.

Since the xor-sum is 00, x1=yx_1=y. Removing any number of sticks from x1x_1 will break this equality and turn x1yx_1 \oplus y nonzero, which is precisely the definition for our winning state.

Winning \rightarrow Losing

Now we have to prove that any winning state can move to a losing state for the other player. Notice the use of can instead of will in our statement due to how these games work.

This time, let's define yy as the xor-sum of all the piles instead of all except for one. Then, say we have an xix_i such that xi>yxix_i > y \oplus x_i. Note that yxiy \oplus x_i is the xor-sum of all the other elements, since XOR is its own inverse.

With this, we can take xi(yxi)x_i - (y \oplus x_i) sticks from xix_i, then makes it equivalent to yxiy \oplus x_i and the xor-sum of the whole board will be 00, thus forming a losing state for the second player.

But all of this hinges on the existence of an xix_i such that xi>yxix_i > y \oplus x_i. Does it always exist?

Suppose that pp is the position of the most significant bit in yy. Then, we know that there must exist some xix_i with a set bit at pp as well. Whether pp is the most significant bit in xix_i or not, XOR-ing the two gives a result with a 00 at bit pp. This then guarantees that there exists an xi>yxix_i > y \oplus x_i.

VariableValue
yy0...01?...?
xix_i?...?1?...?
yxiy \oplus x_i?...?0?...?

Since the first part of yy is all 0s, the first parts of xix_i and yxiy \oplus x_i are the same.

Implementation

Time Complexity: O(N)\mathcal{O}(N)

C++

#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::vector;
int main() {
int test_num;
std::cin >> test_num;

Java

import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
int testNum = Integer.parseInt(read.readLine());
for (int t = 0; t < testNum; t++) {
int pileNum = Integer.parseInt(read.readLine());
StringTokenizer pileST = new StringTokenizer(read.readLine());

Python

for _ in range(int(input())):
pile_num = int(input())
sizes = [int(p) for p in input().split()]
assert pile_num == len(sizes)
xor_sum = 0
for s in sizes:
xor_sum ^= s
print("first" if xor_sum != 0 else "second")

Optional: What if we could add?

In some cases, players may be allowed to add sticks as well as remove them. Funnily enough, this doesn't change how the winning and losing states are determined, i.e. the outcome of the game.

Sprague-Grundy theorem

Before we get into this theorem, we first have to define what "nimbers" (sometimes referred to as "grundy values") are. Each nimber — say 0, 3, or 4 — represents a one-pile game of Nim with that many stones. Notice that for any positive nimber, the first player always wins since they can take all the stones from the pile and leave none for the second. On the other hand, the nimber 0 is a losing state, since the first player can't take any more stones.

What the Sprague-Grundy theorem allows us to do is to reduce the state of certain types of games into a nimber.

The way we do this is with a recursive definition. If we can compute the nimbers of all states rir_i reachable from a certain state ss, then ss itself can be reduced to the nimber

n(s)=mex(r1,r2,,rk)n(s)=\text{mex}(r_1, r_2, \cdots, r_k)

For convenience, we have defined nn as the function that reduces game states to nimbers.

The mex\text{mex} function takes a list of numbers and returns the biggest non-negative integer that is not included in the list. Notice that the name is a portmanteau of "max" and "excluded".

One-pile Example

Let's take a look at an altered version case of Nim. Here's there's only one pile, but each player can only remove 1, 2, or 3 stones.

According to the theorem, the nimber value is the mex\text{mex} of the reachable nimber value. In the case of this game, each state can reach the previous 33 values because we can only remove 1, 2 or 3 stones in one move.

Here's how the values are computed:

  • n(0)=0n(0) = 0
  • n(1)=mex(0)=1n(1) = \text{mex}(0) = 1
  • n(2)=mex(0,1)=2n(2) = \text{mex}(0, 1) = 2
  • n(3)=mex(0,1,2)=3n(3) = \text{mex}(0, 1, 2) = 3
  • n(4)=mex(1,2,3)=0n(4) = \text{mex}(1, 2, 3) = 0
  • n(5)=mex(2,3,0)=1n(5) = \text{mex}(2, 3, 0) = 1
  • n(6)=mex(3,0,1)=2n(6) = \text{mex}(3, 0, 1) = 2
  • n(7)=mex(0,1,2)=3n(7) = \text{mex}(0, 1, 2) = 3

This gives us the following table of nimber values:

Here's the table of nimber values:

Nimber table

All nimber reductions that are equal to 0 are losing states; see n(0)n(0) and n(4)n(4).

Recall that a winning state means that you can put the other player in a losing state. On the other hand, a losing state means that every move results in a winning state for the opponent. For example, n(4)=0n(4)=0 because 11, 22, and 33 are winning. Similarly, n(8)=0n(8) = 0, because we can't reach 44 in a single move.

Multiple-pile Example

How about we try reducing multiple-pile Nim games with this theorem?

We know that a state is a losing state if the xor-sum is 0. This matches up exactly with how our nimbers work, as the 0 nimber represents a losing state.

Thus, to reduce a Nim game of multiple piles to a nimber, we can take the xor-sum of the nimbers of the single piles. Notice that the nimber of only one pile is the size of the pile.

This is equivalent to the formula using mex, but a proof of that is beyond the scope of this module. We merely try to give some intuition for why this is true.

n([p1,,pn])=i=1nn(pi)n([p_1, \cdots, p_n])=\bigoplus_{i=1}^n n(p_i)

This xor-sum reduction can be extended to more things than just Nim. If we can decompose a game into multiple disjoint parts where one player makes a chooses a subgame then makes a move, then the nimbers of these games can be combined with the xor-sum.

Applications

S-NIM

Focus Problem – try your best to solve this problem before continuing!

Explanation

We can compute the nimber values of each pile with the mex definition and then combine them using the XOR operator.

Implementation

Time Complexity: O(PK+ML)\mathcal{O}(PK+ML), where PP is the maximum pile size.

C++

#include <algorithm>
#include <iostream>
#include <set>
#include <vector>
using std::cout;
using std::endl;
using std::vector;
const int MAX_PILE = 1e4;

Python

MAX_PILE = 10**4
can_remove = [int(i) for i in input().split()][1:]
nimbers = [0 for _ in range(MAX_PILE + 1)]
for i in range(1, MAX_PILE + 1):
reachable = {nimbers[i - n] for n in can_remove if i - n >= 0}
for n in range(MAX_PILE + 1):
if n not in reachable:
nimbers[i] = n

Chessboard Game, Again!

Focus Problem – try your best to solve this problem before continuing!

Explanation

Here we see a case of using the xor-sum to combine things that aren't straight Nim games.

In this problem, we can decompose each game into a bunch of subgames, where each subgame is a single coin. Players choose the subgame (coin) and then make a move.

We first apply the mex formula to calculate nimbers for individual coins, and then combine them at the end with a xor-sum

Implementation

Time Complexity: O(TK)\mathcal{O}(TK), since the board is constant size.

C++

#include <iostream>
#include <map>
#include <set>
#include <vector>
using std::cout;
using std::endl;
using std::vector;
const int BOARD_LEN = 15;

Python

from functools import lru_cache
BOARD_LEN = 15
@lru_cache
def nimber(r: int, c: int) -> int:
""":return: The nimber value of a coin at a single position"""
if not (0 <= r < BOARD_LEN and 0 <= c < BOARD_LEN):
return -1 # Return -1 to not interfere with the mex operation

Problems

StatusSourceProblem NameDifficultyTags
CFEasy
Show TagsGame Theory, Nimbers
CFEasy
Show TagsBitmasks, DP, Game Theory, Nimbers
CFEasy
Show TagsBitmasks, DP, Game Theory, Nimbers
IOIEasy
Show TagsGame Theory
IOINormal
Show TagsGame Theory
Baltic OINormal
Show TagsGame Theory
ACNormal
Show TagsGame Theory, Nimbers, Tree
ACNormal
Show TagsGame Theory, Nimbers
GCJHard
Show TagsGame Theory, Nimbers
ACHard
Show TagsGame Theory, NIM
POIVery Hard
POIVery Hard
POIInsane

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!