?

Log in

No account? Create an account
Задача - Олег Етеревский [entries|archive|friends|userinfo]
Oleg Eterevsky

[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Задача [12 November 2015|15:58]
Oleg Eterevsky
Придумал простую задачку.

Придумайте игру, для которой возможна следующая ситуация. Есть три игрока: A, B, C. Когда A играет с B, он выигрывает с вероятностью 75%, когда B играет с C, B также выигрывает с вероятностью 75%, и когда A играет с C, A тоже выигрывает у C с вероятностью 75%. Все трое играют друг с другом по мере своих сил.

Например. Возьмём шахматы. Вася играет сильнее Пети, и выигрывает у него в 75% случаев. Петя играет сильнее Коли, и тоже выигрывает в 75% случаев. Но тогда Вася будет играть значительнее сильнее Коли и будет выигрывать явно больше чем в 75% случаев, так что шахматы как ответ в этой задаче не подходят. То же со всеми другими обычными играми.

Комментарий. В игре все игроки должны находиться в одинаковых условиях и выигрывать друг у друга только за счёт способностей.
LinkReply

Comments:
[User Picture]From: amarao_san
2015-11-12 03:43 pm (UTC)
Арч против мага против танка.

Танк сносит арча (75%), маг сносит танка (75%), арч сносит танка (75%).

Типовое mmorpg'шное pvp.
(Reply) (Thread)
[User Picture]From: eterevsky
2015-11-12 03:54 pm (UTC)
Имеется в виду, что игроки находятся изначально в одинаковом положении и не имеют разных ролей.

[Сорри, намудрил с комментариями.]
(Reply) (Parent) (Thread) (Expand)
[User Picture]From: psilogic
2015-11-12 03:45 pm (UTC)
обычная колода, ходят по кругу, ходящий вслепую (т.е. вверх рубашкой) выкладывает карту, отвечающий - тоже, потом переворачивают обе карты, ходящий выигрывает, если масти не совпали

Edited at 2015-11-12 03:46 pm (UTC)
(Reply) (Thread)
[User Picture]From: eterevsky
2015-11-12 03:55 pm (UTC)
Но тогда если они меняются ролями, то вероятность выигрыша будет 25%. То есть A и B играют в эту игру много раз, причём чередуясь тем, кто начинает, то вероятность выигрыша будет 50%.
(Reply) (Parent) (Thread) (Expand)
From: bas1234
2015-11-12 04:12 pm (UTC)
Камень-ножницы-бумага. Первый игрок выбирает ножницы с вероятностью q, бумагу с вероятностью 1-q, второй бумагу (q) или камень (1-q), третий камень или ножницы. Осталось найти q.
(Reply) (Thread)
[User Picture]From: eterevsky
2015-11-12 04:15 pm (UTC)
Да, точно. Для камень-ножницы-бумага наверняка параметры можно подобрать. Но есть проще решение.
(Reply) (Parent) (Thread) (Expand)
[User Picture]From: igoralexeev
2015-11-12 07:31 pm (UTC)

А 100% можно?

Слегка переиначенное условие. Возможно, будет интересно.
3 шахматные команды, в каждой команде 3 игрока. Сила игрока определятся целым числом. Если играют 2 игрока, то всегда выигрывает игрок, у которого сила больше (т.е. у которого число, определяющее силу, больше).
При встрече 2-х команд каждый игрок из первой команды играет по одному разу с каждым игроком второй команды. Та команда, которая в такой встрече одержит больше побед, считается сильнее.
А теперь команды и силы игроков в них:
A: 1 6 8
B: 0 5 10
C: 2 4 9
Команда A выигрывает у команды B со счетом 5:4.
Команда B выигрывает у команды C со счетом 5:4.
Команда C выигрывает у команды A со счетом 5:4.
Т.е. A>B, B>C и C>A.

Edited at 2015-11-12 07:34 pm (UTC)
(Reply) (Thread)
[User Picture]From: eterevsky
2015-11-12 08:25 pm (UTC)
Прикольный вариант, мне нравится.
(Reply) (Parent) (Thread)
[User Picture]From: nikolenko
2015-11-12 07:33 pm (UTC)
У тебя почему-то все абсолютно комментаторы пишут про камень-ножницы-бумага, хотя задача вообще не о том. :)

Мне вот непонятно, что значит "только за счёт способностей". Упрощённо говоря: представим, что более сильный игрок выигрывает всегда, но по окончании игры кидают две монетки и с вероятностью 1/4 выигрывает тот, кто в самой игре проиграл. Если ты скажешь, что это очевидно не подходит, то я спрошу, чем это отличается от любого другого рандома в игре.
(Reply) (Thread)
[User Picture]From: eterevsky
2015-11-12 08:23 pm (UTC)
Это практически то решение, которое я имел в виду. Только у меня бросали монетку, и если совпало, то играли условно в шахматы, а иначе выигрывал тот, у кого орёл.
(Reply) (Parent) (Thread)
[User Picture]From: shurik_s
2015-11-12 11:12 pm (UTC)
Я, как и большинство, с первого раза прочитал эту задачу неправильно.

Но мне стало интересно немного другое. В твоем и Сережином варианте, от разницы в силе игры ничего не зависит. И это меня огорчает. Хочется добавить условие, чтобы для каждой заданной вероятности p<75% существовал игрок D проигрывающий игроку А с вероятностью p.

Это заметно все усложняет, но дает другой интересный срез. Если сила игрока определяется одним числом, а вероятность победы определяется непрерывной строго монотонной функцией от разности, то достаточно очевидно, что такого не бывает.

Осмысленным классом функций представляется непрерывная функция f(x,y) строго возрастающая по x, при любом фиксированном y, и строго убывающая по y при любом фиксированном x. Супремум и инфинум должны быть равны 1 и 0 соответственно и f(x,y) = 1 - f(y,x). Тут менее очевидно, но тоже кажется ситуация описанная выше невозможна.

Раз при одном параметре характеризующем силу такое не возможно, то у нас остается попробовать характеризовать силу большим количеством чисел. Например, для тех же шахмат, можно считать, что у человека есть умение играть белыми (w_i) и умение играть черными (b_i). Вероятность победить в партии это 1/2 *f(w_i,b_j) + 1/2 *f(b_i,w_j), если вероятность играть за белых и черных одинаковая.

Например, для f(x,y)=x/(x+y) у меня не получилось сходу найти решение для 75%, возможно его нету, но решение существует если 75% везде заменить на 60%. Как я понимаю, принципиально это сути задачи не меняет.

Ну а теперь главный вопрос, а есть ли такая f(x,y), для которой в описанной ситуации будут существовать решения для любой вероятности из диапазона [50%, 100%].




(Reply) (Thread)
[User Picture]From: nikolenko
2015-11-13 05:28 am (UTC)
Я тут главное, чего не понимаю, -- это мотивации. :)

Умение играть белыми и чёрными разделить, безусловно, было бы хорошо, но мы же будем знать заранее, кто чем играет, и в твоей модели это всё равно что просто два разных игрока.

В том же ЧГК, с другой стороны, можно придумать латентные факторы у вопроса, которые бог знает что значат и бог знает чему равны, но тогда это, наверное, совсем другая модель получится.
(Reply) (Parent) (Thread) (Expand)
[User Picture]From: eterevsky
2015-11-13 06:50 am (UTC)
Вообще говоря, с точки зрения игр никаких гарантий строгой монотонности, мне кажется, нет. Легко можно представить себе игру в которой есть три стратегии A, B и C, такие что A выигрывает у B и C вероятностью x, и B тоже выигрывает у C с вероятностью x. Те самые камень-ножницы-бумага с правильно подобранными вероятностями, про которые писали другие комментаторы -- вполне подходят.

Вполне возможно силу игры определять не числом, а вектором. И этот вектор даже вполне можно эффективно искать аналогично рейтингу из следующего поста. И скорее всего, даже если не получится придумать решение с одномерным рейтингом, оно найдётся с многомерным.
(Reply) (Parent) (Thread) (Expand)
[User Picture]From: halif
2015-11-14 09:12 am (UTC)
троеборье, пусть шахматы, шашки, го.

В шахматах первый сильней второго, второй сильнее третьего.
В шашках 2>3>1
В го 3>1>2.

Игра - суммарный зачет побед.
Остается аккуратно рассчитать, какая должна быть разница сил в одиночных играх (в виде вероятности победы), чтобы итоговый результат был 75% в каждой паре игроков.
(Reply) (Thread)
[User Picture]From: eterevsky
2015-11-14 10:19 am (UTC)
Не сразу очевидно, что это возможно.
(Reply) (Parent) (Thread)