Дилемма заключенного и доминантные стратегии. Теория игр - [10]
Костяшки домино XIX века. Домино — одна из игр, где случай вмешивается лишь на этапе выбора костяшек, в дальнейшем все зависит исключительно от умения игроков.
Стратегическими называются игры, в которых никогда не происходит случайных событий. Всё определяют только решения игроков. Благодаря отсутствию случайности, игры этого типа можно проанализировать и найти способ победить. В некоторых случаях можно полностью определить выигрышную стратегию, в других ввиду сложности игры это не удастся, но можно показать, что подобная стратегия существует для одного из игроков. Несмотря на очевидное разнообразие игр такого типа, к ним применимо ограниченное число математических понятий и приемов, которые относятся преимущественно к арифметике (системы счисления и признаки делимости) и геометрии (равновесные ситуации, главным образом, симметрия).
Понятие выигрышной стратегии
В математике слово «игра» может обозначать как собственно игру, в которой участвует более одного игрока, имеются определенные правила, а цель игры — одержать победу в партии, так и математические развлечения и головоломки. В дальнейшем мы будем говорить об играх, в которых участвуют минимум два игрока. Эти игры также можно разбить на группы разными способами, но с точки зрения математики существует признак, определяющий две большие группы: игры с полной информацией и игры, в которых присутствует элемент неопределенности. В этой главе игры первой группы мы будем называть стратегическими, игры второй группы — азартными.
Как следует изучив игру, мы задаемся вопросом: какие ходы нужно совершать, чтобы одержать победу в определенной партии? В азартных играх (например, в классической игре «Змеи и лестницы») этот вопрос не имеет смысла, поскольку игроки лишь двигают фишки согласно выпавшим очкам на игральных костях и следуют инструкциям на игровых клетках. Иными словами, здесь нет места для принятия решений, поэтому нет «хороших» или «плохих» игроков. Результат игр подобного типа полностью зависит от случая, поэтому определить какую-либо выигрышную стратегию невозможно. В этом смысле можно сказать, что интересность игры с точки зрения математики равна нулю.
Другой крайний случай — игры с полной информацией, в которых в любой момент можно узнать все возможные ходы и их последствия (как минимум в теории) и нет места неопределенности. Из всех подобных игр нам больше всего знакомы шахматы, хотя подобных стратегических игр, как традиционных (го, манкала, шашки, крестики-нолики), так и современных (гекс, ним, реверси, абалон и другие), существует великое множество.
Картина времен династии Юань (XIII-XIV века), изображающая трех игроков в го.
Когда мы говорили об анализе игр этого типа, мы упомянули понятие выигрышной стратегии, то есть множества условий, позволяющих одному из игроков (как правило, речь идет об играх только для двух игроков) определить, как следует действовать в каждый момент времени, учитывая ходы, сделанные противником, чтобы одержать победу вне зависимости от ходов соперника. Существование выигрышной стратегии предполагает, что игра оканчивается победой одного из игроков, но в некоторых играх возможна и ничья, например, как в шахматах. В этом случае нужно вести речь о стратегиях, которые позволяют никогда не проигрывать. Когда стратегическая игра не может завершиться ничьей, можно убедиться, что существует выигрышная стратегия для первого или второго игрока, но это не означает, что подобную стратегию можно будет точно определить: игра может быть весьма сложной.
Возможно, наиболее обширный труд о стратегических играх носит название «Выигрышные стратегии ваших математических игр» в четырех томах (издан в 1982 году). Его авторами являются трое выдающихся математиков XX века: Элвин Берлекэмп (род. в 1940 году), профессор компьютерных наук в Калифорнийском университете в Беркли с 1971 года; Джон Конвей (род. в 1937 году), автор важных работ по теории конечных групп, профессор Кембриджского и Принстонского университетов, создатель игры «Жизнь», моделирующей жизнь клеток; Ричард Гай (род. в 1916 году), почетный профессор университета Калгари. Книга посвящена играм со следующими свойствами:
1. Это игры для двух игроков, делающих ходы поочередно.
2. Это игры, в которых определено одно начальное положение и существует конечное число ходов.
3. Это игры с полной информацией: в любой момент игрокам известны все возможные ходы.
4. Ни в начале игры, ни в процессе выполнения ходов нет места неопределенности.
5. Ход партии не допускает повторения ходов. Тот игрок, который не может совершить ход, проигрывает.
Обложка первого тома книги Берлекэмпа, Конвея и Гая Winning ways for your mathematical plays
Допустим, что некая игра для двух игроков имеет следующие свойства:
1. В любой момент времени каждый игрок обладает всей информацией, чтобы решить, каким должен быть следующий ход.
2. Игроки совершают ходы поочередно.
3. В игре полностью отсутствует элемент неопределенности.
4. Любая партия оканчивается победой одного из игроков после конечного числа ходов.
При этих условиях можно показать, что обязательно существует выигрышная стратегия для одного из двух игроков: первого (игрок А) или второго (игрок Б). Допустим, что выигрышной стратегии для игрока А не существует, иными словами, для игрока Б всегда будет существовать ход, на который у игрока А не найдется достойного ответа, и он проиграет. Это означает, что победит игрок Б. Таким образом, для него существует выигрышная стратегия. Подобные рассуждения лишь доказывают, что в подобных играх всегда существует выигрышная стратегия, но это не означает, что ее будет легко обнаружить.
