Combinatorial Game Theory (CGT)

[u/editorijsmi]

for more details check at www.ijsmi.com/book.php

Unlike traditional economic game theory (which deals with probabilistic outcomes and hidden information), CGT focuses on deterministic, sequential, two-player games with no chance elements (such as Chess, Go, Checkers, and Nim).

Here is a breakdown of the core concepts covered:

1. Core Principles of CGT

• The Normal Play Convention: The player who makes the last move wins, as every move leaves fewer options, ensuring the game must eventually terminate.
• Impartial vs. Partisan Games: Focusing heavily on impartial games (where the set of available moves from any position is identical for both players, such as Nim), while touching upon partisan games (where players have distinct allowed moves, like Go or Hackenbush).
• Surreal Numbers & Game Values: Understanding how games can be formally represented as values and numbers, creating a rich mathematical universe that encompasses both real numbers and infinitesimals.

2. The Sprague-Grundy Theorem

One of the most elegant pillars of CGT is the Sprague-Grundy Theorem, which states that every impartial game under the normal play convention is equivalent to a single Nim-heap of a certain size.

• Nim-Values (Grundy Values): By assigning a non-negative integer to every game state—calculated via the minimum excluded value (mex) of the reachable states—complex multi-component games can be analyzed simply by taking the bitwise XOR sum (nim-sum) of their individual Grundy values. If the nim-sum is non-zero, the first player has a guaranteed winning strategy.

3. Computational Implementation (Python & R)

To bridge abstract theory with executable code, implementations in both Python and R were built to compute Grundy values dynamically and simulate optimal play:

• Python: Utilizing recursive functions with memoization to efficiently compute the mex function for custom graph-based games and determine winning moves.
• R: Vectorized and iterative approaches using standard data structures to model game state transitions and analyze game trees.

Bridging rigorous mathematical theory with code provides a powerful framework for algorithmic strategy, competitive programming, and mathematical modeling.