Жду новый пост

Серия «Теория игр для начинающих»

Игра была предложена в 1921 году как пример игры, в которой «имеет значение психология игрока». Она изучалась после Второй мировой войны специалистами по исследованиям операций и стала классикой теории игр.

Название игры заимствовано у вымышленного полковника. Его задача — найти оптимальное распределение своих солдат на N полях сражений, зная, что:

• на каждом поле боя побеждает та сторона, которая выделяет больше солдат, но

• ни одна из сторон не знает, сколько солдат противоборствующая сторона отправит на каждое поле боя, и:

• обе стороны стремятся максимизировать количество полей сражений, которые они рассчитывают выиграть.

Давайте представим себе игру, основанную как на китайском аукционе палочек, так и на игре «Полковник Блотто».

В игру «Голодный полковник» играют 2 игрока. Каждый из них может написать 3 числа, но не в порядке убывания. Сумма чисел должна быть 6. Выигрывает игрок, чьи 2 числовые позиции превышают 2 позиции противника.

У каждого игрока есть 3 варианта (игра симметричная) ходов, в том числе (2; 2; 2), (1; 2; 3) и (1; 1; 4). (1; 1; 4) против (1; 2; 3) приводит к ничье, (1; 2; 3) против (2; 2; 2) приводит к ничье, (2; 2; 2) выигрывает (1 ; 1; 4). Итак, (2; 2; 2) — оптимальная стратегия.

Рассмотрите другой вариант аналогичной игры для двух игроков и сыграйте в нее с друзьями:

• Игровое поле представляет собой доску 3 на 3.

• У каждого игрока есть армия из 100 маленьких Ктулху.

• Перед ночным боем каждый игрок тайно размещает свои отряды на 9 клетках. На каждую клетку можно поставить любое целое число Ктулху от 0 до 100.

• Утром начинается битва новую планету. На каждой из 9 клеток побеждает игрок, у которого больше всего Ктулху на этой клетке. За победу на каждом из 9 квадратов дается 1 очко. Если на какой-то клетке числа соперников были одинаковыми, то бой на этой клетке заканчивается вничью и оба игрока получают по 0,5 очка.

• Битву выигрывает тот, кто выиграл больше всего полей. Если оба игрока получают по 4,5 очка, битва заканчивается вничью.

Эта игра (разумеется, немного в другой формулировке) проходила в качестве конкурса в 2019 году на сайте Михаила Павкухина. Наилучший результат получил игрок, разместивший Ктулхят согласно следующей таблице: :

Этот игрок обыграл 4121 соперника, проиграл 1011 и сыграл вничью с 216.

Эта игра сильно отличается от рассмотренной ранее дилеммы заключенного. Разберем самое главное отличие.

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

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

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

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

–  Вот именно, – сказал Дюпен.  –  А  когда я спросил у мальчика, каким способом он  достигает  столь  полного  отождествления, обеспечивающего  ему постоянный успех, он  ответил  следующее: «Когда  я  хочу  узнать, насколько умен,  или глуп,  или добр, или  зол  вот этот  мальчик иди о  чем он сейчас думает,  я стараюсь придать своему лицу точно  такое  же  выражение, которое вижу на  его  лице,  а потом жду,  чтобы узнать,  какие  мысли  или  чувства возникнут у меня в  соответствии  с этим выражением

Потому мальчик из данного рассказа настолько успешен, что он всегда может продумать цепочку «Он думает, что я думаю, что он думает, что....»  ровно на один шаг дальше, чем соперник.

Точно так же и в «камень-ножницы-бумага» нет равновесия Нэша: во всех этих вероятных исходах нет варианта, при котором оба участника были бы довольны своим выбором. Однако чемпионат мира и Всемирное общество ножниц-камень-бумаги (World Rock Paper Scissors Society) собирают игровую статистику. Очевидно, что в этой игре можно повысить свои шансы на победу, зная кое-что об обычном поведении людей.

По данным World RPS Society, камень — самый популярный бросок (37,8%). Бумагой играют 32,6%, ножницами — 29,6%. Итак, теперь вы знаете, что вам нужно выбрать «бумажный» ход. Однако, если вы играете с кем-то, кто тоже это знает, больше не берите бумагу, потому что это ожидаемо. Известен случай: в 2005 году два аукционных дома Sotheby's и Christie's соревновались за право выставить на торги очень крупный лот, в частности, коллекцию Пикассо и Ван Гога по стартовой цене в 20 миллионов долларов. Хозяин пригласил представителей двух домов поиграть в «камень-ножницы-бумагу». Sotheby's без колебаний выбрал бумагу. Победил дом Christie's. На самом деле его представители обратились к эксперту, 11-летней дочери одного из топ-менеджеров. Она сказала: «Камень кажется самым прочным, поэтому большинству людей хочется выбрать его. Но если мы не будем играть с совсем тупым новичком, то он не выберет камень, но будет ждать этого от нас, поэтому, он выберет бумагу. Мы подумаем на один шаг вперёд и выберем ножницы.»

Ящерица? Спок!

Новый вариант игры «камень-ножницы-бумага» популяризировал американский сериал «Теория большого взрыва», изначально созданный Сэмом Кассом и Карен Брайла. Это камень-ножницы-бумага-ящерица-Спок. Здесь действуют классические правила, к которым нужно добавить ящерицу, которая ест бумагу, отравляет Спока, раздавливается камнем и обезглавливается ножницами. Тем временем Спок испаряет камень, ломает ножницы и дискредитирует себя бумагой. Этот вариант, который увеличивает количество комбинаций с 3 до 10, должен уменьшить количество ничей между двумя игроками, которые знают друг друга.

Согласно теории вероятностей, в классическом варианте вероятность выигрыша, проигрыша и повторной игры одинакова и равна 1/3. В улучшенной версии ситуация меняется: вероятность выигрыша и проигрыша составляет по 0,4, а вероятность повторной игры — 0,2. Другими словами, если вы используете улучшенную версию инструмента разрешения споров, то в среднем количество неудачных раундов будет меньше. Тем не менее, между персонажами сериала этот вариант систематически приводит к ничье Спок vs. Спок.

Другой вариант, на этот раз французский, был популяризирован игрой Le Tout (изобретенной Tobiffleurs). Это камень-ножницы-бумага-галактика-клещ. Здесь мы используем классические правила, добавляя галактику, которая дематериализует камень, лист и ножницы, но которая взрывается из-за клеща. Последний может же быть убит камнем, листом или ножницами.

Давайте сравним этот режим игры с другими типами. Вариант «камень-ножницы-бумага-колодец» менее сложен, чем вариант «камень-ножницы-бумага-ящерица-Спок». Есть 4 знака для увеличения количества комбинаций. Это вариант, встречающийся во франкоязычных странах (Франция, Швейцария, Канада) и Германии.

Подробно о дополнительных условиях победы:

• Ножницы падают в колодец,

• Камень падает в колодец,

• Бумага закрывает колодец.

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

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

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

Пусть первый игрок выбирает камень с вероятностью x, ножницы с вероятностью y и бумагу с вероятностью 1−x−y.

Тогда математическое ожидание выигрыша второго игрока в случае выбора им камня будет равно 0∙x+(-1)∙y+1∙(1-x-y).

В случае выбора ножниц это математическое ожидание будет равно

1∙x+0∙y+(-1)∙(1-x-y), а в случае выбора бумаги будет равно  (-1)∙x+1∙y+0∙(1-x-y).

Тогда равенство потенциальных доходов можно записать в виде:

0∙x+(-1)∙y+1∙(1-x-y)=1∙x+0∙y+(-1)∙(1-x-y)= (-1)∙x+1∙y+0∙(1-x-y).

Решив систему двух уравнений с двумя неизвестными, находим, что в равновесии наш ожидаемый выигрыш будет равен 0 и достигается, когда y = x =  1/3.

Аналогично можно определить и оптимальную стратегию для второго игрока. Логично, что в этой симметричной игре она такая же, как и у первого игрока.

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

Самая крупная сумма, выигранная в этих играх, составляет 50 тысяч долларов. Его выиграл в Лас-Вегасе Шон Сирс, который не собирался участвовать в тот вечер в игре «камень-ножницы-бумага». Но он неожиданно обыграл за вечер 300 противников и заслужил прозвище «сумасшедшие пальцы». Сирс объяснял свой успех умением наблюдать за противником в конкретной ситуации и не придерживаться одной тактики.

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

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

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

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

4. Зависть – желание набрать очков больше, чем соперник. Это – плохое свойство, хорошие стратегии независтливы.

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

Игра в монетки

Давайте проанализируем следующую игру.

Имеется два игрока. Один из них прячет монету в руке. Другой пытается угадать, где монета. Игрок, угадавший, в какой руке монета у партнёра, забирает её. Если угадать не получилось, мы отдаём партнёру по игре свою монетку.

Построим матрицу платежей для данной игры.

Как мы видим, в данной игре ВООБЩЕ нет никаких равновесий – ни по Нэшу, ни Парето-оптимальных.

Как вы думаете, какое будет равновесие в смешанных стратегиях в данной игре?

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

Всё становится сложнее, когда игрок «я такой внезапный» наталкивается на двухшляпного. В первый день он сделает одну шляпу, а во второй – две. Но далее каждый игрок будет делать по 2 шляпы каждый день. Тогда каждый получит средний выигрыш в 11 евро, так как выигрыш в первый день не имеет значения при вычислении средних над бесконечным периодом.

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

Смешаные стратегии

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

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

В повторяющихся играх каждая из стратегий однократной игры называется чистой стратегией.

Смешанная стратегия – это присвоение вероятности каждой чистой стратегии.

Это позволяет игроку случайным образом выбирать чистую стратегию. Поскольку вероятности непрерывны, игроку доступно бесконечно много смешанных стратегий. Интерес к смешанным стратегиям объясняется просто – если соперник определит, какая из ваших стратегий будет применяться в очередной игре, он сможет использовать эти знания для улучшения своего результата (и ухудшения вашего). Поэтому «чем случайнее, тем вернее», именно непредсказуемо случайное чередование стратегий не позволит добиться сопернику выигрыша.

Логично, что  чистые стратегии можно представить как частный случай смешанных, например, в том случае, когда частота одной из стратегий – 1, а остальных – 0.

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

Полностью смешанная стратегия – это смешанная стратегия, в которой игрок присваивает каждой чистой стратегии строго положительную вероятность.

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

Цена игры – результат, достигнутый при решении игры, то есть, средний выигрыш (математическое ожидание выигрыша) при применении оптимальных стратегий обоими игроками.

Те стратегии, которые присутствуют в оптимальной стратегии игрока с ненулевыми частотами, называются полезными (другое название – активными).

В 1928 году фон Нейман доказал, что для каждой игры имеется не менее одного решения. Это решение может находится в том числе в области смешанных стратегий.