«Камень-ножницы-бумага» и теория игр

https://www.quantamagazine.org/the-game-theory-math-behind-rock-paper-scissors-20180402/
  • Перевод
image

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

В 1950-х математик Джон Нэш доказал, что в любом виде игры с конечным количеством игроков и конечным количеством вариантов (таком, как «камень-ножницы-бумага») всегда существует смешение стратегий, при которой ни один игрок не может показать результатов лучше изменением только собственной стратегии. Теория таких устойчивых наборов стратегий, которые называются "равновесиями Нэша", совершила революцию в области теории игр, изменила направление развития экономики и способы изучения и анализа всего — от политических договоров до сетевого трафика. А ещё она позволила Нэшу получить в 1994 году Нобелевскую премию.

Так как же выглядит равновесие Нэша в игре «камень-ножницы-бумага»? Давайте смоделируем ситуацию, в которой есть вы (Игрок A) и ваш противник (Игрок B), снова и снова играющие в игру. В каждом раунде победитель получает очко, проигравший теряет очко, а ничья засчитывается как ноль очков.

Предположим, Игрок B выбрал (глупую) стратегию выбора в каждом раунде бумаги. Через несколько раундов побед, проигрышей и ничьих вы скорее всего заметите его систему и выработаете выигрышную контрстратегию, выбирая в каждом раунде ножницы. Давайте назовём этот набор стратегий (ножницы, бумага). Если в результате каждого раунда получаются ножницы против бумаги, то вы проложите себе дорогу к идеальной победе.

Но Игрок B вскоре замечает недальновидность этого набора стратегий. Увидев, что вы выбираете ножницы, он переключается на стратегию постоянного выбора камня. Этот набор стратегий (ножницы, камень) начинает выигрывать для Игрока B. Но, разумеется, теперь вы перейдёте к бумаге. На протяжении этих этапов игры Игроки A и B используют то, что называется «чистыми» стратегиями — единственные стратегии, выбираемые и реализуемые постоянно.

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

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

Какова же разумная смешанная стратегия для «камня-ножниц-бумаги»? Интуитивно кажется разумным, что это «выбирать камень, бумагу или ножницы с равной вероятностью». Такая стратегия записывается как $(\frac {1}{3},\frac {1}{3},\frac {1}{3})$. Это означает, что камень, ножницы и бумага выбираются с вероятностью $\frac {1}{3}$. Является ли эта стратегия хорошей?

Предположим, что стратегия вашего противника имеет вид «всегда выбирать камень». Это чистая стратегия, которую можно обозначить как $(1,0,0)$. Какими будут результаты игры при наборе стратегий $(\frac {1}{3},\frac {1}{3},\frac {1}{3})$ для Игрока A и $(1,0,0)$ для Игрока B?

Чтобы получить более чёткую картину игры, мы построим таблицу, в которой будут показаны вероятности каждого из девяти возможных результатов каждого раунда: камень у A, камень у B; камень у A, бумага у B; и так далее. В приведённой ниже таблице верхняя строка обозначает выбор Игрока B, а левый столбец — выбор Игрока A.

A | B К Б Н
К $\frac {1}{3}$ 0 0
Б $\frac {1}{3}$ 0 0
Н $\frac {1}{3}$ 0 0

Каждый элемент таблицы обозначает вероятность пары выбранных вариантов для каждого раунда. Это просто произведение вероятностей того, что каждый из игроков сделает соответствующий выбор. Например, вероятность того, что Игрок A выберет бумагу, равна $\frac {1}{3}$, а вероятность того, что Игрок B выберет камень, равна 1, то есть вероятность (камень у A, камень у B) равна $\frac {1}{3} \times 1=\frac {1}{3}$. Но вероятность (бумага у A, ножницы у B) равна $\frac {1}{3} \times 0=0$, поскольку вероятность выбора Игроком B ножниц равна нулю.

Как же проявит себя Игрок A при своём наборе стратегий? Игрок A выиграет одну треть времени (бумага, камень), проиграет в одну треть времени (ножницы, камень) и в одну треть времени сыграет вничью (камень, камень). Мы можем вычислить количество очков, которые в среднем получит Игрок A в каждом раунде, вычислив сумму произведения каждого результата на соответствующую вероятность:

$\frac {1}{3}(1)+\frac {1}{3}(0)+\frac {1}{3}(-1)=0$


Таким образом, в среднем Игрок A будет получать по 0 очков за раунд. Вы будете выигрывать, проигрывать и играть вничью с одинаковой вероятностью. В среднем, количество побед и поражений уравновесят друг друга, и по сути, оба игрока придут к ничьей.

Но как мы уже говорили, вы можете улучшить свои результаты, изменив свою стратегию, предполагая, что противник не будет менять свою стратегию. Если вы перейдёте к стратегии (0,1,0) («каждый раз выбирать бумагу»), то таблица вероятностей будет выглядеть так:
A | B К Б Н
К 0 1 0
Б 0 0 0
Н 0 0 0

В каждом раунде вы будете заворачивать в свою бумагу камень противника и получать за каждый раунд по одному очку.

То есть эта пара стратегий — $(\frac {1}{3},\frac {1}{3},\frac {1}{3})$ для A и $(1,0,0)$ для B — не является равновесием Нэша: вы, как Игрок A, можете улучшить свои результаты, изменив стратегию.

Как мы увидели, чистые стратегии, похоже, не ведут к равновесию. Но что, если ваш противник попробует использовать смешанную стратегию, например $(\frac {1}{2},\frac {1}{4},\frac {1}{4})$? Это стратегия «в половине случаев выбираем камень; бумаге и ножницам достаётся по четверти случаев». Вот, как будет выглядеть таблица вероятностей:
A | B К Б Н
К $\frac {1}{6}$ $\frac {1}{12}$ $\frac {1}{12}$
Б $\frac {1}{6}$ $\frac {1}{12}$ $\frac {1}{12}$
Н $\frac {1}{6}$ $\frac {1}{12}$ $\frac {1}{12}$

А вот таблица «вознаграждений» с точки зрения Игрока A; это количество очков, получаемых Игроком A в каждом из результатов.
A | B К Б Н
К 0 -1 1
Б 1 0 -1
Н -1 1 0

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

$\frac {1}{6}(0)+\frac {1}{12}(-1)+\frac {1}{12}(1)+\frac {1}{6}(1)+\frac {1}{12}(0)+\frac {1}{12}(-1)+\frac {1}{6}(-1)+\frac {1}{12}(1)+\frac {1}{12}(0)=0$


В среднем Игрок A снова за раунд зарабатывает 0 очков. Как и раньше, этот набор стратегий, $(\frac {1}{3},\frac {1}{3},\frac {1}{3})$ для A и $(\frac {1}{2},\frac {1}{4},\frac {1}{4})$ для B, в результате приводит к ничьей.

Но как и раньше, вы, как Игрок A, можете улучшить свои результаты, сменив стратегию: против стратегии Игрока B $(\frac {1}{2},\frac {1}{4},\frac {1}{4})$, Игрок A должен выбрать $(\frac {1}{4},\frac {1}{2},\frac {1}{4})$. Вот таблица вероятностей:

A | B К Б Н
К $\frac {1}{8}$ $\frac {1}{16}$ $\frac {1}{16}$
Б $\frac {1}{4}$ $\frac {1}{8}$ $\frac {1}{8}$
Н $\frac {1}{8}$ $\frac {1}{16}$ $\frac {1}{16}$

а вот итоговый результат для A:

$\frac {1}{8}(0)+\frac {1}{16}(-1)+\frac {1}{16}(1)+\frac {1}{4}(1)+\frac {1}{8}(0)+ \frac {1}{8}(-1)+\frac {1}{8}(-1)+\frac {1}{16}(1)+\frac {1}{16}(0)=\frac {1}{16}$


То есть этот набор стратегий — $(\frac {1}{4},\frac {1}{2},\frac {1}{4})$ для A и $(\frac {1}{2},\frac {1}{4},\frac {1}{4})$ для B — даёт в среднем Игроку A по $\frac {1}{16}$ очка за раунд. После 100 игр Игрок A будет впереди на 6,25 очка. У Игрока A есть большой стимул к изменению стратегии. То есть набор стратегий $(\frac {1}{3},\frac {1}{3},\frac {1}{3})$ для A и $(\frac {1}{2},\frac {1}{4},\frac {1}{4})$ для B тоже не является равновесием Нэша.

Но теперь давайте рассмотрим пару стратегий $(\frac {1}{3},\frac {1}{3},\frac {1}{3})$ для A и $(\frac {1}{3},\frac {1}{3},\frac {1}{3})$ для B. Вот соответствующая таблица вероятностей:
A | B К Б Н
К $\frac {1}{9}$ $\frac {1}{9}$ $\frac {1}{9}$
Б $\frac {1}{9}$ $\frac {1}{9}$ $\frac {1}{9}$
Н $\frac {1}{9}$ $\frac {1}{9}$ $\frac {1}{9}$

Благодаря симметрии мы можем быстро вычислить общий результат:

$\frac {1}{9}(0)+\frac {1}{9}(-1)+\frac {1}{9}(1)+\frac {1}{9}(1)+\frac {1}{9}(0)+ \frac {1}{9}(-1)+\frac {1}{9}(-1)+\frac {1}{9}(1)+\frac {1}{9}(0)=0$


И снова вы и ваш противник пришли к ничьей. Но разница здесь в том, что никакой из игроков не имеет стимула к изменению стратегий! Если Игрок B перешёл бы к любой неуравновешенной стратегии, где один вариант выбора — допустим, камень — выбирался чаще других, то Игрок A просто бы изменил свою стратегию и стал чаще выбирать бумагу. В конце концов это привело бы к положительному общему результату Игрока A в каждом раунде. Именно это и происходит, когда Игрок A выбирает стратегию $(\frac {1}{4},\frac {1}{2},\frac {1}{4})$ против стратегии Игрока B $(\frac {1}{2},\frac {1}{4},\frac {1}{4})$.

Разумеется, если Игрок A перейдёт от $(\frac {1}{3},\frac {1}{3},\frac {1}{3})$ к неуравновешенной стратегии, Игрок B аналогичным образом сможет получить преимущество. Поэтому ни один из игроков не может улучшить свои результаты только за счёт изменения собственной стратегии. Игра достигла равновесия Нэша.

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

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

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

Есть искушение думать так. В нашей игре «камень-ножницы-бумага» мы сразу смогли догадаться, что ни один из игроков не смог бы сыграть лучше, кроме как играя совершенно случайно. Но частично так получается потому, что предпочтения всех игроков известны всем остальным игрокам: все знают, сколько каждый другой выиграет и проиграет при каждом из результатов. Но что, если предпочтения более скрыты и сложны?

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

А если каждое из вознаграждений Игрока B было бы разным и скрытым, то Игроку A потребовалось бы какое-то время на выяснение стратегии Игрока B. Должно пройти много раундов, прежде чем Игрок A догадается, допустим, как часто Игрок B выбирает камень, чтобы понять, как часто ему нужно выбирать бумагу.

Теперь представьте, что в «камень-ножницы-бумагу» играют 100 человек, и у каждого из них есть разный набор тайных вознаграждений, каждое из которых зависит от того, сколько из 99 своих противников они побеждают с помощью камня, ножниц или бумаги. Сколько времени уйдёт на вычисление всего лишь правильной частоты выбора камня, ножниц или бумаги, которая необходима для достижения точки равновесия? Скорее всего, очень много. Возможно, больше, чем будет длиться сама игра. Возможно, дольше, чем срок жизни самой Вселенной!

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

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

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

Упражнения


  1. Допустим, Игрок B играет со смешанной стратегией $(\frac {1}{2},\frac {1}{2},0)$. Какую смешанную стратегию должен выбрать A, чтобы максимизировать количество своих выигрышей в длительной перспективе?
  2. Допустим, Игрок B играет со смешанной стратегией $(\frac {1}{6},\frac {2}{6},\frac {3}{6})$. Какую смешанную стратегию должен выбрать A, чтобы максимизировать количество своих выигрышей в длительной перспективе?
  3. Как может измениться динамика игры, если за ничью каждому из игроков будет даваться очко?
Поделиться публикацией
Ой, у вас баннер убежал!

Ну. И что?
Реклама
Комментарии 26
  • 0
    Думал секрет игры раскроют, а ннет, все же решка выпадает столько же сколько орёл при больших числах, об этом узнал опять
    • 0
      Ну это только у математиков так — у хорошего шулера всё будет как нужно :)
      Да и, в конце концов-то, монета ведь не идеально симметричная. Так что можно такой сюжет написать, что рен-тв со своими пирамидальными зомби-ящерами от зависти удавится.
    • +1
      Вспомнил фильм «Игры разума» про Джона Нэша. Отличное кино, хоть и сильно отличающе
      еся от реальной жизни ученого. Он, кстати, единственный в мире математик получивший и Абелевскую премию и Нобеля.
      • +1
        Правильней будет сказать не математик, а учёный, т.к. Нобелевскую ему дали по экономике.
      • 0
        У нас в детстве был вариант с 4 элементами. Камень, ножницы, бумага и колодец (О_о).
        В колодце тонули камень и ножницы а бумага его накрывала. Потом я только узнал что классическая игра состоит из 3 элементов.
        • 0
          Чем больше элементов, тем меньше вероятность ничьей. Можно вспомнить «камень-ножницы-бумага-ящерица-Спок» или вот, например, такое (существуют и ещё более замороченные комбинации):

          Заголовок спойлера
          image
          • +2
            БОЛЬШЕ! ЕЩЁ БОЛЬШЕ!!!



            • +2
              И как волка с первой картинки собирать быстро? У меня уходит не менее 5 секунд

              Интересно, а в 101-версию кто-то играет?
              • 0

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

                • 0
                  Вы про спока? Сходу сделал без проблем, в чем сложность?
                  • 0
                    Лишь огоаниченное число людей может управлять кистью раздельно
            • 0
              Чем больше элементов, тем меньше вероятность ничьей.

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

            • +2
              а у нас помню был еще вариант с 6-ю — камень, ножницы, бумага, карандаш, огонь и вода. Кто там кого бил и по какой логике уже не помню :)
              • 0
                У нас еще продолжение было "… и бутылка лимонада и железная рука" =)
              • +1
                Получается, бумага и колодец более выгодны, чем камень и ножницы.
                Бумага и колодец побеждают 2-х «противников» и проигрывают одному, а камень и ножницы — побеждают только 1-го «противника» и проигрывают 2-м.
                • 0
                  Если чаще выкидывать колодец, противник начнёт чаще выкидывать бумагу.
                  • 0
                    Это как раз, судя по всему, пример увеличивающегося вознаграждения за один из вариантов. Тоже в детстве думал, что бумага с колодцем более выгодны. Статья дала объяснение в принципе логичное этому.
                  • +2

                    Описанная вами версия ничем не отличается от классической, и вот почему.


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


                    Если сформулировать это более формально, то в обычной игре все три опции Парето-оптимальны; в вашей версии одна из четырёх опций строго доминируется другой, поэтому остаются всё те же три Парето-оптимальных.

                    • 0
                      В детстве об этом не задумывались ))
                  • 0
                    По статистике, оптимальная комбинация — это «ножницы».
                    На первом уровне анализа кажется что это «камень», как формально наиболее старшая комбинация (аналог туза в карточных играх, где двойка/шестёрка бьют этого туза). Маленькие дети чаще всего выберут «камень».
                    Более глубокий уровень анализа подсказывает что надо контрить «наиболее очевидную комбинацию» — камень. Поэтому чаще всего в игре встречается «бумага».
                    И вот именно эту, наиболее часто встречаемую комбинацию, и должны контрить «ножницы».
                    Дальнейшая рекурсия уровней анализа лишена практического смысла.
                    • 0
                      У профессионалов мирового уровня помимо статистики принято ещё также применять и тактику.
                      • 0
                        Никакая тактика не поможет против равновесной стратегии (1/3; 1/3; 1/3).
                    • 0
                      Дополнение: не во всех играх существуют выигрышные стратегии! В камень-ножница-бумага существует. [Выигрышной стратегией называется такая стратегия, против которой математическое ожидание против любой другой стратегии >= 0. ]
                      То есть какую бы вы стратегию вы не выбрали, вы всегда проиграете в долгой игре.
                      • 0
                        Есть очень хорошое наблюдение для таких игр, позволяющая быстро проверять необходимое условие выигрышной стратегии. Хорошая стратегия должна выигрывать против единичных стратегий (1, 0, 0), (0, 1, 0), (0, 0, 1). Отсюда очевидным образом следует, что существует только одна выигрышная стратегия причем с равными вероятностями.
                        • 0
                          Поэтому можно надеяться, что «игры» наподобие экономических пакетов стимулирования, налоговых кодексов, условий договоров и конструкций сетей приведут к равновесиям Нэша, при которых отдельные лица, действующие в собственных интересах, придут к устраивающему всех результату и системы станут стабильными.

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


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


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

                          • 0
                            На пораскинуть мозгами)

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

                            Самое читаемое