🎮 Теория на игрите: Стратегии и Анализ

🎯 Въведение

Теорията на игрите изследва стратегическото взаимодействие между рационални играчи. В състезателното програмиране разглеждаме предимно комбинаторни игри - игри с пълна информация, детерминистични ходове, без случайност и с два играча, които играят на ред.

Основният въпрос е: Кой играч има печеливша стратегия при оптимална игра? "Оптимална игра" означава, че и двамата играчи играят перфектно - винаги правят най-добрия възможен ход.

♟️ Класификация на игрите

В състезателното програмиране разглеждаме безпристрастни игри (impartial games) и партизански игри (partizan games). - Безпристрастни: Допустимите ходове зависят само от състоянието, не от това кой е на ход (напр. Ним). - Партизански: Ходовете зависят от играча (напр. Шах - белите местят бели фигури).

🔙 Ретрограден анализ (Retrograde Analysis)

Това е техника за определяне на печеливши/губещи позиции чрез връщане от края към началото. Използва се за игри, представени като граф на състоянията.

Терминални състояния: Всички състояния, от които няма ходове, са Губещи (L).
Ако от състояние $U$ има поне един ход към Губещо състояние $V$, то $U$ е Печелившо (W).
Ако от състояние $U$ всички ходове водят към Печеливши състояния, то $U$ е Губещо (L).

Алгоритъм (BFS-подобен): - Инициализираме degree[u] = брой изходящи ребра. - Вкарваме всички терминални състояния в опашка. - Когато обработваме състояние $V$ (чийто статус вече знаем): - За всяко $U$, водещо към $V$: - Ако $V$ е губещо $ o$ $U$ става печелившо веднага. - Ако $V$ е печелившо $ o$ намаляваме degree[U]. Ако degree[U] стане 0, значи всички ходове от $U$ водят към печеливши $ o$ $U$ става губещо.

⚖️ Играта Ним и XOR суми (Разширено)

Основна теория на Ним

Класическата игра Ним се състои от няколко купчини с камъчета. На ход, играч взима произволен брой камъчета от ЕДНА купчина (поне един). Губи този, който не може да направи ход (всички купчини са празни).

Теорема на Bouton: Позицията е губеща точно когато XOR-ът на всички купчини е 0.

bool isLosingPosition(vector<int>& piles) {
    int xorSum = 0;
    for (int pile : piles) {
        xorSum ^= pile;
    }
    return xorSum == 0;  // true = губеща, false = печеливша
}

Защо XOR?

Всяко неотрицателно цяло число $n$ има уникално разлагане на сума от степени на 2. Играта Ним е еквивалентна на сума от няколко игри с по една купчина. Операцията, която съответства на "събиране на игри без взаимодействие", е побитовото събиране без пренос (XOR).

Когато комбинираме няколко независими игри, печелившостта на комбинираната игра се определя от XOR на Грънди числата на отделните игри.

Намиране на печеливш ход

Ако XOR-ът не е 0, има печеливш ход. Как да го намерим?

int findWinningMove(vector<int>& piles) {
    int xorSum = 0;
    for (int pile : piles) {
        xorSum ^= pile;
    }

    if (xorSum == 0) {
        return -1;  // Няма печеливш ход (губеща позиция)
    }

    // Намираме купчина, от която можем да вземем
    for (int i = 0; i < piles.size(); i++) {
        int target = piles[i] ^ xorSum;
        if (target < piles[i]) {
            // Взимаме от купчина i до target
            cout << "Вземи от купчина " << i 
                 << " до " << target << " камъчета" << endl;
            return i;
        }
    }
    return -1;
}

Вариации на Ним:

Misere Nim: Печели този, който е принуден да вземе последния предмет (губи този, който вземе последния).
Стратегия: Същата като нормалната игра, освен ако всички купчини са с размер 1. Тогава печелившият ход е да оставим нечетен брой купчини.
Nim с ограничение: Може да се взимат най-много $K$ камъчета.
Еквивалентно на купчина с размер $N \bmod (K+1)$.
Staircase Nim: Монети на стъпала. Местенето от стъпало $i$ на $i-1$ е еквивалентно на махане.
Отчитат се само стъпалата на нечетни позиции (1, 3, 5...).

// Misere Nim
bool misereNim(vector<int>& piles) {
    int xorSum = 0;
    bool allOnes = true;

    for (int pile : piles) {
        xorSum ^= pile;
        if (pile > 1) allOnes = false;
    }

    if (allOnes) {
        // Всички купчини са с размер 1
        return piles.size() % 2 == 1;  // Нечетен брой = печеливша
    }

    return xorSum != 0;  // Като нормалния Ним
}

// Staircase Nim
bool staircaseNim(vector<int>& stairs) {
    int xorSum = 0;
    for (int i = 0; i < stairs.size(); i++) {
        if (i % 2 == 1) {  // Само нечетните стъпала
            xorSum ^= stairs[i];
        }
    }
    return xorSum != 0;
}

🧮 Грънди числа (Sprague-Grundy Theorem)

За произволна безпристрастна игра можем да дефинираме Грънди число (или nimber) за всяко състояние.

Дефиниция: Грънди числото на състояние е минималното неотрицателно цяло число (MEX - Minimal EXcludant), което не е Грънди число на никое от състоянията, до които можем да стигнем с един ход.

\[g(position) = \text{mex}(\{g(next) : next \text{ е достижимо от } position\})\]

MEX функция:

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

Пресмятане на Грънди числа

map<State, int> grundy;

int computeGrundy(State state) {
    if (isTerminal(state)) return 0;  // Няма ходове

    if (grundy.count(state)) return grundy[state];

    set<int> reachable;
    for (State next : getNextStates(state)) {
        reachable.insert(computeGrundy(next));
    }

    return grundy[state] = mex(reachable);
}

Теорема на Sprague-Grundy

Комбинацията от няколко независими игри има Грънди число равно на XOR на Грънди числата на отделните игри.

// Комбинация от игри
int combinedGrundy(vector<int>& individualGrundies) {
    int result = 0;
    for (int g : individualGrundies) {
        result ^= g;
    }
    return result;
}

// Позицията е печеливша ако Грънди числото != 0
bool isWinning(int grundy) {
    return grundy != 0;
}

Пример: Игра на премахване

Имаме купчина от $N$ камъчета. На ход може да се вземат 1, 2 или 3 камъчета. Какво е Грънди числото?

int grundy[MAXN];

void computeGrundyForGame() {
    grundy[0] = 0;  // Терминална позиция

    for (int n = 1; n < MAXN; n++) {
        set<int> reachable;

        // Можем да вземем 1, 2 или 3 камъчета
        if (n >= 1) reachable.insert(grundy[n-1]);
        if (n >= 2) reachable.insert(grundy[n-2]);
        if (n >= 3) reachable.insert(grundy[n-3]);

        grundy[n] = mex(reachable);
    }
}

За тази конкретна игра Грънди числата са: $0, 1, 2, 3, 0, 1, 2, 3, \ldots$ (периодични с период 4).

🏆 Минимакс с Мемоизация

За игри, които не са безпристрастни (нямат Грънди числа), използваме рекурсия с памет.

Основна идея

Всяко състояние може да бъде: - Печеливша (W): Текущият играч може да спечели - Губеща (L): Текущият играч неизбежно губи при оптимална игра - Равенство (D): При оптимална игра резултатът е равенство (рядко в комбинаторни игри)

map<State, int> memo;
// 1: Печели, -1: Губи, 0: Неизвестно

int solve(State state) {
    if (is_terminal(state)) return -1; // Няма ходове -> губим
    if (memo.count(state)) return memo[state];

    int res = -1; // Предполагаме, че губим
    for (State next_state : get_moves(state)) {
        if (solve(next_state) == -1) { // Ако противникът губи от следващото състояние
            res = 1; // Ние печелим
            break;
        }
    }
    return memo[state] = res;
}

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

Двама играчи местят фигура по граф. Губи този, който не може да направи ход.

vector<int> graph[MAXN];
int dp[MAXN];  // 1 = печеливша, -1 = губеща, 0 = непресметната

int solveGraph(int node, int depth) {
    if (graph[node].empty()) return -1;  // Няма ходове
    if (dp[node] != 0) return dp[node];

    for (int next : graph[node]) {
        if (solveGraph(next, depth + 1) == -1) {
            return dp[node] = 1;  // Намерихме губещ ход за противника
        }
    }

    return dp[node] = -1;  // Всички ходове водят до печеливши за противника
}

Минимакс с оценка (за сложни игри)

За игри като шах или го, където не можем да изчислим всички позиции, използваме евристична оценка.

const int INF = 1e9;

// Максимизираме за нас, минимизираме за противника
int minimax(State state, int depth, bool maximizing) {
    if (depth == 0 || isTerminal(state)) {
        return evaluate(state);  // Евристична функция
    }

    if (maximizing) {
        int maxEval = -INF;
        for (State next : getMoves(state)) {
            int eval = minimax(next, depth - 1, false);
            maxEval = max(maxEval, eval);
        }
        return maxEval;
    } else {
        int minEval = INF;
        for (State next : getMoves(state)) {
            int eval = minimax(next, depth - 1, true);
            minEval = min(minEval, eval);
        }
        return minEval;
    }
}

Alpha-Beta Pruning (оптимизация)

Окастряме клонове, които не могат да повлияят на резултата.

int alphaBeta(State state, int depth, int alpha, int beta, bool maximizing) {
    if (depth == 0 || isTerminal(state)) {
        return evaluate(state);
    }

    if (maximizing) {
        int maxEval = -INF;
        for (State next : getMoves(state)) {
            int eval = alphaBeta(next, depth - 1, alpha, beta, false);
            maxEval = max(maxEval, eval);
            alpha = max(alpha, eval);
            if (beta <= alpha) break;  // Beta cut-off
        }
        return maxEval;
    } else {
        int minEval = INF;
        for (State next : getMoves(state)) {
            int eval = alphaBeta(next, depth - 1, alpha, beta, true);
            minEval = min(minEval, eval);
            beta = min(beta, eval);
            if (beta <= alpha) break;  // Alpha cut-off
        }
        return minEval;
    }
}

📊 Практически съвети и трикове

1. Симетрични игри

В симетрични игри (еднаква дъска за двамата играчи), вторият играч често може да копира ходовете на първия.

Пример: На дъска с централна симетрия, вторият играч играе симетрично на хода на първия.

2. Паритет

Много игри зависят от паритета на състоянието.

Пример: Игра, където можем да вземаме монети от два края на ред. Ако общият брой е нечетен, първият играч винаги може да вземе по-голямата монета.

3. Инварианти

Търсете величини, които се запазват или променят предвидимо.

Пример: В играта на Ним инвариантът е XOR-ът на купчините.

4. Моделиране като граф

Често е полезно да представим играта като граф на състоянията.

🎯 Примерни задачи

Задача 1: Башки

Имаме число $N$. На ход можем да извадим 1, 2 или 3. Губи който стигне до 0.

bool canWin(int n) {
    // Грънди числата са периодични: 0,1,2,3,0,1,2,3,...
    return (n % 4) != 0;
}

Задача 2: Игра на делене

Имаме число $N$. На ход можем да го разделим на произволен негов делител (различен от 1 и $N$). Губи който не може да направи ход.

map<int, bool> memo;

bool canWin(int n) {
    if (isPrime(n)) return false;  // Прости числа са губещи
    if (memo.count(n)) return memo[n];

    for (int d = 2; d * d <= n; d++) {
        if (n % d == 0) {
            if (!canWin(d) || !canWin(n / d)) {
                return memo[n] = true;
            }
        }
    }

    return memo[n] = false;
}

Задача 3: Комбинирани игри

Имаме три купчини: (3, 4, 5). Можем да играем Ним на всяка купчина.

int result = 3 ^ 4 ^ 5;  // XOR на Грънди числата
if (result != 0) {
    cout << "Първият играч печели" << endl;
} else {
    cout << "Вторият играч печели" << endl;
}

🏁 Заключение

Ключът към задачите от тип "Игра" е да определите: 1. Има ли играта Грънди числа? (Безпристрастна ли е?) $\to$ Използвайте XOR/mex. 2. Има ли малко състояния? $\to$ Използвайте Минимакс/Ретрограден анализ. 3. Има ли симетрия? $\to$ Търсете огледални стратегии.

Обобщение на техниките:

Тип игра	Подход	Сложност	Приложение
Ним и вариации	XOR на купчините	$O(N)$	Класически Ним, Misere Nim, Staircase Nim
Безпристрастни игри	Грънди числа + XOR	$O(States \cdot Moves)$	Композиция на игри
Партизански игри	Минимакс	$O(States)$	Игри с различни ходове за играчите
Сложни игри	Alpha-Beta	$O(b^{d/2})$	Шах, Шашки (с евристика)
Граф игри	ДП/BFS	$O(V + E)$	Игри върху графи

Стъпки при решаване:

Определете типа на играта:
Безпристрастна или партизанска?
Крайна или безкрайна?
Има ли циклични състояния?
Намерете базовите случаи:
Кои позиции са губещи (няма ходове)?
Кои позиции са печеливши директно?
Пресметнете Грънди числа или минимакс:
За безпристрастни игри: използвайте mex
За партизански игри: използвайте минимакс
Комбинирайте подигри (ако има):
XOR на Грънди числата
Оптимизирайте:
Мемоизация
Alpha-beta pruning
Търсене на модел/период

Често срещани грешки:

Забравяне, че и двамата играят оптимално
Обърква не на печеливши/губещи позиции
Неправилно пресмятане на mex
Пропускане на специални случаи (празно състояние, цикли)

Полезни задачи за практика:

CSES - Nim Game I: Класически Ним
CSES - Nim Game II: Вариация на Ним
Codeforces 768C: Jon Snow and his Favourite Number
CodeChef - GAMENEW: Грънди числа
SPOJ - MCOINS: Игра с монети
UVa 10165: Stone Game (Ним вариация)
Codeforces 768B: Code For 1 (Грънди на дърво)

Теорията на игрите изисква практика и интуиция. Започнете с прости задачи и постепенно увеличавайте сложността. Разбирането на Ним е основата - след това всичко друго е приложение и разширение на същите принципи.

Тип игра	Подход	Сложност	Приложение
Ним и вариации	XOR на купчините	\(O(N)\)	Класически Ним, Misere Nim, Staircase Nim
Безпристрастни игри	Грънди числа + XOR	\(O(States \cdot Moves)\)	Композиция на игри
Партизански игри	Минимакс	\(O(States)\)	Игри с различни ходове за играчите
Сложни игри	Alpha-Beta	\(O(b^{d/2})\)	Шах, Шашки (с евристика)
Граф игри	ДП/BFS	\(O(V + E)\)	Игри върху графи