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

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

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

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

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

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

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

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

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

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