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

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

Стратегическими называются игры, в которых никогда не происходит случайных событий. Всё определяют только решения игроков. Благодаря отсутствию случайности, игры этого типа можно проанализировать и найти способ победить. В некоторых случаях можно полностью определить выигрышную стратегию, в других ввиду сложности игры это не удастся, но можно показать, что подобная стратегия существует для одного из игроков. Несмотря на очевидное разнообразие игр такого типа, к ним применимо ограниченное число математических понятий и приемов, которые относятся преимущественно к арифметике (системы счисления и признаки делимости) и геометрии (равновесные ситуации, главным образом, симметрия).

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

Как следует изучив игру, мы задаемся вопросом: какие ходы нужно совершать, чтобы одержать победу в определенной партии? В азартных играх (например, в классической игре «Змеи и лестницы») этот вопрос не имеет смысла, поскольку игроки лишь двигают фишки согласно выпавшим очкам на игральных костях и следуют инструкциям на игровых клетках. Иными словами, здесь нет места для принятия решений, поэтому нет «хороших» или «плохих» игроков. Результат игр подобного типа полностью зависит от случая, поэтому определить какую-либо выигрышную стратегию невозможно. В этом смысле можно сказать, что интересность игры с точки зрения математики равна нулю.

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

Картина времен династии Юань (XIII-XIV века), изображающая трех игроков в го.

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

Возможно, наиболее обширный труд о стратегических играх носит название «Выигрышные стратегии ваших математических игр» в четырех томах (издан в 1982 году). Его авторами являются трое выдающихся математиков XX века: Элвин Берлекэмп (род. в 1940 году), профессор компьютерных наук в Калифорнийском университете в Беркли с 1971 года; Джон Конвей (род. в 1937 году), автор важных работ по теории конечных групп, профессор Кембриджского и Принстонского университетов, создатель игры «Жизнь», моделирующей жизнь клеток; Ричард Гай (род. в 1916 году), почетный профессор университета Калгари. Книга посвящена играм со следующими свойствами: