Кнопки Подсказка и Автоигра под полем не выдают заготовленных советов. Они выполняют настоящий поиск прямо в вашем браузере, по тому самому полю, что перед вами, и возвращают ход с наивысшей оценкой. Подсказка показывает стрелку на поле, автоигра делает этот ход снова и снова, пока партия не закончится. На сервер ничего не отправляется.
Если начать с пустого поля и доверить всё этому поиску, он доходит до плитки 2048 в 91,4 % партий. Ниже — как он это делает.
Классический инструмент для деревьев игры — минимакс: он предполагает, что соперник всегда выберет худший для вас ответ, и строит план против него. Но в 2048 соперника нет. Есть плитки, которые появляются случайно, и эта разница очень важна.
Игрок, мыслящий минимаксом, считает новую плитку злонамеренной и предполагает, что четвёрка всегда появится в худшей клетке. В итоге он тратит все вычисления на защиту от позиций, которые случаются реже, чем раз из тридцати, и играет подозрительно и слишком осторожно. Expectimax — поиск по математическому ожиданию — вместо этого усредняет все действительно возможные появления плиток, взвешивая каждое по его вероятности. Он играет по вероятностям, а не по кошмарам, и пока случайность не злонамеренна, это верная модель.
Поэтому поиск чередует два вида узлов. В узлах игрока он пробует все четыре направления и оставляет лучшее. В узлах случая ставит в каждую пустую клетку 2 с весом 0,9 и 4 с весом 0,1, оценивает каждый вариант и усредняет. Это та же пропорция 90 к 10, с которой новые плитки выдаёт сама игра.
Дерево нельзя просматривать до самого конца партии, поэтому в нижней точке поиска решатель оценивает поле по четырём показателям и складывает их с такими весами.
| Член | Вес | Что измеряет |
|---|---|---|
| Пустые клетки | 2.7 | Просто число пустых клеток. Безусловно самый тяжёлый член, потому что проигрывают именно тогда, когда клетки заканчиваются. |
| Монотонность | 1 | Растут ли числа вдоль строк и столбцов плавно в одну сторону, а не скачут вверх-вниз. |
| Угол | 1 | Бонус, зависящий от размера самой большой плитки, когда она стоит в одном из четырёх углов. |
| Гладкость | 0.1 | Штраф за соседство плиток очень разного размера. Двойка рядом с 512 никогда с ней не сольётся — это просто балласт. |
Три из четырёх — это всего лишь привычные советы, переведённые в формулы: держите клетки свободными, сохраняйте порядок, ставьте большую плитку в угол. В суждение их превращают веса. Поиск охотно смирится с чуть худшим положением угла, если взамен получит достаточно пустых клеток, — а люди обычно совершают этот обмен наоборот.
Все члены используют не сами значения плиток, а их двоичный логарифм. Так разница между 2 и 4 весит столько же, сколько разница между 1024 и 2048. Иначе самая большая плитка на поле заглушала бы всё остальное.
Узел случая ветвится по каждой пустой клетке, и каждый раз надвое. На просторном поле с десятью пустыми клетками это двадцать ветвей на уровень, на тесном с тремя — шесть. Искать в обоих случаях на одну и ту же глубину — значит делать всё наоборот: на просторном поле выжить легко, а искать дорого, на тесном — ровно противоположное.
Поэтому глубина подстраивается под поле.
| Пустых клеток | Глубина поиска |
|---|---|
| 7 и больше | На 2 хода вперёд |
| 4–6 | На 3 хода вперёд |
| 3 и меньше | На 4 хода вперёд |
Просторное поле — быстрый взгляд, тесное — гораздо больше осторожности. Это точная копия чутья сильного игрока. Благодаря этому на любой стадии партии ожидание между щелчком и появлением стрелки остаётся комфортным.
За 500 полных партий он дошёл до 2048 в 91,4 % случаев с медианным счётом 37 004 и медианной длиной партии 1 943 ходов. Полные результаты вместе с базовыми стратегиями показывают эти цифры в контексте.
Стоит прямо сказать, что это не передовой бот для 2048. Опубликованные решатели используют битовое представление поля, заранее вычисленные таблицы ходов и кэш транспозиций, ищут гораздо глубже и доходят до 32768. Этот решатель работает в основном потоке браузера на обычных массивах, ничего не кэширует между ходами и ограничен четырьмя ходами вперёд, чтобы страница не подтормаживала. Он сделан не для рекордов, а чтобы отвечать на вопрос «что здесь ходить?» так быстро, что это кажется мгновенным.
Лучший способ пользоваться подсказкой — не следовать ей. Сначала решите ход сами, потом нажмите подсказку. Если стрелка совпала, учиться нечему. Если нет — вы нашли позицию, которую читаете неправильно, и именно там прячется рост.
Автоигра полезнее как показательная партия, чем как спасательный круг. Запустите её в позиции, которая вам самим кажется трудной, и посмотрите, какое направление она бережёт и от каких слияний сознательно отказывается. Нажмите любую стрелку — и управление тут же вернётся к вам.
Решатель — это примерно 250 строк JavaScript без зависимостей, обычный файл /js/ai.js. Если хотите проверить написанное здесь, его можно прочитать прямо через просмотр исходного кода в браузере.
Готовы попробовать?
Играть в 2048