Теория игр

  • Пример игры
  • Выигрышные и проигрышные состояния
  • Игра как граф
  • Результат игры
  • Ретроанализ*

Пример игры

Условие: Есть два игрока и N спичек. Они по очереди берут 1, 2 или 3 спички. Если осталось 0 спичек и игрок походить не может - он проиграл. Кто победит при оптимальной игре?

Как решать любые такие задачи? Конечно, нужно посмотреть на маленьких числах и применить динамическое программирование!

Задание

Посчитайте, кто выиграет при оптимальной игре для N от 0 до 8. Попытайтесь заметить закономерность.

Решение

Состоянием динамики в данном случае будет win[n] - кто выиграет, если спичек n. Если первый, то win[n] = 1, если второй, то win[n] = 2. Посчитаем для первых нескольких:

  • win[0] = 2 (первый проигрывает, так как нечего брать)
  • win[1] = 1 (первый выиграет, взяв единственную спичку)
  • win[2] = 1 (первый выиграет, взяв все две спички)
  • win[3] = 1 (первый выиграет, взяв все три спички)
  • win[4] = 2 (первый проигрывает, так как сколько бы он ни взял, останется 1, 2 или 3 спички, которые может взять второй и победить)
  • win[5] = 1 (первый берет одну, остаётся 4 спички, с которыми, как мы только что доказали, второй проиграет)
  • win[6] = 1 (первый берет две)
  • win[7] = 1 (первый берет три)
  • win[8] = 2 (сколько бы ни брал первый, останется 5, 6 или 7, и второй выиграет)

Здесь можно заметить простое правило: если N делится на 4, то первый проиграет, а иначе выиграет. Причем татика у первого простая - нужно просто уменьшать каждым своим ходом N так, чтобы оно делилось на 4. Тогда второй игрок по-любому сделает так, чтобы снова не делилось, и два игрока будут так чередовать. Но случай N = 0 попадется именно после хода первого игрока, так как 0 делится на 4.

Так мы придумали и формулу для N, определяющую кто выиграет, и даже придумали, как ходить, чтобы победить. Но если немного изменить игру (например, можно брать 1, 3, 4 или 17 спичек), то такая стратегия уже не будет работать. Нужно придумать более универсальное решение. Мы придумали состояния динамики, но вместо перехода динамики мы заметили формулу. Давайте придумаем переход динамики!

Выигрышные и проигрышные состояния

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

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

А выигрышным состоянием назовем состояние, в котором игрок, начинающий в нем, имеет стратегию, при которой он в любом случае выиграет.

По сути, ранее описанные win[n] = 1 - это и есть выигрышные состояния, а win[n] = 2 - это проигрышные состояния.

Заметим, что 0 спичек - это точно проигрышное состояние, это и есть база динамики. Также заметим, что

  • Если из состояния есть хотя бы один переход в проигрышное состояние, то состояние выигрышное
  • Если из состояния все переходы ведут в выигрышные состояния, то состояние проигрышное

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

Вот мы и придумали переход для нашей динамики!

In [0]:
win = [None] * 10
win[0] = 2
for i in range(1, len(win)):
    win[i] = 2 # состояние по умолчанию проигрышное
    for k in [1, 2, 3]:
        if i - k >= 0 and win[i - k] == 2:
            win[i] = 1 # но если есть переход в проигрышное, то оно выигрышное
print(win)
[2, 1, 1, 1, 2, 1, 1, 1, 2, 1]

Задание

Решите 3 первые задачи в этом контесте:

https://informatics.msk.ru/mod/statements/view3.php?id=33386

Игра как граф

В общем случае состояния игры могут представлять из себя гораздо более сложную структуру, чем "N спичек". А именно, представим себе ориентированный граф:

  • Вершины - это состояния игры
  • Ребра - это переходы между ними
  • В одной из вершин стоит фишка - текущее состояние игры
  • Два игрока по очереди двигают фишку по одному из ребер.
  • Кто не может двигать фишку - тот проиграл

На таком графе так же легко считать проигрышные и выигрышные состояния. А именно, вершины, из которых не выходят ребра - очевидно проигрышные. Вершины с ребрами в проигрышные - это выигрышные. А вершины с ребрами только в выигрышные - это проигрышные.

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

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

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

Задание

Посчитайте у каждого состояние в этом графе-игре, выигрышное оно или нет. А также найдите для каждой вершины, куда оттуда идти оптимальнее всего:

Решение

Расмотрим такие игры:

  1. Есть шахматная доска NxM, в верхней правой клетке стоит ферзь. Два игрока по очереди двигают его либо вниз, либо влево, либо вниз-влево по диагонали на сколько угодно клеток. Проигрывает тот, кто не может ходить.
  2. Крестики-нолики на доске 3x3.
  3. Шахматы.

Задание

Придумайте, как представить эти игры в виде графов. Что является состоянием игры? Являются ли игры ациклическими?

Решение

  1. Состояние игры - это пара (x, y) - координаты ферзя. Есть ходы из (x, y) в (x - k, y), (x, y - k) и (x - k, y - k), где k - любое. Игра ациклическая - после каждого хода обе координаты не возрастают, и хотя бы одна убывает.
  2. Состояние игры - это доска с уже поставленными крестиками и ноликами. По доске однозначно считается, кто ходит следующий. Во все возможные доски, в которые можно походить, в графе стоит ребро. Игра ациклическая - после каждого хода заполняется езе одна клетка.
  3. Состояние игры - это пара (доска с фигурами, чей сейчас ход). Особенность шахмат в том, что здесь бывают ничьи. Можно расширить нашу модель графа, введя ничейные вершины. А можно поставить во всех ничейных вершинах петлю - если ты попал в нее, то ты будешь вечно ходить по петле, и в соответствии с нашим старым определением, это действительно ничья.

    Еще шахматы циклические - игроки могут вернуться в то же положение. Ха, вообще-то нет! Есть правило, согласно которому одно положение не может повторяться более 3 раз. Поэтому можно сделать состоянием игры (доска с фигурами, чей сейчас ход, статистика о том сколько раз встретилось каждая доска). При этом, если какая-то доска встретилась 3 раза, объявляем ничью. Тогда игра становится ациклической - статистика всегда в одной доске возрастает. При всем огромном числе возможных досок шахматы - игра конечная. Досок конечное число, и на каждой можно побывать не более 6 раз (3 раза с ходом белым, 3 раза с ходом черных), это все еще конечное число. А значит, в шахматах точно существует либо выигрышная стратегия для белых, либо для черных, либо ничейная у обоих.

Задание

Решите 4, 5 и 6 задачи в этом контесте:

https://informatics.msk.ru/mod/statements/view3.php?id=33386

В них самое сложное - придумать, чем является состояние игры. Также рекомендуем использовать ленивую динамику, чтобы не думать о том, в каком порядке проходить состояния.

Результат игры

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

Очень часто рассматриваются игры с нулевой суммой: A + B = 0, то есть сколько монет выиграл один, столько проиграл второй

Можно считать, что в каждой вершине-листе (то есть откуда некуда идти) написан результат игры: первое число получает тот, кто должен ходить из листа, а второе число должен писать тот, кто туда пришел.

Для такой модели существует аналог выигрышных-проигрышных позиций. А именно, давайте в win[x] хранить пару - лучший результат первого игрока, если он начнет играть с этой вершины, и сколько в этом случае получит второй игрок. Если это игра с нулевой суммой, то второй игрок потеряет ровно столько, сколько получит первый, в этом случае можно не хранить пару, а только выигрыш первого.

Тогда такая динамика пересчитывается просто - если ты хочешь узнать результат игры в вершине X, то нужно просто максимизировать выигрыш второго игрока во всех состояниях, куда можно прийти из X. При этом результат первого игрока становится результатом второго игрока в вершине X. Конечно, при этом писать топологическую сортировку не надо, достаточно считать динамику прямо ленивой динамикой (DFS по графу игры).

Задание

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

Решение

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

Задание

Решите 2 последние задачи в этом контесте:

https://informatics.msk.ru/mod/statements/view3.php?id=33386

Оптимизации ретроанализа*

Рассмотрим какую-нибудь сложную игру. Например, шахматы или крестики-нолики. Мы уже обсудили, что так как это конечные ациклические игры, в них однозначно определен победитель при оптимальной игре. Достаточно просто запустить рекурсивную функцию с функцией best_turn(board, player), которая возращает пару (turn, game_result) - лучший ход игрока player на доскеboard, причем в оптимальном случае игра заканчивается с результатом result. Причем с помощью ленивой динамики можно сохранять результат, чтобы не перебирать одну доску несколько раз. Этот алгоритм, вкратце описанный ранее, еще называют ретроанализ.

Понятна проблема такого подхода: алгоритм работает очень долго, особенно в случае с играми типа шахмат.

Есть несколько оптимизаций ретроанализа:

1) Перебирать только на $K$ ходов вперед.

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

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

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

2) Альба-бета-отсечения

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

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

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

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

Задание

Вы может написать стратегию для бота, который будет играть в крестики-нолики. Код-шаблон и описание того, как это делать, можно посмотреть на странице ЛКШ.2016.Зима.C'+. Только не надо слать писать Андрею Гейну вопросы, спустя 3 года он этого вряд ли этого ожидает :)