Глубокое обучение для… шахмат

Автор оригинальной публикации: Эрик Бернхардсон (Erik Bernhardsson)

Перевод Станислава Петренко

Я уже давно собирался заняться изучением Theano, кроме того, мне хотелось создать искусственный интеллект (ИИ) для игры в шахматы. Так почему бы не совместить два этих начинания? Таким был ход моих мыслей, и в итоге я посвятил немало времени этим вопросам.

Теория

Шахматы – игра с конечным числом состояний. Это означает, что, обладая бесконечными вычислительными ресурсами, мы смогли бы найти решение этой игры. Каждая позиция в шахматах это: либо победа для белых, либо победа для черных, либо ничья. Мы можем обозначить это с помощью функции f(позиция). Если бы у нас был бесконечно быстрый компьютер, мы могли бы вычислить ее следующим образом:

  1. Присвоим всем финальным позициям значения –1, 0, 1, в зависимости от исхода игры.
  2. Применим рекурсивное правило f(p) = maxppf(p‘), где pp обозначает все допустимые ходы из позиции p. Знак минус используется потому, что игроки делают ходы поочередно, то есть, если позиция p соответствует ходу белых, тогда позиция p соответствует ходу черных.

Этот подход эквивалентен процедуре минимакс (minimax).

Количество возможных позиций в шахматах составляет около 1043. Вычисления такого масштаба выполнить невозможно. Следовательно, необходимо прибегнуть к аппроксимации f(p).

Как применить машинное обучение для решения этой задачи?

Машинное обучение, по своей сути, сводится к аппроксимации функций на основе некоторых данных. Следовательно, если у нас будет достаточный объем данных, мы сможем аппроксимировать функцию f(p).

Я загрузил 100 миллионов сыгранных партий из базы данных FICS и приступил к обучению. Обучение функции f(p) основано на двух принципах:

  1. Игроки выбирают оптимальные или близкие к оптимальным ходы. Это означает, что для двух последовательных позиций pq мы имеем f(p) = –f(q).
  2. По той же причине, если из позиции p игрок ходит не в позицию q, а в случайную позицию r (pr), должно выполняться неравенство f(r) > f(q), потому что случайная позиция более выгодна для игрока, который будет делать следующий ход, и менее выгодна для игрока, сделавшего данный ход.

Модель

Модель представляет собой нейронную сеть глубиной 3 слоя, шириной 2048 нейронов, с ReLU-нейронами в каждом слое. Входом является слой шириной 8 * 8 * 12 = 768, определяющий присутствие или отсутствие каждой фигуры (всего 12 типов фигур) в каждой клетке (всего 8 * 8 клеток). После трех умножений матриц (каждое с последующей нелинейностью), вычисляется итоговое скалярное произведение с вектором размерности 2048, чтобы свести результат к одному значению.

В общей сложности сеть имеет 10 миллионов неизвестных параметров.

Чтобы обучить сеть, я использовал триплеты (p, q, r). Если обозначить сигмоиду, как

S(x) = 1 / (1 + exp(-x)),

тогда общая целевая функция будет иметь следующий вид:

(p, q, r) log S(f(q) – f(r)) + k log(f(p) + f(q)) + k log(–f(q) – f(p)).

Это лог-правдоподобие (log-likelihood) неравенств f(r) > f(q), f(p) > –f(q), и f(p) < –f(q). Последние два являются способом выражения равенства f(p) = –f(q). Я использовал k, чтобы сделать акцент на правильном получении равенства. Я задал его равным 10,0. Не думаю, что решение очень чувствительно к значению k.

Обратите внимание на тот факт, что функция, которую мы обучаем, не имеет представления о правилах игры в шахматы. Мы даже не обучаем ее тому, как ходит каждая фигура. Наша модель способна генерировать соответствующие правилам ходы, но мы не передаем ей никакой информации о самой игре. Модель извлекает эти знания, обрабатывая огромное количество сыгранных партий.

Следует также отметить, что я не пытаюсь почерпнуть какую-либо информацию на основе того, кто выиграл партию. Причина заключается в том, что обучающие данные содержат множество партий, сыгранных любителями. Если в середине партии в игру вступит гроссмейстер, он может полностью изменить ход партии. Тем не менее, даже игрок-любитель, вероятно, в большинстве случаев делает ходы, близкие к оптимальным.

Обучение модели

Я арендовал GPU на платформе AWS и обучил модель на 100 миллионах партий за четыре дня с помощью стохастического градиентного спуска (stochastic gradient descent) с импульсом Нестерова (Nesterov momentum). Я поместил все триплеты (p, q, r) в файл формата HDF5. В течение некоторого времени я экспериментировал с различными значениями скорости обучения (learning rate), но потом понял, что просто хочу получить хороший результат за несколько дней. В итоге я применил немного необычную схему скорости обучения: 0,03 · exp(–время в днях). Поскольку данные имеют очень большой объем, регуляризация не требуется. Поэтому я не использовал ни дропаут (dropout), ни L2-регуляризацию.

Я применил небольшую хитрость: кодирование доски в виде 64 байтов, а затем преобразование в вещественный вектор размерности 768 на GPU. Это обеспечило значительный прирост производительности, вследствие существенно меньшего количества операций ввода/вывода.

Как работает шахматный искусственный интеллект?

Основой любого шахматного ИИ является некоторая функция f(p), используемая для получения приближенной оценки позиции. Эта функция называется оценочной функцией (evaluation function).

Оценочная функция применяется в сочетании с алгоритмом, выполняющим глубокий поиск среди миллионов позиций в дереве игры. Оказывается, функция f(p) – это лишь небольшая составляющая эффективной игры в шахматы. Все шахматные программы используют интеллектуальные алгоритмы поиска, но при движении по дереву игры количество позиций возрастает экспоненциально, поэтому невозможно выполнить поиск более чем на 5 – 10 позиций вперед. На практике применяется некоторое приближение для оценки листьев, а затем используется какой-либо вариант процедуры негамакс (negamax), чтобы оценить возможные следующие ходы.

Примером простейшей оценочной функции может служить функция на основе ценности фигур: каждая пешка – 1 очко, каждый конь – 3 очка и т.д. Мы же для оценки листьев дерева игры применим обученную нами функцию.

Подведем итог: для решения задачи необходимо обучить функцию f(p), а затем интегрировать ее в алгоритм поиска.

Работает ли описанное решение?

Я назвал свою шахматную программу Deep Pink в знак уважения к создателям Deep Blue. Как выяснилось, функция, которую я обучил, действительно может играть в шахматы. Она выиграла у меня во всех партиях. Хотя я плохой шахматист.

Побеждала ли моя программа другие шахматные программы? Иногда да.

Я устроил соревнование своей программы и программы Sunfish, автором которой является Томас Дибдель Эль (Thomas Dybdahl Ahle). Sunfish, так же как и Deep Pink, полностью написана на Python. В качестве противника я выбрал программу, написанную на Python, потому что она обладает примерно сравнимой скоростью генерации ходов. Я не хотел тратить недели на реализацию граничных случаев с помощью C++, чтобы иметь возможность соревноваться с передовыми шахматными программами. Это была бы просто гонка вооружений.

Очевидно, что эффективность любой оценочной функции f(p) характеризуется не просто точностью, а точностью за единицу времени. Если одна оценочная функция немного лучше другой, но при этом в 10 раз медленнее, преимущество первой не имеет значения, потому что более быстрая (пусть и немного худшая) оценочная функция позволяет выполнить поиск среди большего количества узлов в дереве игры. Поэтому время, затрачиваемое программой на генерацию хода, имеет существенное значение. Теперь давайте посмотрим на результаты соревнования:

Обратите внимание на то, что оси имеют логарифмический масштаб. Оси x и y не очень информативны в данном случае. Основную полезную информацию нам дает расстояние до диагонали, которое показывает, какая из двух программ затратила больше процессорного времени. Перед каждой партией я задавал случайные параметры для каждой программы: максимальную глубину для Deep Pink и максимальное количество узлов для Sunfish. (Я не учел ничьи, поскольку обе программы испытывают с этим трудности.)

Как и следовало ожидать, чем больше времени затрачивала каждая из программ, тем лучше она играла. В целом, Sunfish оказалась лучше, одержав победу в большинстве партий, но Deep Pink тоже показала неплохой результат, выиграв около 1/3 партий. Меня очень вдохновил этот результат. Я думаю, Deep Pink смогла бы играть значительно лучше при некоторой оптимизации:

  1. Более эффективный алгоритм поиска. Я использовал негамакс с альфа-бета-отсечением (negamax with alpha-beta pruning), в то время как Sunfish – MTD-f.
  2. Более эффективная оценочна функция. Deep Pink играет очень агрессивно, но допускает при этом много глупых ошибок. Если использовать для обучения более «сложные» примеры (в идеале на основе тех ошибок, которые сделала программа), в итоге должна получиться более эффективная модель.
  3. Более быстрая оценочная функция. Можно было бы обучить меньшую (но, возможно, более глубокую) версию той же нейронной сети.
  4. Более быстрая оценочная функция. Я не использовал GPU для игры – только для обучения.

Безусловно, реальная цель заключается не в том, чтобы победить Sunfish, а в том, чтобы обыграть одну из передовых шахматных программ. Но для этого потребовалось бы написать тщательно оптимизированный код на С++, а я не уверен, что это лучший способ провести свое время.

Выводы

Я доволен результатом. Следует особо отметить некоторые положительные моменты:

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

Интересно, насколько эффективным было бы мое решение, применительно к таким играм, как го, в которых искусственный интеллект еще не слишком преуспел.

Следует также сказать, что полученные результаты необходимо воспринимать с определенными оговорками. Самая серьезная из них заключается в том, что Deep Pink не соревновалась с какой-либо передовой шахматной программой. Не уверен, найдется ли у меня время для дальнейшей разработки этой темы, но для тех, кто заинтересовался, я разместил весь исходный код на GitHub.

Добавить комментарий

Ваш e-mail не будет опубликован.

закрыть

Поделиться

Отправить на почту
закрыть

Вход

закрыть

Регистрация

+ =