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

1. Это игры для двух игроков, делающих ходы поочередно.

2. Это игры, в которых определено одно начальное положение и существует конечное число ходов.

3. Это игры с полной информацией: в любой момент игрокам известны все возможные ходы.

4. Ни в начале игры, ни в процессе выполнения ходов нет места неопределенности.

5. Ход партии не допускает повторения ходов. Тот игрок, который не может совершить ход, проигрывает.

Обложка первого тома книги Берлекэмпа, Конвея и Гая Winning ways for your mathematical plays

Допустим, что некая игра для двух игроков имеет следующие свойства:

1. В любой момент времени каждый игрок обладает всей информацией, чтобы решить, каким должен быть следующий ход.

2. Игроки совершают ходы поочередно.

3. В игре полностью отсутствует элемент неопределенности.

4. Любая партия оканчивается победой одного из игроков после конечного числа ходов.

При этих условиях можно показать, что обязательно существует выигрышная стратегия для одного из двух игроков: первого (игрок А) или второго (игрок Б). Допустим, что выигрышной стратегии для игрока А не существует, иными словами, для игрока Б всегда будет существовать ход, на который у игрока А не найдется достойного ответа, и он проиграет. Это означает, что победит игрок Б. Таким образом, для него существует выигрышная стратегия. Подобные рассуждения лишь доказывают, что в подобных играх всегда существует выигрышная стратегия, но это не означает, что ее будет легко обнаружить.

Для игр, в которых партия не обязательно содержит конечное число ходов, применимость этого утверждения зависит от принятия так называемой аксиомы выбора. Эта известная и противоречивая математическая аксиома утверждает, что для каждого семейства (конечного или бесконечного) непустых непересекающихся множеств существует новое множество, образованное путем выбора определенного элемента из каждого множества этого семейства. С помощью этой аксиомы Банах, Мазур и Улам в 1930 году определили бесконечную игру и доказали, что в ней не существует выигрышной стратегии ни для одного из игроков.

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

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

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

Суть малой стратегической игры для двух игроков, известной под названием Ним, заключается в том, что игроки выкладывают на стол одну или несколько групп фишек и определяют правила, по которым нужно снимать фишки со стола. Цель игры — взять последнюю фишку либо, наоборот, заставить противника взять последнюю фишку. Происхождение этой игры неизвестно. Некоторые считают, что она родом с Востока. Также неясно и происхождение названия. Среди возможных версий — староанглийское слово «ним», означавшее «брать», «красть». Некто очень остроумный заметил, что если применить к слову NIM центральную симметрию, получится слово WIN — «выиграть» в переводе с английского. Как бы то ни было, игре Ним больше ста лет: первый анализ выигрышной стратегии для игр подобного типа был впервые опубликован в 1902 году математиком Гарвардского университета Чарльзом Леонардом Боутоном.

Эта игра приобрела популярность в Европе в 70-е годы XX века благодаря фильму французского режиссера Алена Рене «В прошлом году в Мариенбаде» (1961). Герои фильма несколько раз играют в один из вариантов этой игры. Поэтому версия игры из фильма (она рассматривается далее в этой книге в параграфе «Игра 5») иногда называется Мариенбад — по имени маленького курортного города в Чехии, где происходит действие картины.

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

«Мариенбад» — одна из версий игры Ним.

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

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