Мне кажется, мы незаслуженно рано забыли эту замечательную задачу.
Напомню ещё раз условие:
3 человека стреляются.
Остаться должен только один.
Стреляют по-очереди (по кругу).
Первый выбирается жребием.
Каждый сам вибирает, в кого он сейчас стреляет.
Можно стрелять в воздух.
Меткости (т.е. вероятности попадания) у каждого — p1,p2,p3.
Найти оптимальные стратегии и вероятности w1,w2,w3 остаться в живых для каждого.
Для p = { 1, 1, 0.5 } был получен замечательный ответ w = { 0.25, 0.25, 0.5 }
1) Предлагаю новую задачу: p = { 1, 0.5, 0.5 }
У меня получился совершенно замечательный ответ для w (если не соврал нигде )
2) Может есть ещё какие простые и красивые случаи?
3) А может, найдётся гигант, который сделает это в общем виде?
Здравствуйте, Pushkin, Вы писали:
P>Мне кажется, мы незаслуженно рано забыли эту замечательную задачу. P>Напомню ещё раз условие:
P>3 человека стреляются. P>Остаться должен только один. P>Стреляют по-очереди (по кругу). P>Первый выбирается жребием. P>Каждый сам вибирает, в кого он сейчас стреляет. P>Можно стрелять в воздух. P>Меткости (т.е. вероятности попадания) у каждого — p1,p2,p3. P>Найти оптимальные стратегии и вероятности w1,w2,w3 остаться в живых для каждого.
P>Для p = { 1, 1, 0.5 } был получен замечательный ответ w = { 0.25, 0.25, 0.5 }
Чем же он замечателен ...
Если ВСЕ 3 человека логически стремятся к max соотношению, то мне кажется ,что 100%-ки будут стрелять в воздух, пока не будут 3-ми в очереди !!!
Тогда они палят в 100% и потом 50%+25% ...
P>1) Предлагаю новую задачу: p = { 1, 0.5, 0.5 } P>У меня получился совершенно замечательный ответ для w (если не соврал нигде )
P>2) Может есть ещё какие простые и красивые случаи?
P>3) А может, найдётся гигант, который сделает это в общем виде?
Здравствуйте, KGP, Вы писали:
P>>Для p = { 1, 1, 0.5 } был получен замечательный ответ w = { 0.25, 0.25, 0.5 }
KGP>Чем же он замечателен ...
Тем, что мазила выигрывает у крутых. И сильно выигрывает. И те ничего не могут сделать даже несмотря на то, что разрешено стрелять в воздух, и казалось бы, делай они это через раз, они могли бы стать точно такими мазилами.
KGP>Если ВСЕ 3 человека логически стремятся к max соотношению, то мне кажется ,что 100%-ки будут стрелять в воздух, пока не будут 3-ми в очереди !!!
Вот этого я совсем не понял. Крутые в воздух, конечно, никогда стрелять не должны. В воздух всё время (до последнего выстрела) стреляет мазила. (Десяток постов назад есть эта задача, там всё написано).
Здравствуйте, Pushkin, Вы писали:
P>1) Предлагаю новую задачу: p = { 1, 0.5, 0.5 } P>У меня получился совершенно замечательный ответ для w (если не соврал нигде )
w={ 0.5, 0.25, 0.25 }
Первому все равно, кого убивать. Далее оставшийся с вероятностью 0.5 промахнется по первому...
Второму/третьему нужно стрелять в первого ("самое сильное звено" ).
С вероятностью 0.5 он промахивается и будет застрелен.
Если повезет (0.5), то между вторым и третьим состоится честная дуэль (0.5).
P>2) Может есть ещё какие простые и красивые случаи?
P>3) А может, найдётся гигант, который сделает это в общем виде?
Имхо, общее правило такое: нужно стрелять в самого меткого.
Придерживаясь такой стратегии, для p={x,y,z}, x>=y>=z, получим
(предполагая, что после одного раунда выжившие мирятся)
Здравствуйте, Кодт, Вы писали:
К>w={ 0.5, 0.25, 0.25 }
У меня другой ответ...
К>Первому все равно, кого убивать. Далее оставшийся с вероятностью 0.5 промахнется по первому...
Итак твой ответ годится, если начинает крутой.
К>Второму/третьему нужно стрелять в первого ("самое сильное звено" ). К>С вероятностью 0.5 он промахивается и будет застрелен.
Совсем не обязательно, может крутой не злопамятный и выберет другого мазилу.
К>Если повезет (0.5), то между вторым и третьим состоится честная дуэль (0.5).
Вау! Честная дуэль?! Кто-то ж начинает! Это маленькая (совсем простая) задача в задаче: две мазилы стреляют по-очереди, найти вероятность остаться живым для первого и второго.
Здравствуйте, Кодт, Вы писали:
К>Имхо, общее правило такое: нужно стрелять в самого меткого.
Если ты убъёшь самого меткого, то в дуэли оставшихся двоих у твоего противника будет право первого хода.
Поэтому твоя простая замечательная стратегия действительно работает в случае, когда не столь важно, кто будет стрелять первым, т.е. в дуэли трёх мазил, (p1,p2,p3<<1) Здесь все вычисления легко довести до конца и получить понятные ответы.
Здравствуйте, Pushkin, Вы писали:
P>Может есть ещё какие простые и красивые случаи?
Для p = { 0.5, 0.5, 0.5 } все будут стрелять в воздух и дуэль не кончится !
Забавно, что и для p = { 1, 1, 1 } тоже. И вообще для любых равных соперников.
Здравствуйте, Pushkin, Вы писали:
К>>Имхо, общее правило такое: нужно стрелять в самого меткого.
P>Если ты убъёшь самого меткого, то в дуэли оставшихся двоих у твоего противника будет право первого хода.
А если я убью самого криворукого, то моим противником окажется самый меткий. Вот я обрадуюсь!
P>Поэтому твоя простая замечательная стратегия действительно работает в случае, когда не столь важно, кто будет стрелять первым, т.е. в дуэли трёх мазил, (p1,p2,p3<<1) Здесь все вычисления легко довести до конца и получить понятные ответы.
Кстати, уточни пожалуйста, как проходит турнир.
Первый выбирается жеребьевкой. А второй (если первый промахнулся)?
Здравствуйте, Кодт, Вы писали:
P>>Если ты убъёшь самого меткого, то в дуэли оставшихся двоих у твоего противника будет право первого хода. К>А если я убью самого криворукого, то моим противником окажется самый меткий. Вот я обрадуюсь!
Дык блин, можно же и в воздух стрелять!
К>Кстати, уточни пожалуйста, как проходит турнир. К>Первый выбирается жеребьевкой. А второй (если первый промахнулся)?
Следующий по часовой стрелке. А если он убит, то следующий.
(Кстати, там в головном посте всё подробно написано, между прочим. )
...
P>1) Предлагаю новую задачу: p = { 1, 0.5, 0.5 } P>У меня получился совершенно замечательный ответ для w (если не соврал нигде )
Обозначим противников А(Р=1) и Б1, Б2 (Р=1/2)
Начнем с А.
1) С Р=1/3, первый ход достанется А.
Он убивает одного из Б, затем оставшийся с Р=1/2 убивает А,
затем А убивает Б. Вероятность убития А равна 1/3 * 1/2 = 1/6.
2) С Р=1/3, первый ход достанется одному из Б, а затем перейдет к А.
Б с Р=1/2 убивает А, затем А убивает одного из Б, затем
оставшийся Б с Р=1/2 убивает А, затем А убивает Б.
Вероятность остаться в живых у А равна 1/4, соответственно
убития 1/3 * (1 — 1/4) = 1/4.
3) С Р=1/3, первый ход достанется одному из Б, затем другому,
а потом перейдет к А.
С Р=1/2 Б убивает А, затем с Р=1/2 другой Б убивает А, потом А
убивает одного из Б, а оставшийся Б с Р=1/2 убивает А, затем А
убивает Б.
Считаем для вероятность остаться в живых:
{Выстрел одного Б}1/2 * {Выстрел другого Б}1/2 * {оставщийся Б}1/2 = 1/8
соответственно, вероятность убития А в этом случае равна
1/3 * (1 — 1/8) = 1/3 * 7/8 = 7/24
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, mrhru, Вы писали:
M>>Вот красивый случай р = {_2_, 0.5, 0.5}
К>Это что? Одним махом двоерых побивахом? Дуэль на гранатах, что ли?
Нет, это у него ствол пистолета раз-два-яи... э... двойной ствол такой.
Евгений, с приветом (но без остроумной подписи, к сожалению )
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, mrhru, Вы писали:
M>>Вот красивый случай р = {_2_, 0.5, 0.5}
К>Это что? Одним махом двоерых побивахом? Дуэль на гранатах, что ли?
M>>Для него w = (3/4, 1/8, 1/8)
К>Еще бы, с таким монстром воевать.
Гм, мысль о гранатах навела на ещё один интересный случай
р = {3, 0.5, 0.5}
в котором суммарная вероятность выжить у участников дуэли, становится меньше 1 .
Евгений, с приветом (но без остроумной подписи, к сожалению )
M>Обозначим противников А(Р=1) и Б1, Б2 (Р=1/2) M>Начнем с А.
M>1) С Р=1/3, первый ход достанется А. M>Он убивает одного из Б, затем оставшийся с Р=1/2 убивает А, M>затем А убивает Б. Вероятность убития А равна 1/3 * 1/2 = 1/6.
Аккуратнеее!
1/6 это вероятность того, что первый ход был у A, но он всё равно был убит.
M>2) С Р=1/3, первый ход достанется одному из Б, а затем перейдет к А.
Не обязательно — может ход до А и не дойдёт.
M>3) С Р=1/3, первый ход достанется одному из Б, затем другому, M>а потом перейдет к А. M>С Р=1/2 Б убивает А, затем с Р=1/2 другой Б убивает А, потом А M>убивает одного из Б, а оставшийся Б с Р=1/2 убивает А, затем А M>убивает Б.
Вот здесь моё главное несогласие! Тот Б, который стоит сразу после А не будет стрелять в А, он предпочтёт выстрел в воздух. Действительно, вероятность выжить, если он убъёт А — 1/3 (дуэль двух Б, где начинает противник). А если не убъёт, то 1/2*2/3 + 1/2*1/4 = 11/24 — существенно больше (здесь первый член соответствует случаю, когда у второго Б получилось убить А, а второй — когда не получилось). Таким образом, оптимальная стратегия для первого мазилы — сваливать всю работу на второго. И второй ничего не может поделать — его оптимальная стратегия — таки стрелять в А!
Вероятность для А остаться в живых
w=1/3*1/2+2/3*1/2*1/2=1/3
Для Б1 (тот, кто стоит сразу после А и стреляет в воздух)
w=1/3*1/4+2/3*(1/2*1/4+1/2*2/3)=7/18
Для Б2 (тот, кто стоит перед А и стреляет в него)
w=1/3*1/4+2/3*(1/2*1/4+1/2*1/3)=5/18
Итак, крутой получает свою "честную" 1/3, а две мазилы располагаются тоже вокруг 1/3 — тот, кто "в тени" крутого получает чуть больше, а второй чуть меньше.
Забавно, что если Б1 имеет меткость 0.5000001, то крутому уже не всё равно, в кого стрелять. И значит Б1 теперь не может отсиживаться за спиной Б2 (тот стрельнет в воздух!). Вся ситуащия радикально меняется и все ответы претерпевают разрыв!
wA =5/12
wБ1=1/18
wБ2=19/36
Удивительный ответ! Б1 лишь слегка выпендрился и получил исчезающую вероятность выжить, в то время как скромный Б2 выживает с вероятностью больше половины. А бедный крутой снова в заднице
...
P>Итак, крутой получает свою "честную" 1/3, а две мазилы располагаются тоже вокруг 1/3 — тот, кто "в тени" крутого получает чуть больше, а второй чуть меньше.
P>Забавно, что если Б1 имеет меткость 0.5000001, то крутому уже не всё равно, в кого стрелять. И значит Б1 теперь не может отсиживаться за спиной Б2 (тот стрельнет в воздух!). Вся ситуащия радикально меняется и все ответы претерпевают разрыв!
P>wA =5/12 P>wБ1=1/18 P>wБ2=19/36
P>Удивительный ответ! Б1 лишь слегка выпендрился и получил исчезающую вероятность выжить, в то время как скромный Б2 выживает с вероятностью больше половины. А бедный крутой снова в заднице
Интересно, в первом случае крутому всё равно в кого стрелять — и вероятность выжить равна 1/3.
Во втором случае, он выбирает Б1 из-за микроскопической разности и повышает свои шансы до 5/12 (> 1/3).
Следовательно, ему и в первом случае следует стрелять в Б1 — лишь для того, чтобы Б1 поменял свою стратегию!!! Так?
Евгений, с приветом (но без остроумной подписи, к сожалению )
Здравствуйте, Pushkin, Вы писали:
P>3 человека стреляются. P>Остаться должен только один. P>Стреляют по-очереди (по кругу). P>Первый выбирается жребием. P>Каждый сам вибирает, в кого он сейчас стреляет. P>Можно стрелять в воздух. P>Меткости (т.е. вероятности попадания) у каждого — p1,p2,p3. P>Найти оптимальные стратегии и вероятности w1,w2,w3 остаться в живых для каждого.
Задача удивительно сложная и красивая. У меня получилось решить её в 3-х частных случаях. В этом посте первый:
Пусть меткости равны (1,1,p) здесь p — параметр, любое число от 0 до 1 (включительно)
Ясно, что при малых p крутые стреляют друг в друга, не обращая внимание на мазилу, а потом разбираются с ним. Вероятность выжить для мазилы мала, а для крутых определяется шансом получить первый ход. Для того, кто стоит после мазилы он равен 2/3, а для того, то перед — 1/3. Это очеь важно — крутые не симметричны! В условии задачи сказано, что бросается жребий, кому первому стрелять, но НЕТ жребия кому как встать! Поэтому все ответы несимметричные — если надо усреднить и расстановке, можно всегда это сделать в конце.
С другой стороны, ясно, что при p=1 никто не захочет друг в друга стрелять. Первый убивший следующим ходом будет убит сам! Поэтому дуэль будет продолжаться вечно. Как это всё перевести в цифры? Как решить, какая стратегия выгоднее — позволяющая выжить с вероятностью 2/5 или вечная стрельба в воздух? Мне удалось найти на мой взгляд разумный выход из этой неприятности. Пусть на каждом выстреле есть очень маленькая (1/1000) вероятность того, что пистолет взорвётся и будет убит сам стреляющий. Это значит, что при длительной стрельбе в воздух всех троих будет по сути бросаться жребий, кому умереть (но обратите внимание, это не то же самое, что жребий кому выжить!). Например, три крутых очевидно предпочтут стрелять в воздух и выжить с вероятностью 1/3 (здесь везде 1/3 — что умереть от взрыва, что выжить в результате), чем кого-то убить и точно умереть самому.
Очевидно, есть такое значение p, при котором происходит перелом — сиена стратегий. Расчёты показали, что это p=2/3. При меньших p крутые палят друг в друга, а мазила стреляет в воздух. Вероятности выжить:
w1=2/3*(1-p)
w2=1/3*(1-p)
w3=p
Выйдя из точки (2/3,1/3,0) при p=0
пройдя затем точку оригинальной задачи (1/3,1/6,1/2) при p=0.5
мы достигаем при дикого превосходства мазилы (2/9,1/9,2/3) в критической точке p=2/3
Но дальше лафа кончается — в мазиле вдруг начинают видеть достойного противника и все начинают стрелять в воздух, ожидая божьего суда. Но вероятности выжить_в_итоге не одинаковы.
w1=2/3-p/3
w2=1/3
w3=p/3
Первый крутой опять имеет преимущество над вторым (он ведь стреляет после мазилы), а мазила наконец на законном последнем месте. При p=1 приходим к законному результату 1/3, 1/3, 1/3
Самое удивительное в ответах конечно то, что в критической точке все фунции рвутся и очень сильно!
Начинается всё при p=0 гарантией жизни для крутого и смерти для мазил.
Но затем при p=0.5 крутой имеет всего 1/3, а мазилы располагаются по обе стороны него симметрично.
При p=2/3 обе мазилы сильно обгоняют крутого w=(5/27,14/27,8/27).
Но в этот момент крутой наконец их пугается и начинает палить в воздух. В тот же момент второй мазиле тоже перестаёт хотеться убить крутого и все палят в воздух. Само собой рутой в результате имеет некоторое преимущество
w1=(2-p)/3
w2=1/(2-p)/3
w3=(1+p-pp)/(2-p)/3
К p=1 всё спокойно приходит к (1/3,1/3,1/3)
Таким образом, как и в случае (1,1,p), здесь тоже наблюдается полный разрыв всех функций в критической точке.
Ещё забавно, что в случае (1,p+0.001,p) вся картинка радикально меняется — крутому становится не всё равно в какую мазилу стрелять и все стратегии от этого меняются. У "крутого мазилы" почти нет шансов выжить, а честный мазила имеет большое преимущество даже над настоящим крутым
Стратегии очевидны — стреляй в самого крутого из двух. Из за маленьких вероятностей здесь перестают играть роль очерёдности ходов. Поэтому эти ответы годятся для всех (не обязательно малых) вероятностей, если в исходную задачу внести правило, что стреляют все всегда по жребию.
M>Интересно, в первом случае крутому всё равно в кого стрелять — и вероятность выжить равна 1/3. M>Во втором случае, он выбирает Б1 из-за микроскопической разности и повышает свои шансы до 5/12 (> 1/3). M>Следовательно, ему и в первом случае следует стрелять в Б1 — лишь для того, чтобы Б1 поменял свою стратегию!!! Так?
После того, как крутой стрельнет в Б1, тот уже никак не сможет поменять стратегию
).
Перекуём баги на фичи!
)
