games-on-graphs.md

Теория игр

Начнём с самого баянного примера математической игры, который можно вспомнить:

На столе лежит кучка из $n$ спичек. Два игрока по очереди берут спички из кучки, разрешается взять одну, две или три спички. Тот, кто берет последнюю спичку, выигрывает. Требуется определить, кто выигрывает при оптимальной игре обоих игроков.

Все задачи такого типа решаются одним и тем же способом: посмотреть на решения для маленьких чисел и применить динамическое программирование. В данном случае состоянием динамики будет $f_k$ — выиграет ли первый игрок, если спичек сейчас $n$, и ход принадлежит ему. Пересчитывать её нужно так:

$$ f_k = \lnot f_{k-1} \lor \lnot f_{k-2} \lor \lnot f_{k-3} = \lnot (f_{k-1} \land f_{k-2} \land f_{k-3}) $$

то есть должен найтись переход в какое-то состояние динамики, которое является проигрышным (или, что эквивалентно, не должно быть пере динамики должны вести в проигрышные состояния).

Примечание. Конечно, здесь не нужна была никакая динамика, и ответ зависит только от того, делится ли $n$ на 4, но мы всё равно рассмотрим этот пример в педагогических целях.

Игры на графах

В общем случае состояния игры могут представлять из себя гораздо более сложную структуру, чем «$n$ спичек».

Любую игру можно описать в виде графа (возможно, бесконечного) состояний игры, между которыми есть переходы. Игроки поочередно выбирают, по какому переходу пройти. Некоторые состояния в этом графе помечены как терминальные

Состояние называется выигрышным, если игрок, начинающий в нём, побеждает, и проигрышным в противном случае. В графе могут быть циклы, и иногда обоим игрокам выгодно по ним ходить. Например, в шахматах бывают ситуации, когда выгодно повторение ходов (сама игра при этом всё равно не может длиться бесконечно, потому что троекратное повторение позиции приводит к ничье — подобные правила есть в большинстве стратегических игр). Такие вершины — в которых оптимальной стратегией будет хождение по циклу — назовём ничейными.

Подобные игры — где чтобы сделать одному игроку лучше, нужно сделать другому на столько же хуже — называют играми с нулевой суммой (почему такое название и что такое игры с ненулевой суммой — ниже прочитаете). Они почти всегда решаются определенным видом динамики на графе, который называется ретроанализом.

Ретроанализ

Обобщим пример со спичками и сформулируем критерии выгрышности и проигрышности:

• Вершина проигрышная — если все её переходы ведут в выигрышные вершины.
• Вершина выигрышная — если из неё есть переход в проигрышную вершину.
• Вершина ничейная — если она не выиграшная, и не проигрышная (у неё есть хотя бы один переход в другую ничейную и, возможно, сколько-то переходов в выигрышные).

Пользуясь этими критериями, можно разработать общий алгоритм: проверять все вершины на соответствие этим критериям и обновлять их статусы, пока вершины с неизвестным статусом не кончатся.

Корректность. Рассмотрим случай ациклической игры. Он проще: раз циклов нет, значит нет и ничейных вершин.

Рассмотрим граф неизвестных вершин $U$. Будучи подграфом исходного, он тоже ациклический, а значит должна быть вершина $v$, у которой нет исходящих рёбер в $U$ — если рёбра есть, то они ведут в вершины с известным состоянием. Значит, на данном этапе мы и для вершины $v$ определим выигрышность, которая будет зависеть только от того, ведут ли эти рёбра в какое-то проигрышное состояние.

Вернёмся к общему случаю — когда в графе могут быть циклы. Наш алгоритм не пометит ничейные вершины ничейными, потому что здесь возникает проблема курицы и яйца — изначально ничейных терминальных вершин нет, и вершину нельзя по определению пометить ничейной. Но выясняется, что алгоритм менять не надо — ничейными можно просто объявить все вершины, выигрышность которых определить не удалось.

Почему так? Пусть мы провели сколько-то итераций алгоритма, и он остановился, когда в графе остались ещё какие-то вершины с невыясненным состоянием, которые образуют подграф $U$. В этом графе ни одна вершина не ведет в проигрышную — иначе она была бы помечена выигрышной, и алгоритм пошел бы дальше. Также, нет вершин без исходящих рёбер в $U$ — иначе такая вершина была бы помечена проигрышной. Получается, оптимальной стратегией в этом подграфе будет всегда оставаться в нём — выходы есть только в выигрышные вершины — и, значит, все вершины в нём ничейные.

Асимптотика. Можно добавить все терминальные вершины в очередь, и поддерживать в ней список вершин, у которых мы определили выигрышность, но ещё не обработали.

• При обработке проигрышной вершины, надо пометить выигрышными все вершины, у которых есть ребро, ведущее в текущее (для этого нам надо хранить обратный граф).
• При обработке выигрышной вершины, надо удалить все ребра в обратном графи и пометить проигрышными все вершины, у которых больше не осталось рёбер в неизвестные вершины, и которые ещё не были помечены раньше.

Асимптотика составит $O(n + m)$, как и у любого bfs-а.

vector<int> g[maxn], t[maxn]; // списки смежности прямого и обратного графа
int cnt[maxn]; // счётчик исходящих рёбер

enum StatusType { win, loss, unknown };
StatusType status[maxn]; // выгрышность вершины;
// по умолчанию все кроме терминальных считаются unknown
// те, кто в итоге остаются unknown -- ничейные

queue<int> q = {/* нужно заранее добавить сюда все терминальные вершины*/};

while (!q.empty()) {
    int v = q.front();
    q.pop();
    for (int u : t[v]) {
        cnt[u]--; // удаляем это ребро
        if (status[v] == unknown) {
            // из u есть ребро в проигрышную -- значит она выигрышная
            if (status[v] == loss)
                status[u] = win;
            // все ребра u ведут в выигрышные вершины -- значит она проигрышная
            if (status[v] == win && cnt[u] == 0)
                status[u] = loss;
            // если после проверок у вершины определилась выигрышность, то её можно добавить в очередь
            if (status[v] != unknown)
                q.push(u);
        }
    }
}

Как обычно это бывает с динамиками, иногда проще написать рекурсивный подсчёт динамики, а не итеративный. Однако это работает только с ациклическими динамиками, а в общем графе могут быть циклы. Тем не менее, именно рекурсивную реализацию ретроанализа мы будем считать каноничной, потому что она в дальнейшем позволит делать некоторые отсечения и оптимизации:

StatusType dfs(int v) {
    if (status[v] != unknown)
        return status[v];
    status[v] = loss;
    // изменим статус, когда найдём переход в проигрышную вершину
    for (int u : g[v])
        if (dfs(u) == loss)
            status[v] = win;
    return status[v];
}

TODO: можно ли здесь циклы учесть?

Минимаксные игры

Иногда у нас более богатая градация терминальных состояний, чем просто проигрышные и выигрышные. Такие игры в общем случае называются минимаксными — в терминальных вершинах могут быть записаны произвольные числа, задача первого игрока — придти в наибольшее, а второго — в наименьшее. Игроков будем называть Макс и Мин соответственно.

Типичный граф минимаксной игры выглядит следующим образом:

В не-листовых вершинах записаны значения игр в поддеревьях при оптимальной игре обоих соперников.

Решение таких задач ничем принципиально не отличается от ретроанализа, только теперь у нас «хорошесть» вершины — это минимум / максимум из переходов в детей.

Ретроанализ для больших графов

Иногда наша игра сложная, и все её состояния не вмещаются в память — например, шахматы или го. Это конечные ациклические игры, и в них однозначно определен победитель при оптимальной игре, которого в теории можно найти ретроанализом. Однако возникает проблема: алгоритм работает очень долго.

Для некоторых игр титаническими трудами были посчитаны исходы во всех возможных состояниях (шашкки, для шахмат — только база эндшпилей).

Ретроанализ нужно оптимизировать.

Ограничение перебора

Для этого надо идти по состояниям графа BFS-ом, а не DFS-ом, и останавливаться в момент, когда пройдено $K$ ходов. При этом возникает только одна проблемы: как понять результат игры на рассматриваемой доске через $K$ ходов, ведь игра еще не закончена. Для этого надо придумать приближенную функцию которая численно оценивает, насколько первый игрок выигрывает.

Для шахмат можно просто присвоить каждой фигуре сколько-то баллов и считать для каждого игрока эту сумму, а за функцию взять разность сумм у первого и второго игрока. Тогда если у первого игрока есть стратегия, с помощью которой он за $K$ ходов гарантированно ест ферзя, не теряя много своих фигур, ретроанализ это обнаружит.

Ясно, что это дает существенное ускорение по времени: можно подобрать $K$ так, чтобы время было достаточно маленьким. А если есть какой-то определенный лимит по времени, можно прекращать перебирать, когда закончится этот лимит. Но ход, который предлагает ретроанализ с такой оптимизацией, конечно, перестает быть оптимальным. Впрочем, оптимальную стратегию для шахмат пока найти не смогли (а для шашек, кстати, нашли).

Мемоизация позиций

В некоторые позиции можно придти более чем одним способом, а также есть группы позиций, про которые нам заранее известно, что их исход один и тот же (например, симметричные позиции в крестиках-ноликах). Нам не обязательно обрабатывать каждую из них каждый раз, когда попадём в неё — эффективнее работает .

Для шахмат (и не только) был разработан интересный способ хэширования. Вместо полиномиального хэша. Для каждой пары

Альфа-бета отсечение

Рассмотрим стандартный минимакс. На картинке в не-листовых вершинах написан выигрыш игрока, который ходит из неё первым.

На картинке изображена игра с нулевой суммой: в ней сумма выигрыша первого и второго игрока равна нулю, поэтому на картинке в вершине написан только выигрыш того игрока, который ходит из нее первым.

Идею оптимизации рассмотрим на частном примере: мы перебираем куда идти из состояния $X$ (например, корень). Мы уже зашли в первого и второго сына, увидели, что если пойти в первого, то выигрыш второго игрока составит -3, а если во второго, то выигрыш составит -6. Наша задача - минимизровать его выигрыш, так как это максимизирует наш выигрыш. Пока что лучшим ходом из корня дерева является второй сын, и выигрыш будет равен 6.

Давайте зайдем в третьего сына, назовем его $Y$, вдруг там второй сможет набрать больше, чем -6. Зайдем в первого сына $Y$, обработаем полностью и заметим, что при таком ходе второй при оптимальной игре получит -5. Утверждается, что тогда ход во второго сына $Y$ можно вообще не проверять. Почему? Потому что уже понятно, что если пойти из корня $X$ в вершину $Y$, то выигрыш второго будет хотя бы -5 (а возможно даже больше), а значит выигрыш первого будет не более, чем 5. Но ход во второго сына $X$ уже дает 6, что больше, и рассматривать вершину $Y$ далее бессмысленно, мы в нее уже точно не пойдем.

Отсечение таких лишних веток и называется альфа-бета-отсечением. Понятно, что оно может значительно ускорить перебор, так как мы выкидываем целые ветки перебора, и при этом эта оптимизация все еще находит оптимальный ход, в отличие от прошлой оптимизации.

Monte-Carlo Tree Search

Игры с ненулевой суммой

Теория Шпрага-Гранди

Рассмотрим игру «ним»: даны $n$ кучек, в каждой из них по несколько камней. За один ход игрок может выбрать кучку и выбросить оттуда любое ненулевое число камней. Проигрыш наступпает, когда ходов больше не осталось, то есть когда все кучки пустые.

Немного переформулируем условие. Состояние нима однозначно описывается неупорядоченным набором неотрицательных чисел — как-нибудь пронумеруем их и обозначим количество камней в $i$-й как $a_i$. Теперь, за один ход разрешается строго уменьшить любое из чисел. Терминальное состояние — когда все числа стали нулями.

Теорема. Состояние игры выигрышное тогда и только тогда, когда xor-сумма $ S = a_1 \oplus a_2 \oplus \ldots \oplus a_n $ размеров кучек отлична от нуля.

Доказательство проведём по индукции. Для терминального состояния xor-сумма равна нулю, и оно действительно проигрышное — база доказана. Теперь докажем переходы:

• Из состояния с нулевой xor-суммой все переходы ведут в выигрышные состояния, то есть в состояния с ненулевой суммой. В самом деле, достаточно убрать сколько угодно спичек из любой кучки — xor сумма изменится с нуля на $a_i \oplus b_i $, где $b_i < a_i$ — это число камней в $i$-й кучке после нашего действия.
• Второй переход сложнее — нужно показать, что если xor-сумма ненулевая, то всегда существует такой $b_i < a_i$, что xor-сумма станет нулевой, то есть $S \oplus a_i \oplus b_i = 0$. Для этого посмотрим на старший взведенный бит $S$ и возьмем любой $a_i$, у которого этот бит тоже взведен. Такой $a_i$ найдётся хотя бы один — свойства ксора говорят, что их должно быть нечетное число. Из предыдущего равнства вытекает, что искомый $b_i$ равен $S \oplus a_i$, и выясняется, что это корректный новый размер кучки, то есть $b_i < a_i$. Почему так? Потому что все старшие биты в выражении остались нетронутыми, $k$-й бит изменился на единицу, а что происходило с дальнейшими битами нам не важно, потому что эти изменения точно не больше, чем $2^k$.

Автор любит конструктивные доказательства — из них сразу же вытекают алгоритмы, которые остается только реализовать. Получается, что оптимальная стратегия: посчитать xor-сумму всех $a_i$, найти такой $a_i$, у которого старший бит взведен, и заменить его на $S \oplus a_i$.

Каждый раз, перед тем, как рассказать про решение нима, автор просит кого-нибудь непосвященного сыграть против него в ним, и со скрежетом ксорит в уме несколько бинарных чисел, пока все не убедятся в верности теории.

Зачем это надо? Есть много игр, в которых присутствует какой-то подобный цугцванг (шахматный термин — когда у соперника кончились хорошие ходы, и он бы просто стоял на месте, но правила это запрещают). Выясняется, что они все эквивалентны ниму — их графы с точки зрения выигрышности суммы отдельных игр работают также, как графы нима. Но чтобы доказать это, нам потребуется немного получше разобраться в том, как ним устроен.

Ним с увеличениями

Пусть у нас

Эквивалентность игр ниму

Игры с неполной информацией

Это называется минимаксоной теоремой, а более общее утверждение доказал Джон Нэш. Все это состояние называется равновесием Нэша, или эквилибриумом. Эквилибриум существует и в играх с большим числом игроков.

Любое доказательство использует слишком большое количество матана, чтобы его включать в блог про программирование, так что автор приводить его не будет.

Вы могли знать это имя по «Играм Разума». Не описано, чем он занимался, и какой вклад это внесло.

Дилемма заключенного

Камень-ножницы-бумага

Покер

Рассмотрим такую у