Версия этой игры на уменьшенном поле не только менее утомительна по сравнению с классической, но и примечательна тем, что ее можно полностью «решить». Размер графа состояний здесь невелик — около 
вершин. Обладая этой картой состояний, построить идеальную стратегию не составляет труда.
Однако, что произойдет, если игра станет «нечестной»? Опираясь на нашу оптимальную стратегию, мы создали вредоносный вариант поля, нацеленный на её разрушение. Спойлер: такая конфигурация «съедает» игрока за 23 хода, тогда как на классическом поле он в среднем продержался бы 367. В конце статьи у вас будет возможность испытать свои силы в противостоянии со «Злой 2048».
Математика расчетов (технические детали)
Разберемся, почему граф столь компактен. Чтобы получить плитку 
, необходимо присутствие на поле всех младших степеней двойки, поэтому на 9 клетках физически невозможно набрать значения свыше 1024. Это ограничивает число состояний порядком 
, что вполне приемлемо для вычислений.
Для каждого состояния мы вычисляем математическое ожидание оставшихся ходов при условии идеальной игры. Это решается методом динамического программирования: перебираем четыре возможных направления и для каждого суммируем матожидания последующих состояний. Проблема порядка обхода вершин решается алгоритмом, аналогичным 1-2-BFS: мы сохраняем порядок посещения в массив, а затем вычисляем значения в обратном порядке.
Теперь наш алгоритм прост: на каждом шаге он анализирует четыре варианта и выбирает тот, что дает максимальное ожидаемое количество ходов. «Злое поле» действует зеркально, подбрасывая именно ту плитку, которая минимизирует результат игрока.
Анализ оптимального алгоритма
На графике видны отчетливые пики. Первый, наиболее выраженный — это проигрышные партии, где не удалось собрать 512. Следующие пики соответствуют неудачам при получении более высоких номиналов. Финальный пик — сложности с набором 1024, для которого нужно, чтобы при заполнении поля выпала «четверка», а не «двойка», что случается лишь в 10% случаев.
Преимущество оптимального алгоритма очевидно. Использование логарифмической шкалы может визуально искажать площадь под графиками, но синяя кривая (оптимальный алгоритм) значительно превосходит остальные по устойчивости.
Пример максимально удачного прохождения за 100 000 попыток:
Встреча со «Злым полем»
«Злое поле» — это детерминированная система, направленная на минимизацию наших успехов. Поскольку его поведение предсказуемо, алгоритмы (как оптимальный, так и основанный на приоритетах направлений) вступают в жесткие рамки предсказуемости. Количество достижимых состояний здесь резко сокращается до 
.
Поведение алгоритмов при таком противостоянии:
Сводный график эффективности:
Результаты говорят сами за себя: даже самый «умный» алгоритм в условиях «злого» поля проигрывает быстрее, чем случайный игрок на обычном поле.
Процесс игры оптимального алгоритма против «Злого поля» (видео)
Напоследок предлагаю вам бросить вызов «Злому полю» самостоятельно: https://ilia-ili-ilya.github.io/angry-2048/
