Вариант этой игры на маленьком поле лучше классического не только тем, что не такой бесконечно долгий, но и возможностью полностью «решить» её. Граф состояний не очень большой, примерно 
вершин. А зная граф состояний, легко построить оптимальную стратегию игры.
Но что, если сама игра не совсем честная? По нашей оптимальной стратегии мы построим «злой» вариант поля, который будет её уничтожать. Небольшой спойлер, она проиграет за 23 хода, притом что на классическом поле в среднем держалась 367. И напоследок вы сможете сами попробовать свои силы против злого 2048.
Как же все это считать? (самая скучная часть)
Для начала поймем, почему вообще граф такой маленький. Поскольку для появления квадратика
нужно, чтобы в какой‑то момент все младшие степени оказались на поле одновременно, на 9 клетках не может получиться чисел больше 1024. А это значит, что число состояний можно оценить 
, что уже очень неплохо.
По сути, для каждого состояния мы хотим посчитать матожидание числа оставшихся ходов при условии, что мы будем играть дальше оптимально. Это делается простой динамикой — для каждой вершины перебираем 4 варианта возможных действий и для каждого считаем матожидание по уже посчитанным значениям. Единственный вопрос, как понять, в каком порядке обходить вершины? Ведь может так получиться, что для кого‑то из детей мы еще не знаем ответ. Но тут нам поможет обычный 1-2-bfs. Сохраняем порядок обхода вершин в массив, а потом идем по нему в обратном порядке и насчитываем динамику.
Теперь наш оптимальный алгоритм становится очень простым — на каждом ходу перебираем 4 возможных действия и выбираем то, у которого наибольшее матожидание. «Злое поле» тоже становится довольно естественным объектом, каждый раз появляется именно тот квадратик, с которым матожидание наименьшее.
Оптимальный алгоритм
На этом графике сразу бросается в глаза несколько пиков. Первый, самый высокий — это игры, когда не удавалось получить плитку 512, второй, третий и четвертый это проигрыши без 512+256, 512+256+128 и 512+256+128+64. Ну и наконец последний пик — это неудачи в получении квадратика 1024, для его достижения необходимо, чтобы в момент, когда на поле уже все степени двойки от 4 до 512, выпала именно 4, а не 2. Вероятность этого события всего 10%.
Тут видно, насколько оптимальный алгоритм лучше остальных. У распределений двух других алгоритмов тоже несколько характерных пиков, возникают они по тем же причинам. Может показаться, что график сломан, ведь площадь под каждым из распределений должна быть одинаковой, но это из‑за логарифмической шкалы, в реальности синий гораздо более широкий.
А это лучшая из 100 000 попыток оптимального алгоритма
Злое поле
Как мы уже решили выше, злое поле просто подкидывает нам плитку, минимизируя матожидание. Легко заметить, что оно детерминированное, поэтому и оптимальный алгоритм, и алгоритм с приоритетами (вниз‑вправо‑влево‑вверх) каждый раз будут делать одно и тоже. Допустимых состояний на злом поле тоже существенно меньше, всего 
.
Так на нем ведут себя наши алгоритмы:
Для сравнения всё на одном графике
Тут разница налицо, оптимальный алгоритм на злом поле проигрывает рандому на обычном.
Как оптимальный алгоритм играет на злом поле (видео)
Ну и, наконец, тут вы можете испытать Злое поле на себе https://ilia‑ili‑ilya.github.io/angry-2048/
Комментарии (9)
wataru
14.07.2026 14:34Только сейчас заметил, у вас rand-angry иногда даже лучше best-angry. Какое же оно тогда best? Что-то у вас явно не так, раз есть стратегия набирающая больше очков оптимальной.
Потому что, как я выше писал, в случае злодея надо оценивать не матожидание а тупо финальный счет. Игрок выбирает ход с максимальной оценкой, злыдень - с минимальной.
Если по дереву ходов где-то внизу расходятся рядом есть очень плохой путь и очень хороший, то игрок-то этот очень плохой никогда не выберет. Но при счите матожидания, этот плохой путь портит оценку хода в начале и ваша best стратегия выбирает средний вариант, потому что рядом с ним не было варианта сильно ошибиться.
А в случае случайных клеток, надо считать матожидание только по выбору новой клетки и никак не по движению. Игрок выбирает одно из 4 направлений минимизируя оценку. Матожидание только по случайной величине делается, ход игрока - не случаен, вы его вычисляете.
ilia-ili-ilya Автор
14.07.2026 14:34Тут никакой ошибки нет, просто оптимальный алгоритм на обычном поле действительно не будет оптимальным на "злом". На нем оптимальный алгоритм это просто самый длинный путь в дереве обхода.
А в случае случайных клеток, надо считать матожидание только по выбору новой клетки и никак не по движению. Игрок выбирает одно из 4 направлений минимизируя оценку. Матожидание только по случайной величине делается, ход игрока - не случаен, вы его вычисляете.Да, я так и делаю
wataru
14.07.2026 14:34Тут никакой ошибки нет, просто оптимальный алгоритм на обычном поле действительно не будет оптимальным на "злом".
В смысле. Оптимальный на злом поле должен брать в расчет злое поле. Но в принципе, я понял. На этом стоит заострить внимание в статье, что алгоритм считает лучшую стратегию в среднем, но играет против худшего случая.
wataru
Ведь каждый раз после хода игрока в случайной (или худшей) клетке появляется 2 или 4. А значит общая сумма очков на поле увеличится. Поэтому все поля топологически упорядочены по сумме очков. Тут нет циклов. Поэтому тут вообще работает динамика. Если бы были циклы, то пришлось бы решать систему линейных уравнений для поиска матожидания.
Простой способ не думать о порядке, это реализовать динамику сверху вниз, через рекурсию от начального состояния. Это просто пустое поле.
Не совсем понял, как вы тут применяете 1-2-bfs. Можно по-подробнее? Предполагаю, что это у вас топологическая сортировка снизу-вверх. Так тоже можно. Но проще же отсортировать все тупо по сумме очков. Можно даже подсчетом за линию.
Еще, если рассматривать "злобную" клетку, то у вас получается игра двух игроков - один сдвигает поле, другой кидает в пустую клетку 2 или 4. Первый максимизирует сумму, второй минимизирует. Тут уже можно рассматривать не матожидание, а минимакс: какое максимальное количество очков может себе гарантировать первый игрок.
Еще вопрос, когда вы считаете, что игра остановилась?
Проводили ли вы какую-то дедупликацию состояний, вроде поворотов/отражений? Казалось, бы если гравитационный ход заменить на поворот и всегда падение вниз, то все состояния будут сильно более похожи: всего 4^3 вариантов какие клетки вообще могут быть заполнены, в каждом столбе количество очков должно различатся у соседних клеток.
ilia-ili-ilya Автор
Да, про bfs не совсем точно написал, он нам нужен скорее не для порядка обхода, а чтобы понять какие вершины вообще достижимы, запускать динамику вообще на всех слишком долго. Дедуплицировать состояния действительно можно, выигрыш где-то в 5 раз должен быть (потому что 4 поворота + 2 отражения, но какие-то позиции сами в себя переходят), но потом не очень удобно пользоваться таким предподсчетом
wataru
И зачем там 1-2-bfs а не просто bfs?
Если запускать динамику рекурсивно, она сама только достижимые и обойдет.
ilia-ili-ilya Автор
1-2-bfs нужен, потому что у нас есть ребра с весами 1 и 2 (когда добавляется плитка 2 и когда добавляется плитка 4). Рекурсивно запускать динамику тоже решение, вполне можно и так
wataru
Если вы его используете для поиска достижимых вершин, веса ребер вам вообще безразличны.
Видимо, вы его используете для подсчета суммарных очков в поле и получения их в порядке возрастания, т.е. это не стандартная топологическая сортировка через bfs снизу-вверх, а сортировка вершин по расстоянию от начала через обход сверзу-вниз, которая гарантирует топологический порядок. Так?
ilia-ili-ilya Автор
Всё так и есть, после bfs-а мы получаем отсортированный по расстоянию список достижимых вершин, а потом запускаем на нем динамику