Хорди Деулофеу - Дилемма заключенного и доминантные стратегии. Теория игр

Первая игра под названием цзяньшицзы — это игра типа Ним, в которой можно брать фишки из нескольких кучек. Эта возможность до сих пор не рассматривалась, и она существенно осложняет поиск общей выигрышной стратегии. Анализ возможных ходов во второй игре, «Спасти ферзя», позволяет сразу же увидеть, что эта игра аналогична первой. Ходы ферзя нужно рассматривать как взятие фишек: движение в горизонтальном ряду — это взятие фишек из первой кучки, движение в вертикальном ряду — взятие фишек из второй кучки, движение по диагонали — взятие одинакового количества фишек из обеих кучек сразу.

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

Нарисуем маргаритку с 11 лепестками и поставим по одной фишке на каждом лепестке. На каждом ходу игрок может брать одну или две фишки, причем две фишки можно брать только с соседних лепестков.

Начальная позиция в игре«Маргаритка».

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

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

Современные абстрактные стратегические игры, несмотря на очевидную простоту, очень сложно анализировать. Хотя для них можно определить существование выигрышной стратегии, найти такую стратегию почти невозможно. Игра «Вавилон» французского автора Бруно Файдутти — наглядный пример подобных игр. На стол кладутся 12 фишек четырех разных цветов, по 3 фишки каждого цвета. Каждый из двух игроков берет одну стопку (изначально все стопки имеют высоту в 1 фишку) и кладет ее поверх другой, соблюдая следующие условия: одну стопку можно поставить на другую, если они имеют одинаковую высоту или же если верхние фишки обеих стопок одинакового цвета. Тот игрок, который не может поставить стопку поверх другой, проигрывает.

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

«Вавилон»— игра, созданная Бруно Файдутти.

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

На столе лежит 20 фишек. Каждый из двух игроков своим ходом может взять 1, 3 или 5 фишек. Тот, кто забирает последнюю фишку, выигрывает. Какой из игроков имеет преимущество — тот, кто ходит первым или вторым? Что произойдет, если изменится число фишек? Эта игра является стратегической, как предыдущие, или же отличается от них?

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

Если изначально на столе лежит 20 фишек (или любое другое четное число) и первый игрок берет 1, 3 или 5 фишек (или любое другое нечетное число), то на столе останется нечетное число фишек (если вычесть из четного числа нечетное, получим нечетное). После этого второй игрок также должен взять нечетное количество фишек, и на столе останется четное число фишек (если вычесть из нечетного числа нечетное, получим четное число). Поэтому после хода первого игрока на столе всегда будет оставаться нечетное число фишек, а после хода второго игрока — четное. Так как 0 является четным числом, то побеждать всегда будет второй игрок вне зависимости от того, какие ходы будут совершать оба игрока. Аналогично, если начальное число фишек нечетно, победа всегда будет оставаться за первым игроком.