Рассказ о моих выходках с шахматными алгоритмами
Шахматы были моей маленькой страстью последние три года, и за это время я углубился в мир шахматных алгоритмов, пытаясь создать идеального шахматного бота. Вот краткий обзор моего пути
Введение в шахматы
Я всегда любил узнавать что-то новое; В возрасте 9 лет мой двоюродный брат познакомил меня с шахматами, и я сразу же увлекся ими. Величайшие шахматные мастера начинали примерно в этом возрасте и продолжали доминировать в игре, но почти десятилетие спустя я и близко не достиг этого уровня :P . Я проигрывал своему двоюродному брату большую часть времени, но через несколько недель я начал играть довольно хорошо (сейчас я редко играю в шахматы, и официально я отстой :D ).
Перенесемся на пару лет вперед, и я учусь в старшей школе, играю в шахматы со своими товарищами. Шахматы были игрой, которая нас всех сблизила. Я играл с одним из лучших в школе… и проиграл.
Будучи конкурентоспособным засранцем и программистом, изучающим машинное обучение в то время, я сказал ему: «Дайте мне несколько месяцев, и я создам бота, который победит вас».
Второе поражение
Наиболее очевидным алгоритмом для применения в шахматах является алгоритм мини-макс.
Идея мини-макс состоит в том, чтобы искать дерево игры до определенной глубины, а затем оценивать каждую позицию в конце этой глубины. Позиции оцениваются на основе эвристической функции, которая присваивает балл каждой позиции. Затем алгоритм выбирает ход, который приводит к наилучшему результату, тем самым максимизируя наши шансы на победу и сводя к минимуму шансы нашего противника, отсюда и минимальный аспект.
Как вы понимаете, это исчерпывающий алгоритм, и качество игры зависит от эвристической функции и глубины поиска.
У меня не было вычислительного кластера, чтобы попробовать большие значения глубины для посредственной эвристической функции, поэтому я попытался создать действительно хороший оценщик перемещений/эвристическую функцию 🤩.
Я сделал то, что сделал бы любой другой человек, занимающийся машинным обучением; использовать нейронную сеть в качестве эвристической функции.
На самом деле это уже много раз делалось в прошлом (Deep Pink by Erik Bern и т.д.). Мне было интересно, почему мы не можем предсказать оценку за один раз, которая не требует минимальных и максимальных значений, верно? (Я проверил это и быстро понял, что это наивный вопрос 😭).
Я рассматривал эту проблему как обучение нейронной сети для аппроксимации оценок положения доски Stockfish (на заданной глубине).
Это было на самом деле очень хорошо! но недостаточно хорош, чтобы победить моего парня 🤣. Второе поражение за год.
Код для этого здесь и здесь. Я потерял исходный код, против которого играл мой тогдашний одноклассник :-(
Зависимость
После создания бота и проигрыша, я не знаю почему, но я продолжал исследовать и думать о том, как улучшить алгоритм.
Примерно в это же время суета с RL начала неуклонно расти, и я не решался применить RL к этому: P Тем не менее, я пробовал другие методы.
Техника №1
Что, если мы заставим нейросетевой оценщик позиции учитывать временную динамику шахмат? Вместо подачи статического представления доски на каждом временном шаге игры мы подаем последовательность представлений доски для каждого шага вывода.
где:
x_t = скрытое представление на доске во время t
f = модель последовательности (RNN
e = оценка позиции
Это может потенциально устранить необходимость в оценке ходов на основе дерева, такой как мини-макс.
Техника №2
Языковые модели сейчас в моде! Трудно сейчас не наткнуться на контент, связанный с LLM / ChatGPT / GPT3.5 / Proompter-Engineering.
У меня есть идея — почему бы не попробовать выполнить моделирование последовательности на Portable Game Notation шахматной игры. Может ли нейронная сеть научиться понимать шахматы исключительно из текстового представления? Таким образом, обучение модели последовательности (преобразователь, RNN, GRU и т. д.) на последовательностях алгебраической записи в файле PGN.
Я нашел это очень интересным для работы, потому что рассмотрение этого как проблемы моделирования последовательности означает, что мы можем выбирать из распределения токенов (мы можем указать стохастичность через температуру) и подсказывать ему конкретные результаты (я называю это внедрением результатов). Возможности подсказок удивили меня (хотя и не должны были), потому что я мог просто обмануть его, заставив думать, что результат должен быть в пользу ботов, и бот должен вернуть ход, который выполняет это.
В этой настройке мы пытаемся максимизировать вероятность правильного хода с учетом предыдущих токенов в PGN.
Математически,
Все технические детали находятся в коде, и я настоятельно рекомендую вам ознакомиться с ним :)
Это на самом деле закончилось игрой достаточно хорошо. Я бы подумал, что он воспроизводит статистически вероятную последовательность ходов для всего, с чем сталкивается (чего вы ожидаете, это модель последовательности).
Не маскируя недопустимые ходы, он пытается сыграть много недопустимых ходов. Я считаю, что с большим количеством данных он выучит правила игры в шахматы и вряд ли будет делать незаконные ходы (так же, как языковые модели учатся связно писать и правильно использовать грамматику).
Я очень ценю, что вы читаете эту статью! Если у вас есть какие-то отзывы, вопросы, дополнения, убавления, пишите в комментариях, с удовольствием посмотрю :)
