Анализ 2048 3 на 3

Вот важная новость с фронта ИИ: ilia-ili-ilya 13 минут назад Анализ 2048 3 на 3 Простой 3 мин 763 Алгоритмы * Игры и игровые консоли Математика * Аналитика Из песочницы Вариант этой игры на маленьком поле лучше классического не только тем, что не такой бесконечно долгий, но и возможностью полностью «решить» её. Граф состояний не очень большой, примерно вершин. А зная граф состояний, легко построить оптимальную стратегию игры.

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

Событие, по словам экспертов, усилит конкуренцию в сфере ИИ.