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

Какой из игроков имеет преимущество? Как нужно играть, чтобы всегда выигрывать?

Пересекаем круг.Это стратегическая игра для двух игроков. На листе бумаги нужно нарисовать окружность и обозначить на ней восемь произвольных точек. На каждом ходу игрок соединяет две точки отрезком. Он может соединить любые две точки, кроме уже соединенных, но нарисованный им отрезок не должен пересекать никакой другой отрезок. Игрок, которому не удастся провести такой отрезок, проигрывает.

Какой из игроков имеет преимущество? Что изменится, если изменить начальное число точек?

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

Игровое поле изображено на рисунке 1. Каждый игрок берет единственную фишку, которая изначально расположена в ячейке S, и передвигает ее на соседнюю клетку. При этом он всегда должен двигаться вправо — по горизонтали или по диагонали. Игрок, который поставит фишку в крайнюю клетку М, выигрывает.

Рисунок 1.

Если читатель попытается решить игру сам, то легко увидит, в какие клетки нужно ставить фишку, чтобы победить. Если рассуждать в обратном направлении, то станет понятно, что первый игрок будет всегда выигрывать, если будет ставить фишку в помеченные крестиком клетки. Совсем не очевидно, что эта игра аналогична игре 1 («выигрывает первый»), если не заметить, что допустимые ходы можно интерпретировать как переход на два шага вперед (если мы передвигаем фишку в горизонтальном ряду) или на один шаг вперед (если мы двигаем фишку по диагонали и переставляем ее в другой ряд). Если пронумеровать клетки таким способом, то станет четко видна аналогия между этими играми (рисунок 2).

Рисунок 2.

На игровой доске всего один ряд из шести клеток. На нем расставлены три фишки. На каждом ходу игрок выбирает фишку и передвигает ее вправо на любое количество клеток (минимум на одну и максимум на пять, в крайнюю правую клетку). Цель игры — поставить все фишки в крайнюю правую клетку. Тот, кто ставит в эту клетку последнюю фишку, выигрывает. В одной клетке могут одновременно находиться несколько фишек. Заметим, что эта игра эквивалентна первой рассмотренной нами версии игры Ним (игра 4): каждая фишка соответствует кучке, перенос фишки вправо соответствует взятию фишек из кучки в игре Ним. Когда фишка попадает в крайнюю правую клетку, это равносильно тому, что из кучки в игре Ним взяты все фишки. Рассмотрим еще две игры и проанализируем их эквивалентность.

На стол выкладываются две кучки фишек, например 7 и 5 фишек. Каждый игрок может брать из выбранной кучки любое число фишек (минимум одну). Он также может брать фишки из двух кучек сразу, но в этом случае нужно брать одинаковое число фишек из каждой кучки.

На одну из клеток шахматной доски, например клетку h8, ставится ферзь. Каждый игрок может передвигать ферзя на любое количество клеток влево, вниз или по диагонали (то есть одновременно влево и вниз). Тот, кто поставит ферзя в клетку a1, то есть в левую нижнюю клетку, выигрывает.

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

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