Pull to refresh

Математика и игра 2048

Reading time 7 min
Views 72K
сто тридцать одна тысяча
Впервые игру 2048 представили на Хабрахабр здесь. Не прошло и пяти дней, как раскрыли тайну простой стратегии ее прохождения. Она действительно проста — нужно строить змейку из тайлов (как на картинке).

Однако понятная цель не всегда означает её легкое достижение. Мы с Mrrl по очереди делились своими успехами: слепили блоки 8, 16, 32 и 65 тыс. Теперь же мне удалось то, что я и сам не ожидал — собрать максимально возможный тайл в игре — 131 072 или 217, скопив свыше 2 млн очков.

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

Чтобы разобраться понадобится немного математики…

Максимально возможный тайл


Глядя на картинку со змейкой, ведущей к созданию блока 217, очевидно, что большего тайла при помощи именно этой стратегии собрать не удастся. Однако верен ли вывод, что 131 072 действительно максимум? Интуиция подсказываем нам ответ «да», но хотелось бы более убедительных аргументов. И эта часть исследования оказалась для меня наиболее сложной. Несколько подходов завели в тупик, пока, наконец, я не пришел к следующей конструкции.

Основная идея – абстрагироваться от того, как расположены тайлы на игровом поле, сосредоточив внимание только на их значениях. С этой точки зрения состояние игры можно описать упорядоченным по возрастанию набором 16 чисел, представленных в данный момент на экране (пустой клетке соответствует ноль).

В случае как на картинке состоянием будет набор (4, 4, 8, 16, …, 65536). А в самом начале игры оно может быть, например, вектором (0, 0, …, 0, 2, 2). Каждый ход (как человека, так и машины) приводит к новому состоянию, которое, однако, не может быть произвольным. Так, правила игры не позволяют перескочить разом с (0, …, 0, 2, 2, 8) до (0, …, 0, 4, 16).

Опишем все возможные переходы от одного состояния к другому:
- в ход человека – либо ничего не меняется, либо одна или несколько пар одинаковых чисел заменяются на сумму элементов в паре, затем добавляется необходимое количество нулей и вектор упорядочивается;
- в ход машины – либо в набор добавляется (так, чтобы не нарушить порядок) одна двойка или одна четвёрка, а один ноль убирается, либо (если нулей в состоянии нет) объявляется проигрыш игрока.
Исходным состоянием (то есть состоянием на момент начала головоломки) может быть (0, …, 0, 2, 2), (0, …, 0, 2, 4) или (0, …, 0, 4, 4). Человек и машина ходят по очереди, игрок начинает первым.

Эти правила можно рассматривать как аксиомы построенной нами модели игры 2048. Как и положено – она проще объекта моделирования, но обладает важными свойствами:
- если в исходной головоломке можно построить тайл, например, 217, то и в новой тоже можно;
- и наоборот, если в упрощенной игре нельзя перейти к состоянию с числом 218, то и в оригинальной создание такого блока невозможно.

Таким образом, для ответа на вопрос «точно ли 131 072 является максимально возможным тайлом?», остается доказать, что перейти в модели к состоянию с числом 218 никогда не удастся.

Доказательство: предположим противное и рассмотрим цепь состояний от одного из исходных до того, когда впервые появилось число 218. Исходя из аксиом модели, последний вектор мог появиться только после хода человека в ситуации вида (…, 217, 217).

Рассмотрим первое такое состояние, встречающееся нам в цепи. Ему предшествовало (опять же согласно принятым аксиомам) либо (…, 216, 216, 217), либо (…, 216, 216, 216, 216), причем очередь хода за человеком.

Это в свою очередь означает, что ранее игрок должен был оказаться в одной из ситуаций: (…, 215, 215, 216, 217), (…, 215, 215, 215, 215, 217), (…, 215, 215, 216, 216, 216), (…, 215, 215, 215, 215, 216, 216), (…, 215, 215, 215, 215, 215, 215, 216) или (…, 215, 215, 215, 215, 215, 215, 215, 215).

Замечание: некоторые состояния и переходы возможны только в рассматриваемой нами модели, им нет аналогов в игре 2048, что не влияет на ход доказательства.

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

В результате, не более чем через 15 шагов все 16 компонент окажутся явно заданы. Тогда мы придем к утверждению, что в цепи должно быть состояние вида (2k, …), где k ≥ 3, причем ходит человек.

Однако игрок не мог оказаться в такой ситуации, так как после действия машины наименьшее из представленных в векторе чисел может быть только 0, 2 или 4. Пришли к противоречию, которое опровергает наше исходное предположение от противного, тем самым доказывая требуемое.

В итоге, 217 действительно является максимально возможным тайлом в игре 2048. Это означает также, что проходя головоломку можно сделать не более чем какое-то фиксированное количество ходов, набрав при этом ограниченное число очков. Интересно, сколько же именно баллов и действий в нашем распоряжении?

Максимально возможное число очков


Подсчет очков мне дался намного проще. Для начала наметим лучшее к чему может стремиться игрок в 2048. Заветная цель рекордсмена по очкам (и по количеству ходов, кстати, тоже) это ситуация, описываемая вектором (2, 8, 16, 32, ..., 131 072) или (4, 8, 16, 32, ..., 131 072). В этом случае игра заканчивается, в то время как любое другое состояние «доминируется» указанными, то есть его точно можно улучшить, выручив при этом дополнительные баллы (совершив дополнительные действия).

Отметим также, что на пути к желанному финалу, машина может выдавать большее или меньшее количество четвёрок. Чем чаще игрок получает такие «подарки», тем хуже будет его результат по очкам. Поэтому давайте считать, что машина во всех (за исключением оговоренных далее) случаях выдаёт двойку. Чтобы дойти до конца необходимо получить всего 15 четвёрок — для сбора блока 131 072, расположенного рядом с ним тайла 65 536, и так далее до 8.

Итак, запомним сделанное предположение и рассмотрим функцию f (n), значение которой определим как наименьшее возможное число очков, заработанное к моменту первого появления на поле тайла 2n. Почему именно наименьшее? Дело в том, что собрав впервые, например, блок 4, мы можем гарантировать наличие четырёх вырученных за это очков, но их может быть больше (если вдруг собралось параллельно несколько тайлов 4).

Получаем f (2) = 4. Далее:
f (3) = 16 (по 4 балла мы получим за каждый из двух необходимых блоков 4, затем ещё 8 — за их объединение в восьмёрку),
f (4) = 48 (= 16 + 16 + 16),
f (5) = 128 (= 48 + 48 + 32) и т. д.

Рекуррентное соотношение таково: f (n) = 2f (n — 1) + 2n для всех натуральных n, 3 ≤ n ≤ 16. Один из способов его разрешить — рассмотреть равенства f (n) = 2(2f (n — 2) + 2n — 1) + 2n = 4f (n — 2) + 2*2n, f (n) = 4(2f (n — 3) + 2n — 2) + 2*2n = 23f (n — 3) + 3*2n, ..., f (n) = 2n — 2f (2) + (n — 2)*2n. С учетом f (2) = 4, получаем f (n) = 2n(n — 1), что верно, напомним, для 3 ≤ n ≤ 16.

Собирая тайл 217 мы получим на 4 очка меньше, чем предсказывает выведенная формула, так как вынуждены будем использовать одну подаренную нам машиной четвёрку. То есть f (17) = 217*16 — 4 или 2 097 148.

Осталось только понять, что после создания максимального блока, нам вновь предстоит «впервые» собрать тайл 216, выручив за это f (16) — 4 очков (штраф опять же за использование дармовой четвёрки), затем 215, получив сопутствующие f (15) — 4 баллов, и так далее до 23 и f (3) — 4 поинтов в копилку.

Вычислив сумму f (17) + f (16) — 4 + f (15) — 4 +… + f (3) — 4, получим 3 932 100, что является максимально возможным количеством очков в игре 2048.

Небольшое замечание: по определению f (n) — это наименьшее возможное число очков, заработанное к моменту первого появления на поле тайла 2n. Однако в финале игры число заработанных баллов в точности равно сумме значений функций для n от 3 до 17 (за вычетом штрафа). Никаких излишков нет, так как они учтены в слагаемых, соответствующих более мелким блокам.

Максимально возможное количество ходов игрока


Задача про количество ходов казалась мне вначале самой сложной. Но рассуждения довольны просты: введем функцию g (n), в чём-то похожую на f. Её значение определим как минимальное число тайлов 2, необходимое для сбора блока 2n. В целях максимизации количества ходов мы также действуем в предположении, что машина каждый раз (за исключением 15-ти особо оговоренных случаев) выдаёт нам двойки.

Итак, g (2) = 2 (для сбора четвёрки нужно слить 2 двойки), g (3) = 4 (для сбора восьмёрки нужно слить две четвёрки, производство каждой из которых требует по 2 двойки), g (4) = 8 (= 4 + 4) и так далее. Простое рекуррентное соотношение g (n) = 2g (n — 1) даёт формулу g (n) = 2n — 1 для 3 ≤ n ≤ 16.

При создании блока 217 нам требуется на два тайла 2 меньше, чем указывает выражение выше, так как одну четвёрку нам дают сразу, собирать её не надо. Поэтому g (17) = 216 — 2 = 65 534. Точно также как и в случае с очками, для подсчёта общего числа двоек, задействованных на пути к одному из двух финальных состояний, следует сложить значения функции g (n) при n от 3 до 17 с учетом штрафов. Получим g (17) + g (16) — 2 +… + g (3) — 2, равное 131 038. Для полного порядка, к этому числу надо прибавить единицу, если мы пришли в финальное состояние (2, 8, 16, ..., 131 072).

Теперь вернемся к нашей задаче. Два тайла 2 нам даются с самого начала. Чтобы получить оставшиеся 131 036 (не считая последней в одном из финалов) необходимо совершить соответствующее количество действий (ведь каждый ход машина выдаёт нам ровно одну двойку). Плюс понадобится еще 15 четвёрок (также не считая последней в одном из финалов). И, наконец, еще одно действие приведёт к появлению последней двойки или четвёрки.

Итого, волей-неволей придётся сделать 131 036 + 15 + 1 = 131 052 нажатий на клавиши (или прикосновений к сенсорному экрану) — это и есть искомое максимальное количество ходов пользователя в игре 2048.

Анализ моих текущих достижений в игре 2048


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

Итак, следуя опробованным ранее рассуждениям, если бы всю игру мне выпадали только двойки и одна четвёрка, то в результате g (16) + g (15) +… + g (2) + 1 — 2 = 65 533 ходов я должен был набрать целых f (16) + f (15) + f (14) +… + f (2) = 1 835 012 очков. Однако, как видно, заработано всего 1 811 320. Не хватает 23 692, то есть машина выдала мне 5 923 четвёрки, лишив возможности добрать очки, но сэкономив соответствующее число ходов.

Выводы:
— к настоящему моменту я сделал порядка 60 тыс. правильных действий на пути к полной победе в игре 2048;
— до одного из двух неизбежных финалов осталось еще около 71 тыс. нажатий на клавиши (при идеальной игре и везении);
— общее количество полученных мной очков (после сбора максимального тайла и четырёхтысячного блока рядом с ним) составляет 2 117 800, то есть ~54% от максимально возможного. Больше половины! Даже с учетом невосполнимых потерь в размере почти 24 тыс. баллов из-за генератора случайных чисел.

Если вдруг добью игрушку до конца — выложу картинку в этот пост. Всем хорошего настроения!

UPD:
финальная позицияПоявившаяся сразу после снимка экрана фраза Game over кажется мне в этом случае не совсем уместной. Ведь на пути к одному из двух возможных финальных состояний победный блок 2048 пришлось собрать 127 раз. Всего сделано 119 322 правильных хода. Машина выкинула на поле 11 730 четверок (не считая последней в левом верхнем углу), что ускорило победу, но лишило 46 920 очков.
Tags:
Hubs:
+64
Comments 34
Comments Comments 34

Articles