Game Theory

Combinatorial Game Theory

เกมที่มีคุณสมบัติ:

• Two players - ผลัดกันเล่น
• Perfect information - รู้ทุกอย่างเกี่ยวกับ game state
• No chance - ไม่มี randomness
• Finite - เกมจบใน finite moves
• Normal play - คนที่ไม่สามารถเดินได้แพ้

Nim Game

กติกา

มี $n$ กอง หิน กองที่ $i$ มี $a_i$ ก้อน ผลัดกันหยิบหินจากกองใดก็ได้ (อย่างน้อย 1 ก้อน) คนที่ไม่สามารถหยิบได้แพ้

Nim-Sum (XOR)

$\text{Nim-value} = a_1 \oplus a_2 \oplus \ldots \oplus a_n$

• ถ้า nim-value $= 0$: Second player wins (P-position)
• ถ้า nim-value $\neq 0$: First player wins (N-position)

bool firstPlayerWins(vector<int>& piles) {
    int xorSum = 0;
    for (int pile : piles) {
        xorSum ^= pile;
    }
    return xorSum != 0;
}

Winning Move in Nim

pair<int, int> winningMove(vector<int>& piles) {
    int xorSum = 0;
    for (int pile : piles) xorSum ^= pile;
    
    if (xorSum == 0) return {-1, -1};  // No winning move
    
    for (int i = 0; i < piles.size(); i++) {
        int target = piles[i] ^ xorSum;
        if (target < piles[i]) {
            return {i, piles[i] - target};  // Remove this many from pile i
        }
    }
    
    return {-1, -1};
}

Sprague-Grundy Theorem

Grundy Number (Nimber)

สำหรับ game state $s$:

$G(s) = \text{mex}(\{G(s') : s' \text{ is reachable from } s\})$

โดยที่ $\text{mex}(S)$ = minimum excludant = ค่า non-negative integer ที่น้อยที่สุดที่ไม่อยู่ใน $S$

Properties

• Terminal state: $G = 0$
• P-position: $G = 0$
• N-position: $G > 0$
• Independent games: $G(A + B) = G(A) \oplus G(B)$

Implementation

int mex(set<int>& s) {
    int result = 0;
    while (s.count(result)) result++;
    return result;
}

// Example: Subtract game (can subtract 1, 2, or 3)
vector<int> grundy;

void computeGrundy(int maxN) {
    grundy.resize(maxN + 1);
    grundy[0] = 0;  // terminal state
    
    for (int n = 1; n <= maxN; n++) {
        set<int> reachable;
        for (int move = 1; move <= 3 && move <= n; move++) {
            reachable.insert(grundy[n - move]);
        }
        grundy[n] = mex(reachable);
    }
}

Classic Games

1. Nim Variants

Staircase Nim

$n$ piles arranged as staircase. Can move any number from pile $i$ to pile $i-1$ (pile 0 is removed).

Solution: XOR of odd-indexed piles

bool stairNim(vector<int>& piles) {
    int xorSum = 0;
    for (int i = 0; i < piles.size(); i += 2) {
        xorSum ^= piles[i];
    }
    return xorSum != 0;
}

Poker Nim

Same as Nim but can also add stones (up to limit).

Solution: Same as Nim (adding doesn’t help)

2. Subtraction Game

Can remove stones from set $S$ (e.g., $S = \{1, 3, 4\}$)

void subtractGame(int maxN, vector<int>& S) {
    vector<int> g(maxN + 1, 0);
    
    for (int n = 1; n <= maxN; n++) {
        set<int> reachable;
        for (int s : S) {
            if (s <= n) {
                reachable.insert(g[n - s]);
            }
        }
        g[n] = mex(reachable);
    }
}

3. Wythoff’s Game

Two piles. Can remove any from one pile, OR remove equal amounts from both.

Solution: P-positions are $(\lfloor k\phi \rfloor, \lfloor k\phi^2 \rfloor)$ for $k = 0, 1, 2, \ldots$

โดยที่ $\phi = \frac{1 + \sqrt{5}}{2}$ (golden ratio)

bool wythoff(int a, int b) {
    if (a > b) swap(a, b);
    double phi = (1 + sqrt(5)) / 2;
    int k = b - a;
    int expected = (int)(k * phi);
    return a != expected;  // First player wins if not P-position
}

4. Euclid’s Game

Two numbers $a, b$. Can subtract any positive multiple of smaller from larger (result must be positive). Last to move wins.

bool euclidGame(long long a, long long b) {
    while (true) {
        if (a > b) swap(a, b);
        if (a == 0) return false;  // Current player loses
        if (b >= 2 * a) return true;  // Can control the game
        b -= a;
        // Role switches
    }
}

5. Green Hackenbush

Game on graph. Remove edge (and disconnected parts). Last to move wins.

• Tree: Grundy = XOR of edge Grundy values
• String (path): length mod 2

Multiple Games

เมื่อเล่นหลายเกมพร้อมกัน (เลือกเกมใดก็ได้ที่ยังไม่จบ):

$G(\text{total}) = G(game_1) \oplus G(game_2) \oplus \ldots$

bool multipleGames(vector<vector<int>>& games) {
    int totalG = 0;
    for (auto& game : games) {
        totalG ^= computeGrundy(game);
    }
    return totalG != 0;
}

Tips

1. Look for patterns - Grundy numbers often have periodic patterns
2. Small cases first - Compute for small inputs to find pattern
3. XOR property - Key insight for combining independent games
4. P and N positions - P = Previous player wins (current loses), N = Next player wins