knop: (qr)
[personal profile] knop
Три игрока - A, B и C - играют в такую игру: каждый из них независимо от остальных выбирает натуральное число от 1 до 6. Затем все числа оглашаются, и выигрывает в раунде назвавший наименьшее уникальное число. (Например, если двое назвали 1, а третий назвал 4, то он и выиграет).

Игра проводится 1000 раундов, и победителем объявляется тот, кто выиграл больше всего раундов.

Какова оптимальная стратегия для А (ну, и для B), если C перед началом игры объявил, что в каждом раунде будет бросать кубик для определения собственного числа (и на самом деле ровно так и играл)?

Комменты в ЖЖ скрыты на несколько дней. Те, кто увидят эту задачу в ВК, FB или Twi, приглашаются в ЖЖ ;-)

Date: 2015-06-23 11:40 am (UTC)
From: [identity profile] efimpp.livejournal.com
в виду симметричности стремиться выиграть больше, чем в половине случаев, вроде бы, не стоит
поэтому А и B договариваются называть 1 и 2 по очереди (1,2) (2,1), (1,2) ...
в этом случае C не достается ничего, а A и B получают по половине, причем уклоняться от этой стратегии им вроде бы нет ровно никакого смысла
виноват - не прочитал условие внимательно. остаться должен один
пошел думать
Edited Date: 2015-06-23 02:41 pm (UTC)

Date: 2015-06-23 11:42 am (UTC)
From: [identity profile] knop.livejournal.com
Ну и еще. Они конкуренты, а не сообщники.

Date: 2015-06-23 11:45 am (UTC)
From: [identity profile] efimpp.livejournal.com
это да, но если бы выплата шла в каждой игре, обманывать нет смысла (разве что договориться с C :-)

Date: 2015-06-23 11:57 am (UTC)
From: [identity profile] knop.livejournal.com
Я не понял этой мысли. Я хочу сказать, что в целом БЕЗУСЛОВНО возможны стратегии, основанные на статистике предыдущих раундов, но все равно никаких предварительных договоренностей игроков не предполагается.

А для начала можно, наверное, ограничиваться "негенетическими" стратегиями, т.е. голыми вероятностями выбора того или иного числа.

Date: 2015-06-23 12:10 pm (UTC)
From: [identity profile] efimpp.livejournal.com
если бы платили за каждый раунд и всё, общая победа не важна, то A и B быстро находят последовательность (1,2), (2,1) и придерживаются ее забирая примерно половину выигрышей каждый. но задача другая :-)

Date: 2015-06-24 06:25 am (UTC)
From: [identity profile] kotomord82.livejournal.com
Получилось подобрать стратегию вероятностью победы в раунде 0.34760705288162663
(без доказательства ее оптимальности - что генетический алгоритм нашел)

P.S. Да, я понимаю, что задача- просто минимизация квадратичной формы, но что под рукой было - то и запустил
Edited Date: 2015-06-24 09:39 am (UTC)

Date: 2015-06-23 11:50 am (UTC)
From: [identity profile] efimpp.livejournal.com
что происходит при равенстве очков?

Date: 2015-06-23 11:54 am (UTC)
From: [identity profile] knop.livejournal.com
Выигрыш казино ;-)

Ну то есть никто из игроков не считается выигравшим раунд

Date: 2015-06-23 12:08 pm (UTC)
From: [identity profile] efimpp.livejournal.com
при равенстве числа выигранных раундов у двух игроков
Edited Date: 2015-06-23 05:43 pm (UTC)

Date: 2015-06-23 12:20 pm (UTC)
From: [identity profile] efimpp.livejournal.com
А и B спонтанно выходят на согласованное поведение (выбрасывание 1 строго по очереди - чтобы начать можно выбрасывать 1 или 2, подбрасывая монетку, в тот момент когда согласование произошло должно начаться строгое чередование).
нарушитель конвенции карается выбрасыванием 1 все время - победа уходит к С.
в 1/6 случаев выбрасывающий не 1 выигрывает раунд поэтому начавший играть конвенционно в худших условиях не обречен.

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

а есть ли алгоритмы, не учитывающие историю и дающие без всех этих хлопот вероятность не меньше 1/2 - не знаю.
замечу что как бы ни играл A или B, второй из них может лишить его победы в случае, если считает, что сам потерял шансы (и склонить к кооперативной стратегии).

Date: 2015-06-23 12:31 pm (UTC)
From: [identity profile] livejournal.livejournal.com
Здравствуйте! Ваша запись попала в топ-25 популярных записей LiveJournal северного региона (http://www.livejournal.com/?rating=ru_north). Подробнее о рейтинге читайте в Справке (http://www.dreamwidth.org/support/faqbrowse?faqid=303).

Date: 2015-06-23 01:12 pm (UTC)
From: [identity profile] 173175973.livejournal.com
Подразумевается, что игроки не будут пытаться угадать стратегию противника? То есть, нужно выбрать распределение для своего ответа?

Date: 2015-06-23 02:38 pm (UTC)
From: [identity profile] knop.livejournal.com
В такой трактовке тоже можно порешать ;-)

Date: 2015-06-23 04:54 pm (UTC)
From: [identity profile] 173175973.livejournal.com
А точно есть "математическое" решение в оригинальной постановке?
Если подойти "практически", то самым лучшим выглядит ход в духе второй игры из Liar Game - первым заявить, что всегда будешь ставить на 1 и придерживаться своего выбора. Тому, кто не успел, остаётся только равнять шансы первого и C - выбриать 1, если лидирует первый и 2, если C вырвался вперёд (и 1/2, если у них поровну).
Или Вы имели в виду угадывание стратегий, и что первые десятки (сотни) ходов они оба ещё не совсем верят C и играют исходя из того, что он тоже не лыком шит?

Date: 2015-06-23 06:10 pm (UTC)
From: [identity profile] knop.livejournal.com
Зачем же равнять шансы? Можно просто тоже ставить на 1 и отдавать победу C, пока А не передумает. Ведь А одинаково не устраивает и победа B, и победа C.

C они как раз верят. Проблема в том, как им друг с другом быть.

Date: 2015-06-24 06:31 am (UTC)
From: [identity profile] 173175973.livejournal.com
Мы всё ещё говорим о теории игр? Если заявить, что будешь ставить на 1 и лучше проиграешь сам, чем дашь выиграть другому, то это, скорее, область психологии - кто кого переблефует. Что-то вроде "буду ставить на 1, пока у тебя больше, чем у меня".
Кстати, если у первого меньше побед, чем у С, то ставить на 2 как раз имеет смысл, т.к. чем дальше вырвется лидер (любой), тем труднее его догонять. Задача о справедлиом разделении ставки (в классическом варианте) очень демонстравтивна.

Upd. По сути, это та же дилема заключённых. Какой на неё Ваш ответ в такой же постановке вопроса?
Edited Date: 2015-06-25 10:30 am (UTC)

Date: 2015-06-25 05:35 pm (UTC)
From: [identity profile] knop.livejournal.com
Да, это безусловно задача из той же серии, что и дилемма заключенного.
Ее можно чуток математизировать, если сразу оговорить, что и за А, и за B будет играть компьютерная программа. Вопрос в том, какой алгоритм в нее заложить.

Я просто сначала собирался написать большой пост про историю соревнований таких программ, а потом решил, что правильнее начать с вводной задачи

Date: 2015-06-24 08:04 am (UTC)
From: [identity profile] lithovore.livejournal.com
А может обязаться отдать после игры весь свой выигрыш + 1 доллар В, если хотя бы один раз назовёт не 1. Тогда В будет знать, что А точно не передумает.

Если В стремится максмизировать вероятность того, что он победит в большем количестве раундов, чем остальные (какой бы ничтожной эта вероятность ни была), то трудно оценить вероятность того, что выиграет А. Но при равном счёте А и С В выгоднее называть 2, чем 1 (если он называет 2, то выигрывает раунд с вероятностью 1/6, а если называет 1, то гарантированно не выигрывает; а кто-то из двух других в любом случае выигрывает с вероятностью 5/6), так что интуитивно кажется, что у А хорошие шансы на победу.
(deleted comment)

Date: 2015-06-23 03:37 pm (UTC)
From: [identity profile] knop.livejournal.com
Именно кубик? Ну тогда все трое выиграют примерно треть игр. Неужели же ОПТИМАЛЬНАЯ стратегия оказывается бессильной улучшить этот тривиальный результат, особенно если учесть, что у игроков A и B перед игроком C есть то важное преимущество, что они знают его стратегию, а он их - нет?

Date: 2015-06-25 11:42 am (UTC)
From: [identity profile] e-ponikarov.livejournal.com
Ну, шестерка на кубике для А и В явно бесполезна, так что даже пятигранная кость должна дать улучшение по сравнению с 1/3.

Например, берем двугранную кость: А и В бросают монетку на числа 1 и 2. Тогда С выигрывает при
-(2,2,1) (p=1/24).
-(1,1,k) для k = 2-6 (суммарная p=5/24)
Итого на долю C приходится 1/4, а на долю этой парочки, соответственно, по 3/8, что лучше 1/3.

Переигровочный вариант (1,1,1) и (2, 2, 2) можно убрать переходом к приведенному вероятностному пространству, лень писать.

Но раз доля побед С фактически приходится на результат, когда варианты А и В совпадают, нужно обеспечить, чтобы совпадения не было. Убираем монету вообще.
А и В фиксированным образом делят себе поровну комбинации (1,2) и (2,1), что обеспечивает на каждом этапе победу игрока с единицей с вероятностью 5/6, и победу игрока с двойкой с вероятностью 1/6. Да, есть вероятность ничьей после 1000 таких испытаний. Но небольшая :)

Date: 2015-06-23 04:23 pm (UTC)
From: [identity profile] varpi.livejournal.com
Первое что приходит в голову - это чтобы А громко объявил, что всегда будет выбирать 1; ну и следовать этой стратегии. Или просто всегда выбирать 1, в надежде что В это заметит. Тогда В, чтобы иметь хоть какой-нибудь шанс, придется всегда выбирать не 1, а значит А выигрывает с большой вероятностью...

Date: 2015-06-23 04:34 pm (UTC)
From: [identity profile] ksega.livejournal.com
Оптимальная стратегия выдавать числа 1 2 3 4 5 6 с вероятностями
121/397,90/397,66/397,48/397,36/397,36/397

Вроде в таком случае получается вероятность выигрыша 138/397, что выше чем "наивная вероятность" 70/216.

(UPD) Вероятности выигрыша даны для одной игры. При игре в 1000 раундов, при такой стратегии выигрывать A и B будут в ~50% случаев, а C будет выигрывать в ~1% случаев
Расчет делался исходя из того, что у A и B одинаковая стратегия (заданная 6-ю числами) максимизирующая вероятность выигрыша (многочлен второго порядка от этих 6-и чисел)
Edited Date: 2015-06-24 10:20 am (UTC)

Date: 2015-06-23 05:58 pm (UTC)
From: [identity profile] slavakab.livejournal.com
Рассмотрим множество состояний, возникающих в игре (N, Na, Nb), где N - число игр, которые осталось сыграть; Na - число раундов, уже выигранных A, минус число раундов, уже выигранных С; Nb - число раундов, уже выигранных B, минус число раундов, уже выигранных С. Требуется вычислить функции Pa(N, Na, Nb) и Pb(N, Na, Nb) вероятностей выигрыша игроков A и B соответственно. Для простоты при равенстве числа выигранных раундов, пусть победитель определяется жребием (тогда Pc = 1 - Pa - Pb). Поведение игроков A и B определяется исключительно стремлением повысить свою вероятность выигрыша в каждом состоянии, следовательно, не имеет значения, как было получено это состояние.
При N = 0 все понятно, например Pa(0, Na, Nb) = 1 при Na > Nb, Na > 0; Pa(0, Na, Nb) = 0.5 при Na = Nb > 0, и т.д.
При каждом переходе от N к N+1, считая отдельно каждую пару (Na, Nb), либо найдем для кого-то из A и B чистую стратегию, позволяющую добиться наилучшего значегия своей функции выигрыша, либо посчитаем смешанную стратегию. И вот так, двигаясь назад к N = 1000, получим ответ.

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

-------
Дополнение: похоже, не работает здесь этот метод, уже Pa(1,0,0) не считается, нет у A стратегии на игру в один раунд, которая гарантирует вероятность выигрыша хотя бы 1/3 при любой игре B.

-------
Дополнение 2: из того, что при малых N некоторые состояния не просчитываются, не следует, что при стремлении разумных A и B к увеличению (каждым своих) шансов на выигрыш, начиная с больших N, им не удастся с большой вероятностью обойти множество "плохих", не просчитываемых состояний, и сохраняя вероятность выигрыша около 1/2 для каждого подойти к множеству состояний, "сваливающихся" при ближайших ходах примерно с равной вероятностью в одно из состояний вида (Na > Nb, Na > N, - значительное преимущество A) и (Nb > Na, Nb > N, - значительное преимущество B), либо в (Na = Nb > N, я бы это трактовал как ничью между A и B, устраивающую обоих).

Пожалуй, при достаточно больших N, когда своими действиями можно показать сопернику возможность наказать его сдачей победы игроку C, основой стратегии A будет:

"Если у B больше выигранных раундов, чем у меня, но он еще не может играя в 1 гарантировать себе победу с вероятностью, заведомо не меньшей 0.5, я играю в 1. Если у меня больше выигранных раундов, чем у B и N достаточно велико, чтобы B игрой в 1 мог лишить меня победы с вероятностью заведомо больше 0.5, то я проявляю добрую волю и хожу в 2; если же мой ход в 1 гарантирует мне победу с вероятностью, заведомо не меньшей 0.5, я хожу в 1. Если у нас одинакого выигранных раундов и N достаточно велико, чтобы любой из нас после любого исхода следующего хода мог игрой в 1 лишить соперника победы, я проявляю добрую волю и выбираю с равной вероятностью 1 или 2. Что я буду делать в остальных случаях, я пока не знаю, буду считать." (Здесь слово "заведомо" в применении к вероятности касается легко просчитываемого влияния случайности действий C при наихудшей для A стратегии B.)

Стратегия B симметрична.

И теперь можно считать, с какой вероятностью начиная с N=1000 это приведет к "плохим", непросчитываемым состояниям. И, конечно, "непросчитываемая" не значит в чистую проигранная, например, просто бросив кубик, А показывает, что Pa(1,0,0) >= 5/36, так что эти оценки можно использовать, усредняя с другими исходами, улучшая оценки для них.
Edited Date: 2015-06-24 08:08 pm (UTC)

Date: 2015-06-23 06:19 pm (UTC)
From: [identity profile] Максим Дмитриев (from livejournal.com)
Если А и В будут кидать четырёхгранный кубик с числами от 1 до 4, то это увеличит шансы каждого из них с 1/3 до 8/23, что уже неплохо.

Стратегию можно усилить ситуационно, если иметь в виду возможность финишного спурта. Имея небольшое преимущество над разумным соперником и большое преимущество над С (после 960 раундов С будет отставать примерно на 40 очков) можно перейти в стратегию "всегда 1". Игрок С уже не представляет опасности, и можно смело отдавать ему оставшиеся очки, увеличивая вероятность сохранить отрыв от ближайшего преследователя.
Edited Date: 2015-06-24 01:23 pm (UTC)

Date: 2015-06-23 06:54 pm (UTC)
From: [identity profile] kodt-rsdn.livejournal.com
Поскольку А и Б находятся в равных условиях, то можно предположить, что у каждого из них стратегия одна и та же.
Если стратегия детерминирована, то они наверняка проиграют. Значит, она вероятностная. Есть вероятности P1...P6. Нужно их так подобрать, чтоб максимизировать шансы.

Посмотрим на возможные комбинации (А,Б,С)
(1,1,1) - ничья
(1,1,2+) - проигрыш
(1,2+,1) - проигрыш
(1,2+,2+) - выигрыш
(2+,1,1) - выигрыш
(2+,1,2+) - проигрыш
(2+,2+,1) - проигрыш
(2+,2+,2+) - рекурсивно

Т.е. выигрываем при
P1*(1-P1)*5/6 + (1-P1)*P1*1/6 = P1*(1-P1)*6/6,
P2*(1-P1-P2)*4/6 + (1-P1-P2)*P2*1/6 = P2*(1-P1-P2)*5/6,
и т.д.,

Т.е.
P1*(1-P1)*6/6 +
P2*(1-P1-P2)*5/6 +
P3*(1-P1-P2-P3)*4/6 +
P4*(1-P1-P2-P3-P4)*3/6 +
P5*(1-P1-P2-P3-P4-P5)*2/6

Что-то в уме не прикидывается, как максимизировать. А решать формальными методами в час ночи ломает, если честно.
Ясно лишь, что при P1=...=P6=1/6 сумма должна получиться 1/3-1/36 (у всех игроков одинаковые шансы, минус вероятности ничьих). Это нижняя граница.

Ну и если А и Б смогут вступить в сговор, то они просто начнут чередовать: по чётным ходам А выбирает 1, Б 2, по нечётным наоборот.
Тогда ситуация ничьей в принципе невозможна, а вероятность выигрыша становится равна ровно 1/2.

Тут проблема

Date: 2015-06-24 05:11 am (UTC)
From: [identity profile] kotomord82.livejournal.com
Стратегия А "всегда 1" выигрывает у любой стратегии В, кроме "Всегда один" (ну и наоборот)

Re: Тут проблема

Date: 2015-06-24 05:15 am (UTC)
From: [identity profile] knop.livejournal.com
Проблема-то в том, что когда оба этих "стратега" начнут применять такую стратегию, то выиграет C.

Re: Тут проблема

Date: 2015-06-24 05:18 am (UTC)
From: [identity profile] kotomord82.livejournal.com
А я что сказал?

Date: 2015-06-24 05:55 am (UTC)
From: [identity profile] kotomord82.livejournal.com
Если предположить, что есть лучшая стратегия в классе "выбираем случайно с известным распределением " - то подобрать вероятности для каждого значения - задача техническая.

Date: 2015-06-24 10:36 am (UTC)
From: [identity profile] kodt-rsdn.livejournal.com
В общем, я не стал аналитически решать симплекс, а градиентным спуском нашёл приближённое решение.

Повторю идею: игроки А и Б, находясь в симметричных условиях, играют по одной и той же вероятностной стратегии, случайно выбирая цифры 1..6 с вероятностью P1..P6

Вектору вероятностей P (нормированному) сопоставим вектор весов W (ненормированный).
Переберём все 6^3=216 комбинаций цифр и помножим их на веса: w(x,y,z) = W[x]*W[y]*1
*1 потому, что игрок С выбирает цифры равномерно.
Посчитаем взвешенную сумму побед и поражений; ничьи отбросим.
Оценочная функция q(W) = win/(win+resign) если win>0 иначе 0.

Начнём с равномерных весов W=[1,1,1,1,1,1] - q(W1) = 1/3
Я начал спускаться с шагом в 0.001
За 28тыс итераций получил W=[1.0000, 0.7329, 0.5264, .03697, 0.2570, .02570]
Это соответствует вероятностям P=[0.3182, 0.2332, 0.1675, 0.1176, 0.0818, 0.0818]
При этом шанс победить 0.3600...
Edited Date: 2015-06-24 01:37 pm (UTC)

Date: 2015-06-25 05:18 am (UTC)
From: [identity profile] antikaon.livejournal.com
Вот такой вариант.

Пусть есть 4 исхода - выигрыш А, выигрыш B, выигрыш C и выигрыш D ("казино")
P(A) + P(B) + P(C) + P(D) = 1

Из соображений симметрии:
P(A) = P(B) = P
P(C) + P(D) = L
2P + L = 1

P = (1 - L) /2

Пусть A и B фон Неймановские игроки со смешанными стратегиями.
Чистой k-стратегией будет выставление числа k, 1 <= k <= 6.
Опять же из симметрии, у A или B нет преимущественной стратегии, так что PA(i) = PB(i) = Pi

Выразим L через P1, P2, P3, P4, P5, P6:

Если C выпал 1, то выигрыш C или D наступает, когда A и B выбрасывают не единицу оба, либо когда единицу -- тоже оба.

Вероятность этого:

[(P2 + P3 + P4 + P5 + P6)^2 + P1^2] * (1/6)

Если C выпал 2, то ...., когда ...

[(P3 + P4 + P5 + P6)^2 + P2^2] * (1/6)

и т.д.

Суммируя, получим L и P.

Подставив P1 = 1 - (P2 + P3 + P4 + P5 + P6),
получаем

P = билинейно по (P2, P3, P4, P5, P6)
Решая эту задачу на максимум P, получаем

P = 0.448
При смешанной стратегии
P1 = 0.618
P2 = 0.236
P3 = 0.090
P4 = 0.035
P5 = 0.014
P6 = 0.007


Date: 2015-06-25 04:48 pm (UTC)
From: [identity profile] slavakab.livejournal.com
Дополнение 3. При N > (6/5)*max(Na,Nb), вероятность, что C догонит A и B, если они упрутся как бараны в 1, больше 0.5, следовательно пока это неравенство соблюдается, в описанной выше стратегии не наступили еще "остальные случаи, когда надо считать". Помоделировав эту стратегию, я получил, что N (напомню, это число оставшихся раундов) опускается до равенства в интервале за 840 - 920 раундов. Когда равенство достигнуто, то при Na <> Nb, лидер может смело играть в 1, зная, что С его с вероятностью не меньше 0.5 не догонит при всем старании соперника. Следовательно, при Na=Nb, при достигнутом равенстве (или почти, в пределах 1, достигнутом), есть смысл попытаться обмануть соперника, сыграв в 1, и если он сыграет в 2, сразу получить решающее преимущество. Ни A, ни B, этого не могут допустить, значит, они сыграют оба в 1, отдадут очко C, уменьшив max(Na,Nb) на 1, неравенство укрепится, и можно снова играть честно. Таким образом, числа Na, Nb, N вместе пойдут вниз на грани соблюдения неравенства. Это грозит неизбежностью "плохих" состоянияй, как (N=1, Na=Nb=0). Что может это предотвратить? При Na=Nb+1, (6/5)*max(Na,Nb) + 2 > N > (6/5)*max(Na,Nb) игрок A сыграет честно в 2, B нет резона не играть в 1. C вероятностью (5/6) выиграет B, неравенство ослабнет, или даже N станет меньше, а Na=Nb, вроде все плохо. Но с вероятностью 1/6 очко получит A и добьется Na=Nb+2 и главное, N < (6/5)*max(Na,Nb) - решающее преимущество! Значит, если игроки A и B готовы играть "честно" вплоть до (6/5)*max(Na,Nb) + 2 > N, то они с равной частотой смогут по нескольку раз оказаться в ситуации, когда счастливый случай (вероятность 1/6) даст им решающее преимущество. Но чтобы войти в эту перспективную ситуацию, надо при Na=Nb, (6/5)*Na + 4 > N > (6/5)*Na + 3 сыграть честно, выбрав 1 или 2 с равной вероятностью. И тут очевидно искушение схитрить, и сыграть в 1, пусть соперник будет честен, сходит по жребию в 1 или 2 и отдаст мне этот шанс 1/6 получить решающее преимущество.
Что делать? Можно считать, кто сколько раз побывал в перспективной ситуации. Если первым в ней побывал A, то B ждет, что A его пустит, и сам на ее пороге играет 1, тогда A видя этот порог и зная, что не его очередь, лучше добровольно сыграет в 2, чем будет тратить ходы. Когда оба побывали в перспективной ситуации, одинаковое количество раз, то счет не помогает, кто будет первым? Чтобы процесс шел, надо быть честным, но быть первым чуть выгоднее, можно схитрить. И все-таки, быть первым при шансе на немедленный успех 1/6, менее важно, чем получать такие шансы несколько раз, чередуясь с соперником, поэтому я бы наверное не стал уже в этом хитрить. Если я с кем-то играю в простую игру, в которой по очереди кидают кубик и выигрывает первым выбросивший 1, то играя вторым, выиграю с вероятностью 5/11, а отказавшись от игры с тем, кто не хочет играть вторым, не выиграю вообще.

Дополнение 4. Только что заметил, что вытекает из очевидности выгоды игры в 1 при возникновении состояния Na>Nb, N < (6/5)*Na, которая гарантирует выигрыш с вероятностью >=0.5. A вот что: если даже A и B добросовестно стремятся к такому состоянию, поддерживая по ходу равные шансы друг для друга, и сводят игру к нему с вероятностью около 1, то поскольку ситуация возникает почти на границе N=(6/5)*max(Na,Nb), то игрок C выиграет с вероятностью почти 0.5, а остальное поделится на A и B, каждому всего по 0.25. Печально.
Печально, потому что это понижает оценку игроком A вероятности выигрыша до 0.25, а если так, то почему бы ему не обеспечить эти 0.25 игрой в 1, когда N опустилось достаточно, чтобы C мог его догнать с вероятностью не больше 0.75. Тогда, очевидно, C выиграет с вероятностью 0.75, а для A и B останется по 0.125. Продолжение рассуждений приводит к 0 для A и B. Сдаюсь.
Edited Date: 2015-06-25 10:03 pm (UTC)

Date: 2015-07-01 06:07 am (UTC)
From: [identity profile] worm-ii.livejournal.com
Если решать классическим методом, учитывая симметричность A и B, то получается 6 неизвестных A_i=B_i — вероятность выбрать i-е число (как для A, так и для B). Стандартно выписывается квадратичная форма, подлежащая максимизации (тут главное не ошибиться в определении, какие случаи являются выигрышными и правильно их посчитать). У меня красивых чисел не получилось, а из солверов под рукой только численный оказался. Ответ примерно такой:
A_1 = 0.3, A_2 = 0.23, A_3 = 0.17, A_4 = 0.12, A_5 = A_6 = 0.09.
Вероятность выигрыша для A (и для B) примерно 0.35.

Date: 2015-07-25 08:02 am (UTC)
From: [identity profile] spartach.livejournal.com
А это никто ещё не посчитал, или просто комментарии скрываются?

Предположил, конечно, что стратегии A и B совпадают. Хоть и не знаю, как легко объяснить, что именно так.
Получилась мерзкая система из 5 линейных уравнений (хотя и не без закономерностей), в ответе получается знаменатель 397, и вероятность успеха А при такой стратегии - 138/397 = 0,3476...

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

Интересно посмотреть, что будет, если 6 устремить к бесконечности (а число игроков оставить прежним).

Интересно

Date: 2015-07-26 01:45 pm (UTC)
From: [identity profile] knop.livejournal.com
скрываются. Сейчас раскрою

April 2017

S M T W T F S
      1
234567 8
9101112131415
16171819202122
23242526272829
30      

Style Credit

Expand Cut Tags

No cut tags
Page generated Sep. 23rd, 2017 11:13 am
Powered by Dreamwidth Studios