Решена математическая задача, над которой бились много лет
Во время ужина на игровом фестивале в 2012 году разработчик настольных игр спросил Эрика Харшбаргера, нельзя ли придумать такие кости, которые позволяли бы определять первого игрока без вероятности ничьей. Идея была простой: быстро определить, кто ходит первым, и перейти к игре.
«Цель в том, чтобы сэкономить всем несколько драгоценных секунд и как можно скорее начать играть», — рассказал Харшбаргер ведущей программы As It Happens Нил Кёксал. Харшбаргер, математик и старший преподаватель Обернского университета в Оберне, штат Алабама, говорит, что такая задача пришлась ему как раз по душе. «Это был вопрос без очевидного ответа, а математики обычно очень любят за такие вопросы хвататься».
Харшбаргер вообразил себе такой теоретический набор костей, в котором каждый игрок мог бы бросить по одной кости, все имели бы одинаковые шансы на победу и при этом никакие два игрока не могли бы получить одинаковый результат. Но найти кости, которые действительно работали бы в реальном мире, оказалось гораздо сложнее.
Теперь, почти 15 лет спустя, Харшбаргер и его коллеги наконец создали такой набор: Go First Dice для пяти игроков. Они позволяют честно определить, кто первым ходит в настольной игре, причём победитель гарантирован уже после одного броска.
Упрямая задача
За эти годы Харшбаргер фактически стал хранителем этой задачи. Он вёл сайт, где фиксировал новые результаты, а к проекту в разное время присоединялись и уходили из него около 20 специалистов по информатике и математиков со всего мира.
Довольно быстро Харшбаргер и его команда нашли решение с набором из четырёх 12-гранных костей. Два, три или четыре игрока могли бросить по одному додекаэдру и получить статистически честный результат, причём каждый раз обязательно находился победитель. «Для двух человек мы решили задачу в мгновение ока, для трёх — за день‑два, а кости для четырёх человек придумывали две‑три недели, ну, может быть, месяц», — рассказал Харшбаргер. Но вариант для пяти игроков оказался гораздо более крепким орешком.
По словам Харшбаргера, он и его коллеги всегда знали, что с математической точки зрения такие кости существуют. Оставалось понять, можно ли воплотить математическое решение в физической форме игральной кости, то есть сделать предмет, который реально можно изготовить и бросать. «Я знал, что существует безумное решение вроде 1440 граней у каждой кости, — сказал он. — Но такое невозможно изготовить».
Поэтому исследователи начали разрабатывать разные теории и пытаться уменьшить число граней, постепенно «обтёсывая» задачу. В процессе к группе присоединился исследователь из Австралии и нашёл более практичное решение: набор из пяти 120-гранных костей. Открытие привлекло внимание прессы, и примерно через полгода к работе присоединился ещё один исследователь, на этот раз из Канады.
Прорыв из Канады
Канадский инженер‑программист Пол Мейер связался с Харшбаргером и попросил прислать некоторые старые результаты работ. Через три месяца Мейер отправил Харшбаргеру письмо с отличной новостью: он нашёл решение с пятью 60-гранными костями. За время работы над проектом Харшбаргер получал множество писем от людей, утверждавших, что решили задачу, поэтому первым делом он всегда проверял предложенное решение. На этот раз всё действительно работало. Харшбаргер написал Мейеру: «Вы понимаете, что мы искали это очень давно?»
Мейер подошёл к задаче как к вычислительной проблеме: использовал математические закономерности из предыдущих решений и компьютерный перебор. Пространство поиска было колоссальным: возможных конструкций существовало больше, чем атомов во Вселенной. Но Мейеру удалось достаточно сильно сузить его и найти решение.
Кости размером примерно с мяч для гольфа уже можно купить, хотя некоторые исследователи сомневаются, смогут ли они на практике полностью соответствовать математической модели. Харшбаргер, однако, уверен в математике. Кости спроектированы так, чтобы быть абсолютно честными, а любые отклонения, способные повлиять на результат, могут возникнуть только из‑за особенностей изготовления, а не из‑за самой математической конструкции.
В итоге у каждого игрока своя 60-гранная кость, причём числа на пяти костях не повторяются, поэтому ничья невозможна. Эти числа специально распределены между костями так, чтобы ни одна из них не имела преимущества: при броске любых двух каждая выигрывает с вероятностью 50%, а при игре втроём, вчетвером или впятером все возможные порядки результатов остаются равновероятными. Иными словами, кости разные, но математически «честные» относительно друг друга. Кроме того, любое количество человек, от двух до четырёх, могут взять по одной случайной кости из набора, и они будут работать точно так же, обеспечивая равные шансы и не приводя к ничьей / прим. перев.
Следующие нерешённые вопросы
После этого Мейер вошёл в исследовательскую группу, и работа в ней продолжается. По словам Харшбаргера, они по‑прежнему пытаются понять, можно ли сделать набор для пяти игроков с меньшим числом граней. Известно, что теоретический минимум составляет 30 граней. Кроме того, исследователи хотят выяснить, можно ли распространить эту идею на шесть игроков.
Нынешних математических и вычислительных методов для решения этих задач пока недостаточно, говорит Харшбаргер, но за эти годы команда научилась ждать неожиданностей. «Конечно, вполне может появиться кто‑то ещё с совершенно новой теорией и сказать: „А я сделал вот так“, — говорит Харшбаргер. — По сути, именно это и произошло с Полом. Он возник буквально из ниоткуда».
Для Харшбаргера именно эта непредсказуемость и сделала задачу настолько увлекательной. «С математической точки зрения она казалась очень красивой и интригующей, хотя мы с первого дня понимали, что сам вопрос довольно дурацкий. Но на него не было очевидного ответа, а за такие вопросы математик часто хватается и потом упрямо занимается ими годами».
Комментарии (26)
InsiderCrush
11.09.2026 12:32Я туплю? или можно взять например пять 10-тигранников например, каждому по очереди присваиваем числа по очереди от 1 до 25 (первый кубик 1, второй 2..) и потом от 50 до 26. Вот вам и суммы одинаковые на кубиках и вероятности. На что 15 лет люди потратили? :D
CitizenOfDreams
11.09.2026 12:32На что 15 лет люди потратили?
Хоть математику немного подучили, всяко полезнее, чем просто кидать 20-гранники на инициативу.
losse_narmo
11.09.2026 12:32Если взять 10-гранные кубики и 3 игроков, то кубики "нечестные". Всего может быть 1000 вариантов бросков (10*10*10), а 1000 на 3 не делится. Значит кто-то выигрывать будет чаще других.
Они искали кубики так, чтобы 2/3/4/5 игроков брали любые из этих кубиков и шансы были равны
TimID
11.09.2026 12:32При чем здес "тысяча вариантов на троих"? Важно, чтобы значения в бесконечном количестве бросков выпадали так, чтобы правило "больше-меньше" работало взаимно равновероятно. То есть кости однозначно не только выбирали лучшего, но ещё и расставляли всех в рейтинге.
wataru
11.09.2026 12:32чтобы правило "больше-меньше" работало взаимно равновероятно
Оно не может работать равновероятно, потому что элементарных исходов 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 выигрывает чаще других.
wataru
11.09.2026 12:32Надо же не сумму на костях делать одинаковой, а вероятности выигрыша.
Ваша система, кстати, гарантирует что каждая пара костей честная - одна выиграет у другой с вероятностью 1/2, ведь все исходы можно сгруппировать в парочки. Пусть x выкинул первый игрок, y -второй: (x,y) <-> (51-x, 51-y). В каждой паре исходов выигрывает то один то другой игрок.
Но вот это не гарантирует общую честность. Если играет 3 или более игроков, то первая кость выигрывает заметно чаще.
gr-pr-moi-do
11.09.2026 12:32для до 6 игроков достаточно одного обычного кубика: говоришь ты "первый/один", бросаешь кубик и отсчитываешь выпавшее число
avshkol
11.09.2026 12:326 человек садятся в круг и договариваются ходить по часовой стрелке.
Первым номером назначают самого младшего, остальные получают номера по часовой стрелке по возрастанию.
Младший бросает кубик, и получаем номер того, с кого начинается ход.
LeToan
11.09.2026 12:32Для Харшбаргера это математическая задача. Уверен, что если бы он играл сам, то вовсе не против был бы бросать несколько раз. Его цитата о выигрыше нескольких секунд этот факт подтверждает.
avshkol
11.09.2026 12:32Не очень понял, где в моем варианте бросают несколько раз? Только один раз.
Да, я занимаюсь на досуге разработкой [не издаваемых] настолок, и, как понимаю, здесь нужно было реализовать вариант, чтобы в каждом раунде порядок ходов формировался случайно.
Но это грозит "распадом связности" - так, в случае ходов по кругу или по некому правилу, определяемому в процессе игры, это становится еще одним "оптимизируемым фактором", т.е. тем, что можно учитывать в дальнейших прогнозах. В случае, если каждый раунд ходы определяются случайно, случайности становится слишком много, ценность стратегий, прогнозов девальвируется, и это ухудшает удовольствие от игры.
LeToan
11.09.2026 12:32Вы придумываете какие-то обходные способы решить проблему - всё это Харшбаргера не интересует. Он таких способов и сам может придумать пачку. Для него это исключительно математическая задача с заданными условиями. Если же бы он был игрок, то его бы не затруднило потратить несколько лишних секунд и для повторных бросков ради определения чего надо.
Alexandroppolus
11.09.2026 12:32при игре втроём, вчетвером или впятером все возможные порядки результатов остаются равновероятными
То есть за один бросок определяется не только победитель, но так же второе, третье и четвертое места?
wataru
11.09.2026 12:32Все числа уникальные, так что можно и порядок получать. Равновероятность всех перестановок как раз и делает задачу сложной.
srgis
11.09.2026 12:32но ведь если числа на кубиках не повторяются, значит только на одном из них есть например цифра 1 (самая меньшая из использованных) - разве это не даст преимущество его владельцу?
Sayonji
11.09.2026 12:32Допустим, кубиков только два и они двугранные. На одном 1, 4, а на втором 2, 3. Преимущества нет.
srgis
11.09.2026 12:32так ведь речь шла именно о кубиках для 5 игроков.
randomsimplenumber
11.09.2026 12:32В том и задача, сколько граней должно быть на
кубикахкостях и какие числа там нарисованы. Для 2 2-гранныхкубиковмонет все просто.
pavelpedko
11.09.2026 12:32Решение чрезмерное для заявленной задачи. Особенно если допустимо бросить несколько именованых (разноцветных) кубиков одновременно - это ничем математически не отличается от нескольких последовательных бросков.
Для определения первого из пяти игроков достаточно бросить пятигранный кубик, для первого из четырёх - 4-хгранный и так далее. По желанию, все четыре кубика можно бросить одновременно. Такие броски определят и первого, и всю последовательность инициативы.
Но они переформулировали математическую задачу, искали в ограниченной области решений, и это тоже интересно как упражнение.
randomsimplenumber
11.09.2026 12:32Для определения первого из пяти игроков достаточно бросить пятигранный кубик, для первого из четырёх - 4-хгранный и так далее
Интересует конструкция 3 гранного кубика.
zhka
11.09.2026 12:32это обычный 6-ти гранный кубик на котором числа 1,2,3 повторяются по 2 раза.
wataru
11.09.2026 12:32Тогда уж проще просто назначить числам от 1 до 6 различные перестановки трех последних игроков и одним броском шестигранного кубика определить их порядок.
А еще можно взять кубик с n! сторон и одним броском найти порядок всех n игроков.
Но задача не об этом. Это теоретическая задача о существовании костей, любое подмножество которых честное. И решают ее не потому что не знают, как еще определить порядок игроков в ДнД, а потому что это офигенно.
lightln2
11.09.2026 12:32Я понимаю, что это перевод, но все же на Хабре хочется технических подробностей. Собсвенно, тут в комментариях люди пытаются угадать, что же за задача решается. В статье нет ни формулировки, ни решения.
Вместо статьи о том, что математики делают математику, один бородатый, а второй из Канады, хочется видеть что-то вроде такой статьи:
Сформулировать условие - 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 лет, и до сих пор не знают, оптимально ли найденное решение.
MountainGoat
Тем временем нормальные люди вытягивают нумерованные жетоны.