Теория игр. Симметричная стратегия

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

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

Рассмотрим эту стратегию на примере задачи.

1.  В двух кучах лежит по 20 конфет. Двое игроков, Крош и Ёжик, по очереди берут любое количество конфет, но только из одной кучи. Начинает Крош. Выигрывает тот, кто берет последнюю конфету. Кто из игроков может выиграть, как бы ни играл соперник?

Ответ. Ёжик

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

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

Итак, мы доказали, что у Ёжика всегда есть ход согласно стратегии. Значит, Ёжик не может проиграть. Но игра когда-то закончится (например, не позже, чем через 40 ходов, ведь конфет в сумме всего 40, а каждым ходом берется хотя бы одна конфета). Поэтому кто-то все-таки проиграет. Это точно не Ёжик, поэтому проиграет Крош.

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

Каждый абзац решения последовательно отвечает на свой вопрос: в первом мы привели стратегию, во втором — доказали, что всегда можно сделать ход согласно этой стратегии, в третьем — объяснили, почему в итоге данная стратегия приведет Ёжика к выигрышу. При этом мы никак не пытались предугадывать, как же будет играть Крош, так как нам нужно доказать, что Ёжик может выиграть при любых действиях его соперника.

В этой задаче мы воспользовались симметричной стратегией, то есть стратегией, которая опирается на предыдущий ход оппонента, и в некотором смысле «повторяет» его. Симметрия бывает очень разной, и совсем не обязательно, что симметричной стратегией пользуется второй игрок. Иногда бывает, что на месте первого игрока нужно сначала «подготовиться», а уже начиная со своего второго хода действовать симметрично. Об этом следующая задача.

2.  Двое игроков, Крош и Ёжик, по очереди ставят шахматные ладьи на клетки доски начинает Крош. Запрещено ставить ладью, если ее бьет одна из ранее поставленных. Проигрывает тот, кто не может сделать ход. Кто из игроков может выиграть, как бы ни играл соперник?

Ответ. Крош

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

Пусть до некоторого момента Крош мог ходить симметрично. Тогда перед ходом Ёжика картинка была симметрична относительно центральной клетки. Если Крош смог поставить ладью, то это значит, что и симметричная клетка до хода Ёжика была свободна и не побита ладьей. Осталось заметить, что ладья не может бить ладью, симметричную себе относительно центра, если она не стоит в центральном столбце или центральной строке. Значит, Крош сможет всегда сходить согласно своей стратегии.

Заметим при этом, что игра закончится не позже, чем через 121 ход, то есть когда все клетки будут заняты. Это значит, что кто-то все-таки проиграет. Мы доказали, что это не Крош, значит, проиграет Ёжик.

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