Филимоненков Виктор (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

Recent Posts from This Journal

  • Ямбики 2

    Выкладываю последнюю порцию центонов-негативов. Прием ответов на предыдущие этапы конкурса продолжается, окончание игры пока где-то в тумане,…

  • Ямбики 1

    В игре: Словесные игры - 40, Хорейчики 1, там же смотрите правила, Хорейчики 2. Продолжаем разговор! Внимание! В последних двух турах конкурса…

  • Сей Геллеспонт переплывал

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

  • 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