Камень, ножницы, теорема. Фон Нейман. Теория игр

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

Решка

Орел

Решка

1

-1

Орел

-1

1

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

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

ИГРЫ С НЕПОЛНОЙ ИНФОРМАЦИЕЙ

Первая теорема о минимаксе, доказанная фон Нейманом в 1928 году, может применяться к большинству игр с двумя участниками и нулевой суммой, главное условие — чтобы в каждый момент оба игрока точно знали, на какой стадии находится игра. Эти игры фон Нейман назвал играми с полной информацией. Играя в шахматы, шашки или трис, каждый игрок может видеть расположение фигур после хода. Если же один игрок закроет часть доски, это условие перестанет выполняться, и применить теорему будет нельзя.

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

Очень простая игра, иллюстрирующая эти условия, — классическая «камень, ножницы, бумага». Платежная матрица такой игры, в которой игроки ставят по 1 евро в каждой партии, имела бы такой вид.

В

Камень

Бумага

Ножницы

А

Камень

0

-1

1

Бумага

1

0

-1

Ножницы

-1

1

0

Если, например, А выбирает бумагу, а В — камень, то А выигрывает 1 евро, который, соответственно, проигрывает В. Ничья, когда никто не выигрывает и не проигрывает, соответствует значению 0.

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

Таким образом, вторая теорема о минимаксе гласит, что минимальное из максимальных значений среднего результата игрока А совпадает с максимальным из минимальных значений среднего результата для игрока В.

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

ТЕОРИЯ ИГР И ТОПОЛОГИЯ

Смысл теоремы о минимаксе элементарен, и его можно изложить обычным языком без специальных терминов, однако доказательство теоремы очень далеко от простоты. Сначала фон Нейман пытался доказать теорему, используя только алгебраические методы, но ему не удалось добиться удовлетворительных результатов. Тогда он обратился к топологии.

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