Математики изобрели игральные кости, с которыми невозможна ничья
Самый очевидный способ определить, кто ходит первым в настольных играх — бросить кости. Зачастую выпадает ничья, и приходится итерацию повторять, порой неоднократно. Группа математиков и специалистов по компьютерным наукам сочла эту особенность игральных костей серьезным недостатком — и взялась его устранить.
Все началось в 2012 году, когда Эрик Харшбаргер из Обернского университета за ужином с приятелем заговорил об идее так называемых «костей первого хода» — таких, что обеспечивали бы всем равные шансы и гарантировали при этом невозможность ничьей.
Вскоре он вместе с математиком Робертом Фордом из Колледжа Далтон-Стейт разработал набор из четырех двенадцатигранных костей, позволяющий двум, трем или четырем участникам бросать по одному додекаэдру и каждый раз получать статистически честный результат — с однозначной победой.
Сразу после этого возникла идея такого набора для пяти игроков. «Никакой практической пользы в этом нет, но с точки зрения математики это интересная задача», — признается Харшбаргер.
С тех пор он стал своего рода застрельщиком этой проблемы — запустил веб-сайт, на котором фиксировал все новые результаты, а около двадцати специалистов из разных стран то присоединялись к работе, то бросали ее.
Теоретический набор из пяти костей нашли довольно быстро — но с ними всегда что-то было не так: у некоторых вариантов число граней доходило до сотен, что делало их изготовление невозможным; кроме того, решения с разным количеством граней не только выглядели менее изящными, но и наверняка вызывали бы у людей подозрения в нечестности — даже если это было не так. «Но это хотя бы сдвинуло дело с мертвой точки», — говорит исследователь.
Помог программист
Со временем появлялись все более удачные варианты — например, набор из 180-гранных костей, предложенный самим Харшбаргером, и 120-гранные кости от австралийского исследователя.
Прорыв произошел, когда к проекту подключился инженер-программист Пол Мейер. Он совместил поиск математических закономерностей в предыдущих наработках с полным компьютерным перебором — и получил рабочий дизайн: пять костей с 60 гранями каждая, которые полностью удовлетворяют условиям задачи и, что важнее, могут быть изготовлены и использованы в реальности.
«Они довольно округлые и долго останавливаются после броска, но они действительно работают», — подчеркивает Харшбаргер.
«Я много раз бросал кости, чтобы решить, кто ходит первым в настолках, поэтому идея меня зацепила. Но когда я увидел саму математическую задачу, то подумал: "Это же просто задача на компьютерный перебор, наверняка можно написать алгоритм". Я и не ожидал, что действительно решу ее», — рассказывает Мейер.
Пространство возможных вариантов было колоссальным — по словам Харшбаргера, пять костей дают больше сочетаний, чем насчитывается атомов во Вселенной. Однако сходство и симметрия в ранее найденных решениях позволили Мейеру сузить область поиска. При этом его перебор не был исчерпывающим — вполне вероятно, что существуют еще меньшие кости, отвечающие всем условиям.
Что дальше
В продолжении поиска еще более оптимизированного варианта, а также в решении задачи следующего уровня сложности — с шестью костями (что раздувает пространство вариантов вообще до невообразимых масштабов) могут помочь квантовые компьютеры или искусственный интеллект, подытожил Харшбаргер.
