?

Log in

Задача - Олег Етеревский [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)
[User Picture]From: amarao_san
2015-11-12 04:03 pm (UTC)
В mmorpg игроки в одинаковых условиях, а "профессию" и "скиллы" они выбирают в рамках игрового процесса (то есть их выбор можно считать "ходами").

Кстати, как различить A, B и С? Порядковый игрока? Сторона доски? Любые три? Если любые три, как выполнить условие A>B, если A и B произвольные?
(Reply) (Parent) (Thread)
[User Picture]From: eterevsky
2015-11-12 04:07 pm (UTC)
Интересный вариант с выбором "профессий". Пожалуй, он подходит под то, что я имею в виду.

На счёт A, B, C -- представь, что это три шахматные программы с тремя разными алгоритмами. Или три физических шахматиста, которые друг с другом играют.
(Reply) (Parent) (Thread)
[User Picture]From: amarao_san
2015-11-12 04:41 pm (UTC)
Но поведение программ и шахматистов не детерминировано.

То есть я не понимаю, как в игре с свободой выбора можно закладывать в правила, что игрок А всегда будет делать ход E15-D16. Точнее, закладывать можно, но это будет противоречить равноправию игроков, либо этот обязательный ход не влияет на ход партии (т.к. его делать все).

Я понял суть проблемы. Ты говоришь "выигрывает в 75% случаев". То есть аппелируешь к теорверу. А теорвер со своими шариками подразумевает, что если ты раньше вытягивал шарики с вероятностью 25%, то от перестановки урн вероятность не поменяется.

А в игре игрок А, обнаружив, что его стратегия не приводит к выигрышу, может начать действовать иначе, то есть вероятность становится функцией от предыдущих "вытягиваний". Что явно выводит нас за пределы теорвера.

Если мы говорим про "теорию игр", то мы не можем накладывать такие условия, потому что по теории игр игроки вольны выбирать себе любую стратегию (более того, предполагается, что она эффективная) - и если игрок B в игре A обнаруживает, что есть статегия C>A, то нет нет причин, почему он не может не использовать статегию C.

Если мы под "игрок" подразумеваем конкретную стратегию, то можно придумать игру с тремя разными статегиями, которые дают 75% выигрыш против одной стратегии, но дают 75% выигрыш против другой.

Даю минималистичное определение такой игры: камни-ножницы-бумага, в которой камни с 75% побеждают ножницы и т.д.

Под "игроком" в этом случае будет подразумеваться выбор одного из трёх вариантов.
(Reply) (Parent) (Thread)
[User Picture]From: eterevsky
2015-11-12 04:46 pm (UTC)
Камень-ножницы-бумага -- ок.

Формализация вероятности -- такая. Предположим, что после каждой партии каждый игрок её забывает, то есть остаётся лишь со своим первоначальным опытом.
(Reply) (Parent) (Thread)
[User Picture]From: amarao_san
2015-11-12 04:57 pm (UTC)
Ну, то есть, упрощая человека до минимума, то "стратегия". Так?
(Reply) (Parent) (Thread)
[User Picture]From: eterevsky
2015-11-12 05:00 pm (UTC)
Ага.
(Reply) (Parent) (Thread)
[User Picture]From: amarao_san
2015-11-12 06:10 pm (UTC)
Ну тогда остаётся свести игру к минимальной, в которой есть три возможные стратегии (один ход, три выбора, независимые для каждого игрока), исход определяется выбором и рандомом. Или, если рандом в правилах не нравится, то описать матобъект такой, чтобы можно было описанные правила к нему применить. Кольцо на интах, или предопределённый набор чисел.

(Reply) (Parent) (Thread)
[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)
[User Picture]From: psilogic
2015-11-12 04:02 pm (UTC)
Ну можно правилами запретить меняться ролями - после первой жеребьевки роли распределяются навсегда, а жеребьевка идет в равных условиях.

Хотя способности тут ни при чем.

Если именно на способностях, то можно шахматный пример в стиле воин-вор-маг, но не по ролям, а по способностям: Вася лучше всех (в 4 раза) играет блиц, Петя - суперблиц, а Миша в 4 раза лучше других при классическом регламенте. Если три вида регламента играются одинаково часто, и соперники выбираются равновероятно, то будет то, что вы написали.
(Reply) (Parent) (Thread)
[User Picture]From: eterevsky
2015-11-12 04:10 pm (UTC)
Можно поподробнее? Есть три варианта игры, игроки в начале случайным образом выбирают один из них? Ещё раз, как там получаются нужные вероятности?
(Reply) (Parent) (Thread)
[User Picture]From: psilogic
2015-11-12 04:29 pm (UTC)
а, не, гоню, не получится, если не ограничивать участие :)
(Reply) (Parent) (Thread)
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)
From: bas1234
2015-11-12 05:33 pm (UTC)
Я как-то плохо прочитала условие, и решила вариант с A>B>C>A...
(Reply) (Parent) (Thread)
[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)
[User Picture]From: shurik_s
2015-11-13 07:47 am (UTC)
Ну в описанном мной варианте, это действительно два независимых человека, но можно говорить о общем рейтинге и поправке на белость. Тогда победа за черных повышает и рейтинг в игре за белых.
А так да, я просто пришел к тому что хочется придумать хорошие функции вычисляющие вероятности по рейтингам. Ну то есть, что у нас будет хорошо учится и предсказывать.
То есть я пытаюсь придумать преобразование вроде probit или logit которое даст удобную регрессию. :-)
(Reply) (Parent) (Thread)
[User Picture]From: nikolenko
2015-11-13 08:27 am (UTC)
О поправке на белость говорят в моделях Брэдли-Терри, например.
(Reply) (Parent) (Thread)
[User Picture]From: eterevsky
2015-11-13 06:50 am (UTC)
Вообще говоря, с точки зрения игр никаких гарантий строгой монотонности, мне кажется, нет. Легко можно представить себе игру в которой есть три стратегии A, B и C, такие что A выигрывает у B и C вероятностью x, и B тоже выигрывает у C с вероятностью x. Те самые камень-ножницы-бумага с правильно подобранными вероятностями, про которые писали другие комментаторы -- вполне подходят.

Вполне возможно силу игры определять не числом, а вектором. И этот вектор даже вполне можно эффективно искать аналогично рейтингу из следующего поста. И скорее всего, даже если не получится придумать решение с одномерным рейтингом, оно найдётся с многомерным.
(Reply) (Parent) (Thread)
[User Picture]From: shurik_s
2015-11-13 07:40 am (UTC)
Идея монотонности возникает из следующих соображений, если у нас есть вектор описывающий рейтинги игроков, то если рейтинги игроков A и B отличаются в одной позиции и на этой позиции рейтинг A больше, то вероятность что A победит C должна быть больше чем вероятность, что B победит C. Иначе теряется смысл называть это рейтингом. Единственный момент когда можно уйти от строгой монотонности, это когда вероятность победы равна 1 или 0. Но я считаю, что таких вероятностей быть не должно ибо мало ли что...
(Reply) (Parent) (Thread)
[User Picture]From: nikolenko
2015-11-13 08:26 am (UTC)
Ну так рейтинг - это всего лишь проекция гораздо более сложного процесса...
(Reply) (Parent) (Thread)
[User Picture]From: shurik_s
2015-11-13 08:34 am (UTC)
Конечно, но мы хотим чтобы эта проекция соответствовала нашему бытовому восприятию. Больше рейтинг - игрок круче.
(Reply) (Parent) (Thread)
[User Picture]From: nikolenko
2015-11-13 08:42 am (UTC)
Ну для крайнего примера можно рассмотреть рейтинг по какому-нибудь пятиборью. Вот там чётко понятно насчёт фич и размерности. :)
(Reply) (Parent) (Thread)
[User Picture]From: shurik_s
2015-11-13 09:01 am (UTC)
В пятиборье особые правила пересчета секунд в очки, что несколько меняет всю ситуацию.
А задача предсказывать время прохождения дистанции выглядит гораздо более сложной чем предсказание порядка на финише.
(Reply) (Parent) (Thread)
[User Picture]From: nikolenko
2015-11-13 10:19 am (UTC)
Нет, она, конечно, проще: у тебя будет ещё информация о времени, там наверняка попроще модель получится. Как у меня в ЧГК с плюсиками.
(Reply) (Parent) (Thread)
[User Picture]From: eterevsky
2015-11-13 11:03 am (UTC)
Вообще для рейтинга достаточно и более слабого условия: что для x > 0 f(x) > 0.5 и f (не строго) монотонна. Это значит, что если рейтинг одного игрока больше рейтинга другого, то он выигрывает с вероятностью больше половины. Условие "псевдо-транзитивности" (что если A играет лучше B, а B лучше С, то A играет сильно лучше C) a priori выполняться вовсе не обязано.

Вот представим себе, скажем, фехтование. Пускай есть два трюка X и Y, которые позволяют выиграть дуэль у человека, который не знает, как от них защищаться с вероятностью, скажем 60%. Пускай A не знает ни одного из них, B знает только X, а C знает и X, и Y. Тогда B может применить против A трюк X, C против B трюк Y, а C против A либо X, либо Y, но лишний трюк не даёт ему дополнительного преимущества. Мне кажется, нормальная модель.
(Reply) (Parent) (Thread)
[User Picture]From: shurik_s
2015-11-13 11:07 am (UTC)
Ну не строгая монотонность усложняет определение оптимальной точки на плато. Очевидно, что это хорошо будет работать для дискретных ситуаций, но тогда f может быть просто ступенчатой.
(Reply) (Parent) (Thread)
[User Picture]From: eterevsky
2015-11-13 11:16 am (UTC)
Дык форму функции f тоже можно оптимизировать относительно predictive power. И она может быть разной для разных игр.
(Reply) (Parent) (Thread)
[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)