Анализ 2048 3 на 3

Вариант этой игры на маленьком поле лучше классического не только тем, что не такой бесконечно долгий, но и возможностью полностью «решить» её. Граф состояний не очень большой, примерно вершин. А зная граф состояний, легко построить оптимальную стратегию игры.

Но что, если сама игра не совсем честная? По нашей оптимальной стратегии мы построим «злой» вариант поля, который будет её уничтожать. Небольшой спойлер, она проиграет за 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/