Две игры на слияние, один вопрос: можно ли сыграть хоть в одну из них безупречно? Ответ проходит через угол доски, соперника, который так и не появляется, и число высотой в семнадцать показателей степени.
Написано и отредактировано на английском языке. Эта русская версия создана машинным переводом; там, где важна точность, авторитетным остаётся английский оригинал. Читать оригинал на английском →
Начнём с игры, которую знают все. 2048 — четыре направления, сетка 4×4, плитки, удваивающиеся при соприкосновении, — строго говоря, не решена. Никто не написал алгоритм, который играл бы в неё идеально. У нас есть лишь очень сильные приближения. Поиск expectimax (ожидаемого максимума), заглядывающий примерно на восемь ходов вперёд и оценивающий каждую доску горсткой вручную настроенных эвристик — свободные клетки, крупные плитки, прижатые к краю, гладкость, — доходит до плитки 32768 более чем в трети партий, 1 а сильнейший общедоступный движок добирается до плитки 65536 в нескольких процентах случаев. 2 Для обобщённой доски m×n даже просто определить, достижима ли целевая плитка, — NP-трудная задача. 3 Сильная игра — не то же самое, что решённая игра.
Как высоко может подняться одна плитка? На шестнадцати клетках ответ — небольшой изящный подсчёт. Разложите доску нисходящей лестницей: 65536, 32768, 16384 и так далее вплоть до одинокой двойки. Каждая плитка ровно на одну степень двойки меньше соседней, так что шестнадцать различных степеней от 21 до 216 идеально заполняют доску, а 65536 = 216 стоит на вершине: по одному показателю на клетку. Таков потолок, если игра выдаёт вам только двойки. Но 2048 в одном случае из десяти порождает четвёрку, и одна вовремя появившаяся четвёрка протаскивает семнадцатый показатель, поднимая истинный максимум до 131072 = 217 — степени семнадцати плиток, упакованные в шестнадцать клеток. 4 Ни один человек её не построил; несколько ИИ к ней едва прикоснулись.
Почему эти доски вознаграждают того, кто прячет свою самую крупную плитку в угол? Плитку в центре можно толкнуть в четыре стороны, и её постоянно разлучают с плитками, с которыми она хочет соединиться. Угловая плитка касается двух стен; толчки к стенам, к которым она и так прижата, не могут её сдвинуть, и, пока вы не толкаете в сторону от них, она стоит на месте, а всё остальное выстраивается вокруг неё. Выложите остальное монотонной «змейкой» — старшая плитка в углу, дальше по убыванию, туда и обратно, — и один свайп может запустить каскад слияний. 1 Именно эта эвристика господствует в любительской игре людей, и почти её же заново открывают ИИ, когда им позволяют самим настраивать свои веса.
У игры на слияние со случайным появлением плиток нет соперника — только погода. «Решить» её — значит в среднем обыграть кости, а не обыграть разум.
Теперь наклоним доску в третье измерение. 3927 — кубическая родственница 2048: решётка 3×3×3 из 27 клеток, шесть направлений сдвига вместо четырёх и плитки, сливающиеся по три — 3 в 9, 9 в 27, 27 в 81, — основание три там, где у 2048 основание два. 5 Переживёт ли угловая укладка лишнее измерение? У куба восемь углов, и угловая клетка теперь касается трёх граней, а не двух, — она должна быть ещё устойчивее, прижатая сразу тремя стенами, хотя шесть направлений дают доске больше способов расшатать вашу конструкцию. «Змейка» превращается в сложенный путь, пронизывающий все три слоя. Насколько мне удалось выяснить, никто не проверил, действительно ли аналогия работает; это рассуждение, а не измерение.
А потолок? Правило «один показатель на клетку» подсказывало бы 327 ≈ 7,6 триллиона как грубую верхнюю границу. Но аналогия сильно расползается. Лишний показатель 2048 появился благодаря удачной четвёрке; 3927 порождает только наименьшую плитку — голую тройку, так что бонуса нет. Хуже того, тройному слиянию нужны три плитки, выстроенные в линию, а каждый ряд, столбец и вертикальная стойка в кубе 3×3×3 имеет длину ровно в три клетки, так что каждое слияние поглощает целую линию. Это ограничение кусается куда сильнее всего, что есть в плоской игре, и почти наверняка опускает реальный максимум намного ниже 327. Каково это истинное число, я нигде не нашёл вычисленным. (Это явно обозначенное рассуждение; описанная выше механика взята из проектной документации игры.)
Вот тонкость, из-за которой «идеальная игра» ускользает из рук. Игра на слияние со случайным появлением плиток — это однопользовательская стохастическая игра, пасьянс против игральной кости, а не дуэль. Ничто не выбирает худшую плитку, чтобы вас погубить; есть только равнодушный генератор случайных чисел. Поэтому правильное понятие оптимальной игры — expectimax: максимизировать ожидаемый результат по распределению появлений. Это решительно не минимакс: минимакс предполагает противника, и если действительно позволить ему ставить каждую плитку («злая 2048»), игра превращается в нечто более жестокое, где вас можно вынудить проиграть. Поскольку кости в принципе могут выдать любую последовательность, стратегии, которая гарантирует заданную плитку, может просто не существовать. Так что честный ответ на вопрос «существует ли идеальная стратегия?» таков: для стохастической игры лучшее, что вообще можно определить, — это стратегия, лучшая в среднем, и вычислить её точно для 2048 пока невозможно 6, а для 3927 вопрос полностью открыт.