Master Combinatorial Game Theory: From Nim-Values to Python & R Code

Introduction to Combinatorial Game Theory (CGT)

Unlike traditional economic game theory—which often deals with incomplete information, probabilities, and strategic deception—Combinatorial Game Theory (CGT) focuses on deterministic, sequential, two-player games with perfect information and no chance elements (such as dice or shuffled cards). Classic examples include Chess, Checkers, Go, and the foundational game of Nim.

Core Principles and Rules

• The Normal Play Convention: The player who makes the last legal move wins the game. Because every valid move reduces the available options, infinite loops are avoided in finite games, ensuring termination.
• Impartial vs. Partisan Games: Impartial games are those where the set of available moves from any given position is identical for both players (e.g., Nim). Partisan games allow different players distinct legal moves (e.g., Chess, where one player controls white pieces and the other black).
• Game Values and Surreal Numbers: Developed largely by John Horton Conway, CGT demonstrates how game states can be assigned numerical values, giving rise to surreal numbers that include standard integers, fractions, and infinitesimals.

The Sprague-Grundy Theorem

One of the most powerful and elegant results in CGT is the Sprague-Grundy Theorem. It establishes that every impartial game under the normal play convention is equivalent to a single Nim-heap of a specific size.

Nim-Values (Grundy Values)

To analyze complex multi-component games, positions are mapped to non-negative integers called Grundy values or Nim-values:

• Terminal positions (where no moves remain) have a Grundy value of $0$.
• The Grundy value of any state is determined using the mex (minimum excluded) function: the smallest non-negative integer not present in the set of Grundy values of all reachable successor states.
• Complex games are solved by taking the bitwise XOR sum (nim-sum) of the individual component Grundy values. A non-zero nim-sum indicates a winning strategy for the current player.

Computational Implementation

Translating abstract mathematical definitions into executable code helps automate winning move calculations. Below are implementations in both Python and R.

Python Implementation (Grundy Value & Mex)

def mex(values):
    """Calculate the Minimum Excluded (mex) value."""
    s = set(values)
    m = 0
    while m in s:
        m += 1
    return m

def get_grundy(state, memo={}):
    """Recursively calculate the Grundy value for an impartial game state."""
    if state in memo:
        return memo[state]
    
    successors = get_valid_moves(state)
    if not successors:
        memo[state] = 0
        return 0
    
    successor_grundy = [get_grundy(s, memo) for s in successors]
    memo[state] = mex(successor_grundy)
    return memo[state]

# Example placeholder function for valid transitions
def get_valid_moves(state):
    # Returns a list of next states
    return [state - i for i in [1, 2, 3] if state - i >= 0]

R Implementation

# Calculate Minimum Excluded (mex) value in R
mex <- function(values) {
  m <- 0
  while (m %in% values) {
    m <- m + 1
  }
  return(m)
}

# Iterative or memoized function for Grundy values
get_grundy_r <- function(max_state) {
  grundy <- numeric(max_state + 1)
  grundy[1] <- 0 # State 0 has grundy value 0
  
  for (i in 1:max_state) {
    # Define valid step sizes (e.g., removing 1, 2, or 3 items)
    allowed_moves <- c(1, 2, 3)
    reachable <- i - allowed_moves
    reachable <- reachable[reachable >= 0]
    
    # Get grundy values of reachable states
    successor_values <- grundy[reachable + 1]
    grundy[i + 1] <- mex(successor_values)
  }
  
  return(grundy)
}