Филимоненков Виктор (fiviol) wrote,
Филимоненков Виктор
fiviol

Categories:

Жребий Крижановского

В эту игру играют на http://eq.ur.ru
В игре участвует n игроков (n>2). Каждый игрок независимо от других называет натуральное число в диапазоне от 1 до n+1 включительно. Среди названных чисел выбираются те, которые были названы только одним каким-либо игроком. Выигрывает игрок, написавший наименьшее из этих выбранных чисел, причем количество выигранных им очков равно написанному им числу.
Если ни одно из названных чисел не оказалось уникальным, то объявляется ничья и очки никому не присуждаются.

Сегодня сидел на экзамене, пока студенты делали вид, что пришли по делу, обдумывал выигрышную стратегию в ЖК. Вот что у меня получилось.
Игрока, за которого мы придумываем стратегию, так и будем называть игроком, остальных будем называть противниками.
Определение. Стратегией игрока (i-го противника (i=1,...,n-1)) назовем набор вероятностней x_j (соответственно p_ij), с которым игрок (противник) назовет число j.
Будем сначала предполагать, что игроку известны стратегии противников. Какую стратегию он должен выбрать, чтобы обеспечить себе максимально большой вероятный выигрыш?
Утверждение. Оптимальной стратегией игрока при известных стратегиях противников является простая стратегия, при которой он все время называет одно и то же число (зависящее от стратегий противников).
Доказательство: Средняя ожидаемая величина выигрыша игрока является линейной формой от x_j:
F=k_1*x_1+...+k_(n+1)*x_(n+1), где k_j есть средняя ожидаемая величина выигрыша игрока при выборе им числа j. Числа k_j выражаются через числа p_ij с учетом правил игры и аксиом теории вероятностей, хотя эти выражения и громоздкие. Возникает обычная задача ЛП: оптимизировать форму F при одном ограничении в виде равенства x_1+...+x_(n+1)=1 и ограничениях-неравенствах x_j>=0. Такая задача имеет оптимальное базисное решение, при котором одно из x_j=1, а остальные равны 0. Но такое решение и означает простую стратегию.

Пусть теперь игра проводится в большое количество туров, и противники являются роботами, стратегии которых не меняется от тура к туру, но игроку они не известны. Тогда в очередном туре в качестве p_ij разумно взять долю появления числа j у i-го противника в предыдущих турах, и вычислить по этим p_ij новые значения k_j, и, соответственно, выбрать оптимальную стратегию игрока, то есть то число j, для которого x_j=1. Через большое число туров, по ЗБЧ, эмпирические p_ij будут близки к заданным в программах роботов, и игрок будет называть все время одно оптимальное число.

Гипотеза: Если среди роботов будут думающие противники, то игроку все равно выгодно играть по стратегии, описанной в предыдущем абзаце.
Tags: Игры, Математика
Subscribe

  • С Новым годом!

    Желаю всем в 2021 году здоровья, благополучия, удачных свершений и приятных неожиданностей! А еще хочется заступиться за ушедший год - в каких только…

  • Отпуск, июнь 2020, Улан-Удэ

    Первую часть отпуска на в этом году мы взяли на июнь, исходя из того, что в конце мая Олег должен был вернуться домой, отслужив свой год в Бурятии.…

  • 51

    Не достигну края Земли - Не такой я упорный бродяга. Но [... ...]. Комментарии не скрываю, не та тема поста. Но по случаю даты крыло нужно написать…

  • Post a new comment

    Error

    default userpic
    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 0 comments