Comments 29
Тем временем нормальные люди вытягивают нумерованные жетоны.
Я туплю? или можно взять например пять 10-тигранников например, каждому по очереди присваиваем числа по очереди от 1 до 25 (первый кубик 1, второй 2..) и потом от 50 до 26. Вот вам и суммы одинаковые на кубиках и вероятности. На что 15 лет люди потратили? :D
На что 15 лет люди потратили?
Хоть математику немного подучили, всяко полезнее, чем просто кидать 20-гранники на инициативу.
Если взять 10-гранные кубики и 3 игроков, то кубики "нечестные". Всего может быть 1000 вариантов бросков (10*10*10), а 1000 на 3 не делится. Значит кто-то выигрывать будет чаще других.
Они искали кубики так, чтобы 2/3/4/5 игроков брали любые из этих кубиков и шансы были равны
теперь понял где туплю) спасибо :)
При чем здес "тысяча вариантов на троих"? Важно, чтобы значения в бесконечном количестве бросков выпадали так, чтобы правило "больше-меньше" работало взаимно равновероятно. То есть кости однозначно не только выбирали лучшего, но ещё и расставляли всех в рейтинге.
чтобы правило "больше-меньше" работало взаимно равновероятно
Оно не может работать равновероятно, потому что элементарных исходов 1000. Вероятность любого события составляется из этих элементарных исходов, а значит любая вероятность будет суммой скольких-то 1/1000. Значит, искомую вероятность 1/3 вы никак не получите.
Вообще, из попарной справедливости костей не следует, что они справедливы группой.
Например, пусть у нас 3 кости которые дают вот такие перестановки с такими вероятностями:
1 2 3 - 1/10 - с вероятностью 1/10 первая кость даст максимальное число, потом вторая кость, а третья - минимальное число.
1 3 2 - 2/10
2 1 3 - 2/10
2 3 1 - 2/10
3 1 2 - 2/10
3 2 1 - 1/10
Можете убедиться, что любая пара выпадет с вероятностью 1/2. Например, 1<2 в первой, второй и предпоследней строке, что дает (1+2+2)/10 = 1/2 - ровно половина случаев.
Однако тут 1 идет первым с вероятностью 3/10, 2 - 4/10, 3 - 3/10. Нечестно, 2 выигрывает чаще других.
Надо же не сумму на костях делать одинаковой, а вероятности выигрыша.
Ваша система, кстати, гарантирует что каждая пара костей честная - одна выиграет у другой с вероятностью 1/2, ведь все исходы можно сгруппировать в парочки. Пусть x выкинул первый игрок, y -второй: (x,y) <-> (51-x, 51-y). В каждой паре исходов выигрывает то один то другой игрок.
Но вот это не гарантирует общую честность. Если играет 3 или более игроков, то первая кость выигрывает заметно чаще.
для до 6 игроков достаточно одного обычного кубика: говоришь ты "первый/один", бросаешь кубик и отсчитываешь выпавшее число
6 человек садятся в круг и договариваются ходить по часовой стрелке.
Первым номером назначают самого младшего, остальные получают номера по часовой стрелке по возрастанию.
Младший бросает кубик, и получаем номер того, с кого начинается ход.
Для Харшбаргера это математическая задача. Уверен, что если бы он играл сам, то вовсе не против был бы бросать несколько раз. Его цитата о выигрыше нескольких секунд этот факт подтверждает.
Не очень понял, где в моем варианте бросают несколько раз? Только один раз.
Да, я занимаюсь на досуге разработкой [не издаваемых] настолок, и, как понимаю, здесь нужно было реализовать вариант, чтобы в каждом раунде порядок ходов формировался случайно.
Но это грозит "распадом связности" - так, в случае ходов по кругу или по некому правилу, определяемому в процессе игры, это становится еще одним "оптимизируемым фактором", т.е. тем, что можно учитывать в дальнейших прогнозах. В случае, если каждый раунд ходы определяются случайно, случайности становится слишком много, ценность стратегий, прогнозов девальвируется, и это ухудшает удовольствие от игры.
Вы придумываете какие-то обходные способы решить проблему - всё это Харшбаргера не интересует. Он таких способов и сам может придумать пачку. Для него это исключительно математическая задача с заданными условиями. Если же бы он был игрок, то его бы не затруднило потратить несколько лишних секунд и для повторных бросков ради определения чего надо.
при игре втроём, вчетвером или впятером все возможные порядки результатов остаются равновероятными
То есть за один бросок определяется не только победитель, но так же второе, третье и четвертое места?
но ведь если числа на кубиках не повторяются, значит только на одном из них есть например цифра 1 (самая меньшая из использованных) - разве это не даст преимущество его владельцу?
Решение чрезмерное для заявленной задачи. Особенно если допустимо бросить несколько именованых (разноцветных) кубиков одновременно - это ничем математически не отличается от нескольких последовательных бросков.
Для определения первого из пяти игроков достаточно бросить пятигранный кубик, для первого из четырёх - 4-хгранный и так далее. По желанию, все четыре кубика можно бросить одновременно. Такие броски определят и первого, и всю последовательность инициативы.
Но они переформулировали математическую задачу, искали в ограниченной области решений, и это тоже интересно как упражнение.
Для определения первого из пяти игроков достаточно бросить пятигранный кубик, для первого из четырёх - 4-хгранный и так далее
Интересует конструкция 3 гранного кубика.
это обычный 6-ти гранный кубик на котором числа 1,2,3 повторяются по 2 раза.
Тогда уж проще просто назначить числам от 1 до 6 различные перестановки трех последних игроков и одним броском шестигранного кубика определить их порядок.
А еще можно взять кубик с n! сторон и одним броском найти порядок всех n игроков.
Но задача не об этом. Это теоретическая задача о существовании костей, любое подмножество которых честное. И решают ее не потому что не знают, как еще определить порядок игроков в ДнД, а потому что это офигенно.
Самое интересное (с математической т.з.) в этой задаче не решено, а именно обобщение для N. Какой-нибудь способ генерации для N кубиков. А так же теоретический лимит, для какого N это возможно. Навскидку выглядит, как будто никакого лимита нет, но после этого я уже ничему не удивлюсь.
вроде бы, можно. Вот тут доказано, что всегда можно найти N permutation-fair кубиков, правда, разного размера. Но, насколько я понимаю, их всегда можно свести к кубикам одного размера (взяв наибольшее общее частное их количества граней, потом повторив каждую грань столько раз, что все кубики будут одинаковыми, но с повторяющимися числами, потом заменив каждое повторяющееся число на последовательность чисел, и увеличив все числа больше его соответственно).
Я понимаю, что это перевод, но все же на Хабре хочется технических подробностей. Собсвенно, тут в комментариях люди пытаются угадать, что же за задача решается. В статье нет ни формулировки, ни решения.
Вместо статьи о том, что математики делают математику, один бородатый, а второй из Канады, хочется видеть что-то вроде такой статьи:
Сформулировать условие - n игроков бросают n кубиков с d гранями каждый, с различными числами на гранях 1 … nd. Выигрывает тот, кто выкинул максимальное число. Можно ли обеспечить равновероятность выигрыша каждым игроком?
Рассказать, что есть разные варианты задачи
каждый игрок выигрывает с равной вероятностью
любые k <= n игроков могут взять произвольные k кубиков и выиграть с равной вероятностью
результат обеспечивает любую перестановку игроков с равной вероятностью
Упомянуть, что для более простых условий есть тривиальные решения:
если разрешена ничья, то можно в случае ничьи продолжать кидать кубики, матожидание количества бросков будет константа
если можно брать разные кубики, то можно взять кубики с n, n-1, …, 1 гранями, и их результат будет задавать произвольную перестановку с равной вероятностью
В комментариях уже написали, что для двух игроков есть тривиальное решение (1,4) и (2,3) Для трех игроков уже надо искать брутфорсом, перебирая все варианты, простой скрипт на питоне выдает несколько решений, например, (0, 4, 8, 11, 13, 15) (1, 5, 6, 10, 12, 17) (2, 3, 7, 9, 14, 16).
Проверка, что кубики удовлетворяют условию задачи, делается за O(d^n), но можно применить оптимизацию, похожую на merge sort, ускоряющую ее до O(dn) (очень похоже на те самые всеми нелюбимые leetcode-задачи!).
При этом количество вариантов размещения чисел на кубиках растет экспоненциально, поэтому для трех достаточно скрипта на питоне, для четырех надо писать умные оптимизации, а для пяти чуваки решали задачу 15 лет, и до сих пор не знают, оптимально ли найденное решение.
Создан новый тип игральных костей, которые гарантируют отсутствие ничьей при определении победителя