Новости

Просмотр записей в категории geektimes

Небольшая группа шведов протестует против безналичной экономики

https://geektimes.ru/post/299667/
  • Финансы

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

https://geektimes.ru/post/299695/
  • Логические игры


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$

Роскомнадзор подал иск на блокировку Telegram

https://geektimes.ru/post/299725/
  • Социальные сети и сообщества
  • Регулирование IT-сектора
  • Информационная безопасность

Мангровый лес: крутейший биом планеты

https://geektimes.ru/post/299689/
  • Экология

Клиентка ДНК-сервиса по поиску родственников узнала, что ее отец — врач, лечивший мать от бесплодия

https://geektimes.ru/post/299697/
  • Будущее здесь
  • Биотехнологии

Последние записи

Архив

2018
2017
2016
2015
2014

Категории

Авторы

Ленты

RSS / Atom