🎮 Напреднала Теория на Игрите (Game Theory)

Комбинаторната теория на игрите разглежда игри, които са: 1. Impartial (Безпристрастни): Достъпните ходове зависят само от състоянието на играта, а не от това кой играч е на ход. (Шахът НЕ е такава игра, защото белите не могат да местят черни фигури). 2. Perfect Information (Пълна информация): Няма скрити карти или зарове. 3. Normal Play Convention: Последният играч, който може да направи ход, печели (или този, който не може да направи ход, губи).

1. Играта на Ним (Nim Game)

Това е "майката" на всички безпристрастни игри. * Правила: Има $K$ купчини с камъчета с размери $a_1, a_2, …, a_k$. Двама играчи се редуват да избират една купчина и да премахват произволен брой камъчета от нея (поне едно). * Условие за победа: Който вземе последното камъче, печели.

Стратегия (Nim-Sum)

Победителят се определя чрез XOR сумата на размерите на купчините: $S = a_1 ⊕ a_2 ⊕ … ⊕ a_k$

Ако $S ≠ 0$: Текущата позиция е Печеливша (N-position). Първият играч може да направи ход, който да доведе сумата до 0.
Ако $S = 0$: Текущата позиция е Губеща (P-position). Всякакъв ход ще направи сумата различна от 0.

Доказателство: 1. Крайното състояние (всички 0) има XOR сума 0. 2. От състояние с $S=0$ всеки ход води до $S ≠ 0$. 3. От състояние с $S ≠ 0$ съществува ход, който води до $S=0$. Нека $d$ е най-старшият бит на $S$. Избираме купчина $a_i$, която има този бит (1). Заменяме $a_i$ с $a_i ⊕ S$. Тъй като $a_i ⊕ S < a_i$, това е валиден ход.

2. Теорема на Спрейг-Грънди (Sprague-Grundy)

Тази теорема гласи, че всяка безпристрастна игра е еквивалентна на купчина на Ним с определен размер. Този размер се нарича Grundy число (или nim-value) на състоянието.

2.1. Изчисляване на Grundy числа (MEX)

За дадено състояние $u$, Grundy числото $g(u)$ се дефинира рекурсивно като: $g(u) = \text{MEX}(\{ g(v) \mid u \to v \text{ е валиден ход} \})$

MEX (Minimum Excluded value) на множество от неотрицателни цели числа е най-малкото неотрицателно цяло число, което НЕ присъства в множеството. * $\text{MEX}(\{0, 1, 3\}) = 2$ * $\text{MEX}(\{1, 2, 5\}) = 0$ * $\text{MEX}(\emptyset) = 0$ (за губещи състояния)

2.2. Комбиниране на игри

Ако една игра се състои от няколко независими под-игри (напр. няколко фигури на дъска, които не си пречат), Grundy числото на общата игра е XOR сумата на Grundy числата на под-игрите. $G_{total} = g(G_1) ⊕ g(G_2) ⊕ … ⊕ g(G_k)$

Това е изключително мощно! Вместо да анализираме сложната игра като цяло, я разбиваме на части, смятаме MEX за всяка част и правим XOR.

Пример: Игра върху Граф

Имаме пулче върху връх на насочен ацикличен граф (DAG). Играчите местят пулчето по ребрата. Който не може да мръдне, губи. Решение: 1. За всеки връх $u$ пресмятаме $g(u)$ чрез DFS и мемоизация. 2. Ако имаме $K$ пулчета, позицията е еквивалентна на Nim с купчини с размери $g(u_1), g(u_2), …$.

#include <vector>
#include <set>
#include <algorithm>

using namespace std;

const int MAXN = 1000;
vector<int> adj[MAXN];
int memo[MAXN];

int grundy(int u) {
    if (memo[u] != -1) return memo[u];

    set<int> reachable_values;
    for (int v : adj[u]) {
        reachable_values.insert(grundy(v));
    }

    int mex = 0;
    while (reachable_values.count(mex)) mex++;

    return memo[u] = mex;
}

3. Вариации на игри

3.1. Staircase Nim

Монети са разположени на стъпалата на стълбище (0, 1, 2...). Ходът е: премести произволен брой монети от стъпало $i$ на стъпало $i-1$. Монетите от стъпало 0 се премахват. Решение: Имат значение само монетите на нечетните позиции (1, 3, 5...). * Преместване от нечетно на четно ($i → i-1$) е еквивалентно на премахване на монети от Nim купчина (защото четните не се броят). * Преместване от четно на нечетно ($i → i-1$) е обратимо от противника (той може да ги премести на $i-2$). * Отговор: $a_1 ⊕ a_3 ⊕ a_5 …$

3.2. Green Hackenbush

Игра върху графи, където ръбовете се премахват. * Всеки ръб е или "зелен" (може да се маха от всеки), или стъпва на земята. * При махане на ръб, всичко, което не е свързано със земята, пада (изчезва). * За дървета: $g(u) = (\oplus_{v \in children} (g(v) + 1))$.

4. Misere Play

Вариантът, където последният играч губи. * За обикновения Nim: Стратегията е същата като Normal Play, освен ако всички купчини не са с размер 1. * Ако всички са 1: Печели се, ако броят им е нечетен (XOR = 1). * В противен случай: Играем по нормалната стратегия.

5. Задачи за упражнение

HackerRank "Game of Stones": Проста игра с изваждане, решава се с DP/Grundy.
SPOJ ADAGAME: Игра върху граф с цикли (изисква внимателен анализ).
Codeforces 768E: Game of Stones (прекалкулация на Grundy числата).
UVa 10165: Stone Game (Чист Nim).

🏁 Заключение

Видите ли игра в състезание: 1. Проверете дали е безпристрастна. 2. Ако да -> Grundy теорема (XOR). 3. Разбийте я на независими под-игри. 4. Сметнете MEX.

6. Имплементация на Grundy числа с мемоизация

За сложни игри с много състояния, използваме map или unordered_map за мемоизация:

#include <unordered_map>
#include <set>

unordered_map<int, int> memo;

int grundy(int state) {
    if (memo.count(state)) return memo[state];

    // Базов случай: загубена позиция
    if (isLosing(state)) return memo[state] = 0;

    set<int> reachable;
    for (int nextState : getNextStates(state)) {
        reachable.insert(grundy(nextState));
    }

    // MEX
    int mex = 0;
    while (reachable.count(mex)) mex++;

    return memo[state] = mex;
}

7. Impartial игри с допълнителни правила

7.1. Anti-Nim (Misère Nim)

В тази вариация последният играч губи (обратно на нормалния Nim).

Стратегия: * Ако всички купчини имат размер 1: Печели се, ако броят им е нечетен. * Иначе: Играем по стандартната стратегия (XOR сума), но целим да оставим противника в позиция с XOR = 1.

7.2. Moore's Nim

Позволява се премахване на камъчета от произволен брой купчини наведнъж (не само от една).

Решение: Grundy числото на позицията е същото като в обикновен Nim - XOR на размерите.

8. Игри с частична информация

Ако играта не е с пълна информация (има случайност или скрити елементи), Grundy теоремата не се прилага директно. Тогава се използват: * Вероятностни методи. * Minimax алгоритъм (за игри като Шах, Го). * Alpha-Beta Pruning (оптимизация на Minimax).

9. Разширени примери

9.1. Игра "Subtract Set"

Имате число $N$. На ход можете да извадите $a_1, a_2, \ldots, a_k$ (даден набор от числа). Който стигне до 0, печели.

Решение:

set<int> S = {1, 3, 4}; // Позволени изваждания
int memo[1001];

int grundy(int n) {
    if (n == 0) return 0; // Губеща позиция
    if (memo[n] != -1) return memo[n];

    set<int> reachable;
    for (int s : S) {
        if (n >= s) {
            reachable.insert(grundy(n - s));
        }
    }

    int mex = 0;
    while (reachable.count(mex)) mex++;
    return memo[n] = mex;
}

За игра с $K$ независими позиции: $G = g(n_1) \oplus g(n_2) \oplus \ldots \oplus g(n_k)$.

9.2. Игра "Divisor Game"

Имате число $N$. На ход избирате делител $d$ на $N$ (където $d < N$) и заменяте $N$ с $N - d$. Който стигне до 0 (или не може да направи ход), губи.

Наблюдение: Това е еквивалентно на проверка на четността на $N$! * Ако $N$ е четно, печелите. * Ако $N$ е нечетно, губите.

Но ако условията са по-сложни, използвайте Grundy числа.

10. Композиция на игри (Game Sums)

Ако имате няколко игри, които се играят паралелно (всеки играч избира в коя игра да направи ход), общата игра е сумата на отделните игри: $$G_{total} = G_1 + G_2 + \ldots + G_k$$

Grundy числото на сумата е XOR на Grundy числата: $$g(G_{total}) = g(G_1) \oplus g(G_2) \oplus \ldots \oplus g(G_k)$$

🏁 Финални съвети

Винаги първо проверете дали играта е безпристрастна и с пълна информация.
Начертайте граф на състоянията за малки примери, за да разберете Grundy числата.
Помнете, че XOR е ключовата операция в теорията на игрите.
За състезания под натиск от време: Научете стандартните игри (Nim, Staircase Nim) наизуст.

Теорията на игрите е една от най-красивите области в състезателното програмиране - комбинира математика, логика и програмиране по уникален начин!