Читать «Дилемма заключенного и доминантные стратегии. Теория игр» онлайн - страница 27
Хорди Деулофеу
Из этих примеров становится понятно, что порой игры, кажущиеся совершенно разными, на самом деле полностью эквивалентны. Для этого достаточно иметь возможность преобразовать цель и правила одной игры в цель и правила другой. Однако в других случаях происходит обратное. Игры, которые кажутся полностью аналогичными, в действительности очень отличаются, особенно если разбирать их выигрышные стратегии. Рассмотрим еще одну игру, которая, кажется, полностью совпадает с игрой 1, о которой мы говорили выше.
Нарисуем маргаритку с 11 лепестками и поставим по одной фишке на каждом лепестке. На каждом ходу игрок может брать одну или две фишки, причем две фишки можно брать только с соседних лепестков.
Эта игра очень похожа на первую игру из этой главы, но фишек не 20, а 11. Кажется, что выигрышная стратегия для первого игрока — взять две фишки на первом ходу, затем всегда оставлять число фишек, кратное трем. Однако наложенное ограничение (можно брать не любые две фишки, а только соседние) полностью нейтрализует эту стратегию. Теперь главную роль играет не количество фишек, а их расположение. Фактически исходное число фишек неважно, так как если фишек больше трех, то выигрышная стратегия звучит одинаково для любого числа фишек.
Эта игра уже не относится к семейству игр Ним. Она принадлежит к играм типа Нимбус, и общая стратегия для игр подобного типа неизвестна. Здесь мы рассказали о простейшей из игр такого типа. В нашем конкретном примере можно заметить, что второй игрок всегда будет выигрывать независимо от исходного числа фишек, если будет использовать симметричную стратегию. Попрактиковавшись в этой игре, можно увидеть, что если один из игроков разделит фишки на две одинаковые группы (если все фишки в одной группе находятся рядом, то и во второй они также должны находиться рядом), то будет всегда выигрывать, используя симметричную стратегию. Иными словами, он должен будет повторять для своей группы фишек ходы, которые делает соперник на другой группе фишек, причем положение фишек должно оставаться симметричным. Первый игрок не может разделить фишки на две группы первым ходом. Для этого ему нужно будет взять две фишки, не расположенные рядом друг с другом, что невозможно. Значит, после его хода между фишками образуется промежуток, и второй игрок сможет образовать второй промежуток, разделив фишки на две группы.
«ВАВИЛОН», ИГРА БРУНО ФАЙДУТТИ
Современные абстрактные стратегические игры, несмотря на очевидную простоту, очень сложно анализировать. Хотя для них можно определить существование выигрышной стратегии, найти такую стратегию почти невозможно. Игра «Вавилон» французского автора Бруно Файдутти — наглядный пример подобных игр. На стол кладутся 12 фишек четырех разных цветов, по 3 фишки каждого цвета. Каждый из двух игроков берет одну стопку (изначально все стопки имеют высоту в 1 фишку) и кладет ее поверх другой, соблюдая следующие условия: одну стопку можно поставить на другую, если они имеют одинаковую высоту или же если верхние фишки обеих стопок одинакового цвета. Тот игрок, который не может поставить стопку поверх другой, проигрывает.
Хотя на первый взгляд кажется, будто решение можно найти, рассмотрев частные случаи с последующим обобщением, тщательный компьютерный анализ показывает, что найти стратегию, которую мог бы запомнить и использовать человек, невозможно.
