Недавно мы начали разбирать теорию игр — набор инструментов, которые помогают принимать взвешенные, рациональные и точные решения, а также понимать данные. Вот суть прошлой статьи:
- теория игр — это не только про игры, а про любые ситуации, в которых может что-то происходить, меняться и зависеть от разных факторов;
- игрок — это тот, кто находится в этой ситуации и принимает решения;
- смысл теории игр в том, чтобы понять, как нужно действовать игрокам в разных ситуациях, чтобы получить нужный результат;
- есть много разных видов игр: с полной и неполной информацией, с нулевой, ненулевой суммой и так далее;
- для разных игр — разные стратегии.
Сегодня разберём игру Ним — старую игру, на основе которой математики нашли стратегию выигрыша для многих других игр.
Правила игры Ним
Классические правила игры Ним звучат так:
Есть несколько кучек, в каждой из которых лежит сколько-то камней. За один ход игрок может взять из любой одной кучки любое ненулевое число камней. Игроки берут камни по очереди. Побеждает тот, кто забирает последние камни.
Есть более известный вариант — две кучки, за один ход можно взять 1, 2 или 3 камня, а всё остальное то же самое.
Допустим, у нас 3 кучки, в которых лежат 1, 2 и 3 камня соответственно. Разберём последовательность ходов в этой игре:
- Первый игрок забирает один камень из первой кучки — в них теперь лежит 0, 2 и 3 камня.
- Если второй заберёт все камни из второй кучки, то первый возьмёт всё из третьей и выиграет. По этой причине второму игроку невыгодно брать сразу все камни из второй кучки, и он забирает один — в кучках становится 0, 1 и 3 камня. Теперь та же ситуация у первого игрока, и он не хочет забирать все камни из любой кучки.
- Выигрышный ход: первый игрок берёт два камня из второй кучки. В кучках теперь 0, 1 и 1 камень.
- Второй игрок берёт один камень.
- Первый игрок забирает последний камень и выигрывает.
Обратите внимание на расстановку сил после третьего пункта. Теперь у второго игрока нет выбора: у него есть только две кучки, в каждой из которых лежит по камню. Какой бы камень он ни взял, первый игрок заберёт оставшийся камень из другой кучки и выиграет.
Поиск такой выигрышной стратегии и есть суть теории игр: как сделать так, чтобы ты точно выиграл, а соперник — точно проиграл.
Выигрышный ход
Каждому игроку нужно просчитывать свои ходы так, чтобы действия соперника не влияли на финальный выигрыш. В теории игр это называется выигрышным ходом или выигрышной позицией — что бы ни сделал противник после этого, он всё равно проиграет при нашей правильной стратегии.
В примере выше таким выигрышным ходом у первого игрока было взять два камня из третьей кучки — это гарантировало ему выигрыш при любых действиях второго игрока. Задача теории игр — определить такие выигрышные ходы, если они есть.
Бывает так, что выигрышный ход можно сделать уже в самом начале игры, а потом просто поддерживать перевес в свою сторону.
Как выиграть в игру Ним
Математики, когда изучали эту игру, пришли к такому выводу:
Текущий игрок имеет выигрышную стратегию тогда и только тогда, когда XOR-сумма размеров кучек отлична от нуля. В противном случае текущий игрок находится в проигрышном состоянии.
Это значит, что для выигрыша нужно, чтобы после каждого хода XOR-сумма кучек не была равна нулю. Если этого не сделать, то второй игрок своим ходом обнулит сумму и первый игрок попадёт в ситуацию с нулевым XOR — и это значит, что он совершит проигрышный ход.
Напомним, что XOR — это побитовое ИЛИ, которое работает так:
0 XOR 0 = 0
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0
Для примера рассмотрим ситуацию с ходом первого игрока, когда у него в кучках было 0,1 и 3 камня.
0 в двоичной = 00 в десятичной
1 в десятичной = 01 в двоичной
3 в десятичной = 11 в двоичной
0 XOR 1 XOR 3 = (0 XOR 1) XOR 3 ← в десятичной, переводим в двоичную:
(00 XOR 01) XOR 11 = 01 XOR 11 = 10
Мы получили число, отличное от нуля, — это значит, что игрок в начале своего хода находится в выигрышной позиции. Теперь его задача сделать так, чтобы второй игрок в начале хода оказался в проигрышной позиции, то есть чтобы XOR всех камней в кучках стал равен 0.
XOR возвращает 0, если с обеих сторон от него стоят одинаковые числа. Когда мы посчитали скобки, то увидели, что XOR первых двух кучек даёт 1. Получается, что нам нужно сделать так, чтобы в третьей кучке тоже остался один камень. Мы забираем 2 камня из третьей кучки, и общий XOR всех камней становится нулевым:
0 XOR 1 XOR 1 = 1 XOR 1 = 0
Это значит, что второй игрок начинает свой ход в проигрышной позиции, а мы, если будем придерживаться правильной стратегии, обязательно выиграем.
Где ещё применяется эта стратегия
Стратегия и теория из игры Ним применяется во всех подобных играх, когда несколько игроков меняют состояния нескольких объектов. Главный критерий — чтобы игра точно заканчивалась в какой-то момент, когда остальные игроки не могут сделать свой ход. Например, есть варианты с добавлением камней, перекладыванием из кучки в кучку, объединением камней, ограничением на их количество и так далее — и все они работают под одной и той же стратегии.
Кроме игр, эта стратегия может применяться в обычной жизни. Вот несколько примеров:
Принятие бытовых решений. В жизни часто бывают ситуации, где мы сталкиваемся с какими-то ограничениями и ожидаемыми результатами. Применение концепции выигрышного хода может помочь найти решение, после которого любые внешние действия всё равно приведут к нужному нам результату.
Единственное, что здесь дополнительно нужно учитывать, — в жизни случаются такие форс-мажоры, которые могут полностью изменить ситуацию, и тогда игра начнётся заново, но с другими условиями.
Управление проектами. В проектном менеджменте вместо камней игроки могут управлять рисками, ресурсами и стратегиями, которые помогут достичь желаемых результатов. Для этого в компании вводятся балльные системы оценки влияния каждого фактора. Это помогает построить математическую модель проекта и принимать решения, которые приближают проект к успешному завершению.
Что дальше
В следующей части сделаем игру Ним на компьютере — можно будет играть вдвоём с кем-то или одному против алгоритма.
