2048 год был решен ИИ?

2048 не решена в формальном смысле теории игр — полной таблицы оптимальных ходов не существует, поскольку пространство состояний игры равно примерно 10 в 47-й степени, что слишком велико для исчерпывающего вычисления. Что сделал ИИ, так это очень близко подошел к нему на практике и в процессе подтвердил, какие человеческие стратегии действительно верны.

Наиболее эффективные подходы ИИ

• Ожидаемый максимальный поиск — вероятностно оценивает все возможные появления плиток и выбирает ход с наилучшим ожидаемым результатом во многих будущих состояниях. Опубликованные реализации сообщают о проценте выигрышей в диапазоне от 90 до 99 процентов в зависимости от глубины поиска.
• Поиск в дереве Монте-Карло (MCTS) — моделирует тысячи случайных игр из текущей позиции и выбирает статистически лучший ход. Приближается к аналогичному проценту выигрышей с менее точным расчетом.
• Глубокое обучение с подкреплением — нейронные сети прошли обучение в миллионах самостоятельных игр и достигли производительности, сопоставимой с ожидаемой максимальной в масштабе.

Почему «решено» — неправильное слово

Решенная игра — это игра, в которой при идеальной игре известен исход каждой достижимой позиции, как в шашках. 2048 дважды провалил этот тест. Во-первых, пространство состояний выходит далеко за рамки перечисления. Во-вторых, и это более важно, 2048 год не является детерминированным: противник является случайным порождением, поэтому даже идеальный игрок не может гарантировать победу из данной позиции, а только лучший возможный ожидаемый результат. Вот почему процент побед ИИ стабилизируется ниже 100 процентов, а не сходится в уверенности — оставшиеся потери носят структурный характер, а не недостаток глубины поиска. Как выглядит человеческая сторона этого дела? всегда ли можно выиграть 2048?

Что это значит для игроков-людей

Практический вывод из исследований ИИ ясен: стратегии, на которых ИИ сходится – угловой анкер, монотонные ряды, максимизация пустых ячеек – действительно оптимальны. Игроки-люди, применяющие их, поступают правильно, просто не имея возможности заглянуть на тысячи ходов вперед. Исследования ИИ подтверждают стратегии; он не открывает никаких ярлыков, которые сделали бы игру тривиально простой для людей.

2048 остается популярным ориентиром в исследованиях ИИ именно потому, что он нетривиален: достаточно мал, чтобы быстро выполнять итерации, и достаточно сложен, чтобы требовать настоящей стратегии прогнозирования.