Коллеги показали игру 2048. Смесь пятнашек с… эээ… тетрисом, что-ли. Сама игра меня не сильно заинтересовала (был очень занят по работе), но вечером меня торкнуло и я решил сделать бота для нее. Захотелось применить пылившиеся знания по основам AI полученным после прохождения курса CS188.1x: Artificial Intelligence на edX.

Результат можно посмотреть на гитхабе: 2048AI. Текущая реализация бота набрала мне 12К очков и сложила число 1024. Учитывая, что бот у меня тупой-тупой (см. ниже), это можно считать отличным результатом!

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

Из казусов. Я ошибся с первой своей эвристикой (сумма всех цифр на поле) и все следующие ходы получали одинаковую оценку. Поэтому ходы выбирались по очереди: сначала пробуем вверх, если ход не имеет смысла, то влево, … Так вот. Этот бот набрал 5000 очков. Значение, которого “более умным” ботам не сразу удалось достигнуть.

Анализ задачи

Задача является задачей взаимодействия с противником (появляющиеся на поле цифры), который действует случайным образом, в мире, поведения которого мы можем предсказать (смоделировать).

Раз мы имеем дело с противником, то решить задачу offline-способом нельзя и лучшей стратегией будет вычислять наиболее оптимальный ход, совершать его и ждать ответного хода противника.

А раз у нас полностью моделируемый мир, то никакие алгоритмы обучения нам не нужны. Чистая математика (хотя алгоритмы обучения тоже чистая математика, никакой магии).

Бот aka Рациональный Агент

Бот наш, в соответствии с картинкой, будет состоять из 3 частей:

• модуль взаимодействия с внешним миром (с браузером, с помощью Selenium )

• модуль оценки ситуации и принятия решения (сам AI)

• управляющий модуль (который все это склеивает вместе)

Модуль взаимодействия с внешним миром я написал достаточно быстро. Получить расположение цифр на поле не сложно, а набор возможных действий не велик. Хотя и здесь не обошлось без тонкостей: Селениум был настолько быстр, что браузер просто не успевал обновлять страницу и модуль падал. Лечил я это с помощью задержки (что не так уж просто сделать), а в последствии несколькими попытками чтения состояния.

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

while (game.CanMove)
{
    var move = agent.MakeDecision(game.GridState);
    game.Turn(move);
}

Artificial Intelligence

Самым сложным, как и ожидалось, был модуль AI. Он состоит из:

• модели мира (вычисляющей состояние мира в ответ на действие агента)
• эвристики (численной оценки текущего состояния мира, больше – лучше)
• агента (просчитывающего ситуацию на несколько ходов вперед, например)

С моделью мира я провозился больше всего. Под конец даже переключился в режим “говнокодим. главное, чтобы тесты прошли”. Код игровой логики. Слабонервным не смотреть! Я предупреждал))

Эвристика тоже сложная штука. Нужно посидеть, подумать, порисовать ситуации на бумаге. Но, тут есть одна хитрость, которую я понял при прохождении курса: даже простая эвристика может давать хорошие результаты. Поэтому я остановился на простой эвристики в виде суммы квадратов (т.е. чтобы объединять квадраты было выгодно) и дополнил ее правилом “наибольшая цифра в верхнем левом углу очень, очень, ну просто очень хорошо”. Такая эвристика, вкупе с оценкой на 2 хода в глубину, позволили выбить 12К очков.

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

Код агентов обычно не меняется от задаче к задаче. Т.е. однажды написанный агент может быть использован неоднократно. Я, например, планирую поднять код, который я писал для курса, и забрать алгоритм агента оттуда. Что еще интересно, эвристики и агенты – это разные ветки развития AI. Новую эвристику можно подключить к любому из агентов, а новый агент можно использовать с уже существующими эвристиками.

Заключение

Сделать бота для игры не так уж и просто, но в этом нет никакой магии. Если вы, все еще, считаете решение таких задач магией, то я настоятельно рекомендую прослушать курс CS188.1x: Artificial Intelligence. Кроме задач взаимодействия с противником в курсе рассмотрено как решаются задачи на составление расписаний, обход лабиринта наиболее оптимальным способом, а так же самообучающиеся агенты.