Рекорд в головоломке Digit Party оказался математически недостижимым: почему профессора математики три года ошибались в собственной игре

В 2023 году математики Роберт Бригналл из Открытого университета Великобритании и Винсент Ваттер из Университета Флориды запустили бесплатную браузерную игру Digit Party. В ней игроки заполняют квадратное поле случайными числами и пытаются набрать как можно больше очков за счет их соседства. После каждого раунда программа показывает результат игрока в процентах от теоретически возможного максимума — наилучшего счета, который можно было бы получить при идеальном размещении тех же самых чисел.

Спустя три года создатели игры опубликовали признание: все это время алгоритм завышал теоретический максимум. Оценка мастерства игроков была неточной, поскольку разработчики использовали упрощенную формулу вместо точного математического расчета. Попытка исправить эту неточность привела к решению сложной задачи на стыке дискретной геометрии, комбинаторики и теории оптимизации.

Правила игры и подсчет очков

Игровое поле Digit Party состоит из 25 клеток — сетки размером пять на пять. В каждом раунде игроку поочередно выдается 25 цифр от 1 до 9. Порядок выдачи случаен, а информация ограничена: игрок видит только текущую цифру и одну следующую за ней. Каждую цифру необходимо сразу поставить в любую свободную клетку. Перемещать уже установленные цифры запрещено.

Очки начисляются за пары одинаковых цифр, оказавшихся в соседних клетках. Соседними считаются клетки, которые соприкасаются сторонами или углами. Таким образом, у клетки в центре поля есть восемь соседей, у клетки на краю — пять соседей, а у клетки в углу — три соседа. Всего на поле такого размера расположено 72 пары соседних ячеек.

Если две соседние клетки содержат одну и ту же цифру, игрок получает количество очков, равное значению этой цифры:

• Пара соседних единиц приносит одно очко.
• Пара соседних пятерок приносит пять очков.
• Пара соседних девяток приносит девять очков.

Цель игрока — сгруппировать одинаковые цифры в плотные блоки, отдавая приоритет крупным числам.

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

В чем заключалась ошибка

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

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

Границы одних групп неизбежно сдавливают или разделяют другие группы. Из-за нехватки места часть цифр теряет контакты. Сумма изолированных максимумов дает лишь верхнюю теоретическую оценку, которая на практике часто оказывается физически недостижимой.

Максимальное число связей для одной цифры

Чтобы построить корректный алгоритм, сначала потребовалось решить базовую задачу: сколько связей могут образовать одинаковые клетки определенного количества на бесконечной сетке? Это дискретный аналог классической изопериметрической задачи, которая в непрерывной геометрии определяет фигуру с максимальной площадью при заданном периметре.

В дискретном случае связь между клетками считается контактом. Число контактов зависит от того, какие направления считаются соседними:

1. Только горизонтальные и вертикальные связи (четыре соседа)

Эту задачу решили Фрэнк Харари и Хейко Харборт в 1976 году. По их формуле предельное количество связей вычисляется как удвоенное число клеток за вычетом удвоенного квадратного корня из этого числа, округленного вверх до целого.

Удвоенное число клеток показывает предел связей для бесконечной плоскости (каждое общее ребро принадлежит двум клеткам одновременно), а вычитаемое значение определяет неизбежную потерю связей на внешней границе фигуры. Наиболее выгодной формой при четырех направлениях связности является квадрат.

2. Связи по горизонтали, вертикали и диагоналям (восемь соседей)

В игре Digit Party учитываются и диагональные контакты. В этом случае предельный теоретический коэффициент увеличивается вдвое.

Николас Таличео и Джулиан Флерон выдвинули гипотезу, а математик Эндрю Винс в 2024 году строго доказал формулу для сетки с диагональными связями: максимальное число контактов для группы равно учетверенному количеству клеток минус поправка на внешнюю границу. Эта поправка рассчитывается как квадратный корень из числа клеток, умноженного на 28, за вычетом 12, с округлением результата вверх до ближайшего целого.

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

Для групп размером от 1 до 13 клеток максимальное число контактов в точности совпадает с округленным произведением размера группы на его натуральный логарифм. Согласно аналитической теории чисел, эта же математическая зависимость задает приближенное значение соответствующего по счету простого числа.

Однако на четырнадцати клетках связь нарушается: точная геометрическая формула дает ровно 36 контактов, тогда как произведение четырнадцати на его натуральный логарифм дает около 36,95 и округляется до 37. Это расхождение объясняется действием закона малых чисел: в диапазоне небольших величин разные математические закономерности нередко дают одинаковые результаты исключительно из-за малого объема доступных целых чисел.

Точный расчет для всего поля: целочисленное программирование

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

Общая сумма всех 25 выпавших цифр фиксирована. Чтобы перевести задачу в систему линейных уравнений, используются переменные и условия:

1. Основные переменные

Для каждой из 25 клеток поля и каждой из 9 возможных цифр вводится бинарная переменная-индикатор:

• Переменная равна единице, если в данной клетке стоит конкретная цифра.
• Переменная равна нулю во всех остальных случаях.

Всего для поля создается 225 основных бинарных переменных (произведение 25 клеток на 9 цифр).

2. Ограничения размещения

• В каждой отдельной клетке поля должна находиться ровно одна цифра: сумма индикаторов всех девяти цифр для этой ячейки строго равна единице.
• Каждая цифра должна быть использована ровно столько раз, сколько она выпала в партии: сумма индикаторов конкретной цифры по всем клеткам поля строго равна ее фактическому количеству.

3. Целевая функция и перевод в линейный вид

Очки начисляются, когда две соседние клетки содержат одинаковую цифру. Чтобы зафиксировать это событие математически, значения индикаторов двух соседних клеток перемножаются: результат равен единице только тогда, когда обе ячейки заняты одной и той же цифрой.

Суммарный счет игры представляет собой сумму номиналов цифр за все 72 пары соседних клеток поля, где цифры совпали.

Такой расчет содержит произведение переменных, то есть является нелинейным. Методы линейного программирования требуют строго линейных выражений. Чтобы убрать произведение, математики заменяют каждое умножение двух базовых индикаторов на одну вспомогательную переменную соседства.

Для 72 пар соседних ячеек и девяти возможных цифр создается 648 вспомогательных переменных (72 умножить на 9). Их связывают с базовыми индикаторами через два простых линейных правила:

1. Вспомогательная переменная не может быть больше индикатора первой клетки.
2. Вспомогательная переменная не может быть больше индикатора второй клетки.

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

Итоговая математическая модель состоит из 873 переменных и 1330 линейных ограничений. Специализированные программы оптимизации находят точный максимум для такой системы менее чем за 10 миллисекунд.

Анализ ошибок за три года

С помощью точного алгоритма авторы проверили все 1096 ежедневных партий за первые три года существования игры.

Выяснилось следующее:

• В 1041 партии (почти 95% случаев) упрощенный расчет дал правильный ответ. Пространственного конфликта между фигурами не возникло.
• В 55 партиях (около 5% случаев) игра показала завышенный максимум.
• Средняя ошибка среди неверных расчетов составила около двух с половиной очков.

Самое сильное расхождение зафиксировано в играх №88 и №813: ошибка составила шесть очков. В игре №88 выпал следующий набор цифр: пять троек; по четыре двойки, пятерки, шестерки, семерки и девятки; а также две двойки и две четверки.

Упрощенный расчет складывал максимальные возможности каждой отдельной группы независимо от других:

• тройки давали 24 очка (три очка умножить на восемь связей);
• четверки шестерок, семерок и девяток давали суммарно 162 очка;
• пары двоек и четверок приносили шесть очков.

В сумме это давало заявленный максимум в 192 очка.

Точный расчет на основе линейного программирования доказал, что оптимальные формы этих групп невозможно состыковать на сетке пять на пять. Максимальный физически достижимый результат составлял 186 очков. Игрокам предъявляли недостижимую цель.

Как обеспечить мгновенный расчет в браузере

Digit Party выполняется на стороне пользователя в веб-браузере. Игроки могут запускать неограниченное число случайных партий. Встраивать сложную программу оптимизации в браузерный код нецелесообразно: это перегрузило бы процессоры мобильных устройств и увеличило время загрузки страницы.

Прямое сохранение всех возможных исходов также невозможно. Полное число вариантов распределения 25 неразличимых клеток между девятью типами цифр составляет 13 884 156 комбинаций. База данных такого объема слишком велика для легкого веб-приложения.

Упрощение через теорию разбиений

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

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

Существует всего 1291 вариант разбиения числа 25 на группы количеством не более девяти слагаемых.

Авторы проверили каждое из 1291 разбиений с помощью математического анализа:

1. 891 разбиение (69%) является идеальным. Группы таких размеров всегда можно разместить на сетке пять на пять так, чтобы каждая группа получила свой максимальный контакт без компромиссов.
2. 400 разбиений (31%) являются неидеальными. Для них одновременное достижение локальных максимумов невозможно, и хотя бы одна группа цифр вынужденно теряет связи.

Применение принципа Парето

Для 400 неидеальных разбиений необходимо определить наименее затратный вариант потери связей.

Каждое допустимое заполнение сетки дает определенное число реально сохраненных связей. Разница между изолированным максимумом группы и ее реальным значением образует список потерь (вектор дефицита). В нем для каждого блока цифр записано, сколько именно контактов он потерял.

Одни способы размещения на сетке заведомо хуже других. Если один вариант размещения теряет не больше связей, чем второй вариант по всем группам, и при этом сохраняет строго больше связей хотя бы в одной группе, первый вариант всегда выгоднее независимо от выпавших цифр. Худшие варианты отбрасываются.

Оставшиеся варианты формируют множество Парето — список наилучших доступных компромиссов между потерями связей в разных группах.

Для каждого проблемного разбиения число вариантов в списке Парето невелико: от одного до пяти вариантов для большинства случаев. Максимальное число вариантов (14) зафиксировано только для одного редкого разбиения — на группы размером 7, 6, 4, 4 и 4.

Вся таблица оптимальных компромиссов для всех 400 неидеальных конфигураций занимает менее трех килобайт памяти.

Итоговый алгоритм работы игры

Благодаря предварительному расчету базы данных итоговый алгоритм в браузере работает по следующей цепочке:

1. Определение структуры: получив случайный набор из 25 цифр, программа подсчитывает число повторений каждой цифры и упорядочивает эти размеры по убыванию.
2. Проверка на идеальность: программа проверяет, входит ли полученная комбинация размеров в список 891 идеального случая. Если входит, теоретический максимум рассчитывается прямым умножением номинала каждой цифры на максимальное число связей для группы ее размера.
3. Оптимизация по Парето: если комбинация неидеальна, программа берет из таблицы готовый список вариантов дефицита. Для каждого варианта вычисляется итоговый штраф: наибольшие потери контактов программа целенаправленно сопоставляет с цифрами наименьшего достоинства (потерять связь в двойках выгоднее, чем в девятках). Выбирается вариант, дающий минимальный суммарный штраф.

Такой расчет на устройстве пользователя выполняется мгновенно и гарантирует абсолютную точность отображаемого рекорда.

Различие между предварительным расчетом и реальной игрой

Разработанный метод полностью решает задачу для идеальных условий, когда вся последовательность из 25 цифр известна заранее до первого хода.

Однако реальная партия в Digit Party протекает в условиях жесткого дефицита информации: игрок видит только следующий шаг и вынужден делать необратимые ходы. В теории вычислительных процессов качество алгоритмов в таких условиях оценивается через коэффициент эффективности — гарантированное соотношение между результатом в условиях неполных данных и абсолютным рекордом, рассчитанным задним числом.

Построение математически безупречной пошаговой стратегии для игры с частичной видимостью и определение точного предела результативности человека на сетке пять на пять остаются открытыми вопросами комбинаторной теории игр.

Источник: Math Horizons