Я обучил нейросеть играть в «Точки» — теперь она меня обыгрывает

Знаете ли вы игру в «Точки»? Это игра на тетрадном листе в клетку, популярная в СНГ и Польше. Двое игроков ставят точки разных цветов на пересечениях клеток и стараются окружить точки соперника. В школе я сыграл в неё немало партий, часто выигрывал и радовался, когда попадался сильный противник.

После универа я начал работать разработчиком и хотел запрограммировать алгоритм для игры в «Точки», но у меня не получилось. Тогда стал смотреть в сторону обучения нейросети, но не знал, с чего начать. Я понимал, что для обучения нейросети нужно огромное количество сыгранных партий, и не понимал, где мне их взять.

Потом я узнал про нейросети для игры в Го, которые генерируют данные для обучения, играя множество партий сами с собой. Решил попробовать такой же подход для «Точек». Обучил нейросеть и сделал небольшое приложение, в котором с ней можно сыграть. Теперь на поле 20×20 она меня обыгрывает.

Когда понял, что нейросеть уже неплохо играет, подумал: почему бы не выложить игру в Steam? И выложил — Just Dots. Я ещё не сделал всё запланированное, но уже можно скачать демо (бесплатно), поиграть и попробовать победить ИИ.

Здесь расскажу, как я учил ИИ-соперника, как после одного из улучшений бот стал играть сильнее, а нейросеть на его партиях — учиться хуже, и почему сделать простого соперника оказалось не так-то просто.

Как окружать точки

На всякий случай напомню правила. Игроки по очереди ставят точки своего цвета на пересечениях клеток и стараются окружить чужие. Окружённым считается всё, что оказалось внутри замкнутой цепочки своих точек, расположенных на расстоянии одной клетки друг от друга (диагонали тоже считаются).

Правила можно выучить за две минуты, но научиться хорошо играть — непросто. Пока ты окружаешь противника, то же самое делает и он. Каждый игрок плетёт свою сеть точек, а партия превращается в гонку ловушек, которые соперники расставляют друг для друга.

Как ИИ выбирает ход

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

В «Точках» этот вариант не сработал.

В шахматах в типичной позиции около 35 возможных ходов. Если на каждом шаге проверять примерно столько вариантов, то на четыре хода вперёд (по два за каждую сторону) получится около 1,5 млн комбинаций. Перебор — выполнимая задача для современных компьютеров. Классическое поле «Точек» — 39×32, то есть до 1248 вариантов хода. В начале партии почти всё поле свободно, и такой же перебор даст около 2,4 трлн комбинаций — примерно в 1,6 млн раз больше, чем в шахматном примере.

При этом мало перебрать ходы — нужно ещё понять, какое продолжение партии лучше для игрока. В шахматах можно хотя бы грубо оценить позицию по силе оставшихся фигур. В «Точках» можно посчитать, сколько точек уже захвачено, но этого мало: у одного игрока может быть больше захватов, а другой вот-вот замкнёт вокруг него большое окружение. Нужно оценить именно саму расстановку точек — насколько она выгодна игроку и какие у него шансы из этой позиции выиграть партию.

Вот этому я и обучаю нейросеть. Она получает позицию и выдаёт число от −1 до +1: −1 соответствует поражению текущего игрока, +1 — победе, 0 — нейтральной оценке. Например, +0,8 означает, что сеть считает его положение близким к выигрышному, а −0,8 — к проигрышному.

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

Один проход по дереву с оценкой позиции называется симуляцией. На каждый ход я выделяю определённое число таких проходов — бюджет поиска. Чем больше симуляций, тем больше продолжений бот может проверить и тем выше шанс найти удачный ход.

Откуда берутся партии для обучения

Для обучения нейросети нужно много сыгранных партий, и я не знал, где их взять. Потом узнал про AlphaZero — программу, которая с помощью нейросети играет в Го. Она обучалась на собственных партиях. Я решил попробовать так же: сеть сама готовит партии, на которых будет учиться следующее поколение.

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

Когда партии сгенерированы и обучено новое поколение сети, оно проходит проверку — «арену». Это серия (несколько сотен) партий против предыдущего поколения, то есть против своего учителя. Если ученик побеждает, он сам становится учителем и будет генерировать обучающие партии для следующего поколения.

За полтора месяца я обучил 30 поколений, прямо сейчас обучается 31-е. На первых поколениях с полями 9×9 и 11×11 генерация партий и обучение занимали около трёх часов. На полях до 23×23 на это уходит уже около 35 часов — партии стали длиннее.

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

Причины каждый раз разные. Иногда приходится откатываться к предыдущим поколениям. Однажды я выкинул девять поколений и начал с нуля.

Два поколения без прогресса

Два поколения подряд не смогли превзойти учителя на арене. Новые партии генерируются, обучение идёт, а ученик лучше не играет.

Я начал перебирать настройки обучения. После каждого изменения — очередная проверка, и снова ученик не может обыграть учителя. Может, сеть слишком простая, чтобы распознавать сложные окружения?

Я увеличил размер сети и обучил её на тех же партиях. Она стала просчитывать ходы примерно вдвое медленнее, но на арене опять не показала превосходства над учителем. Вычислений стало больше, а результата нет.

Тогда я изменил настройки арены — поднял бюджет поиска с 800 до 1600 симуляций на ход — и ученик наконец победил учителя.

Похоже, при меньшем бюджете поиска преимущество ученика не успевало проявиться. Когда боты смогли просчитать больше вариантов, ученик использовал эту возможность лучше учителя. Я пытался исправить обучение, а дело оказалось в арене.

Улучшил бота — следующая сеть стала слабее

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

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

Я проверял настройки обучения и даже сравнивал оценки сети на процессоре и видеокарте — вдруг они вычисляются по-разному. Это не объяснило неудачу. А потом посмотрел статистику самих партий: с сохранением дерева на маленьких полях стало больше ничьих. Например, на 9×9 их доля выросла с 53 до 65%.

Я выключил сохранение дерева, перегенерировал партии и повторил обучение. Новое поколение обыграло учителя!

Похоже, с сохранённым деревом боты лучше защищались и чаще сводили партии к ничьей. В обучающих данных стало меньше примеров того, как выиграть. Получилось, что бот стал сильнее, а учить следующую сеть стал хуже. В итоге в самой игре кэширование дерева включено, а при генерации обучающих партий — выключено.

Как нейросеть попала в игру

Игру я пишу на движке Godot, на .NET 10 (язык C#). Тот же код используется при генерации обучающих партий, когда бот играет сам с собой.

Сеть обучается на Python с помощью PyTorch — библиотеки для работы с нейросетями. Чтобы использовать её в игре на C#, я сохраняю обученную модель в ONNX — формат для переноса нейросетей между разными инструментами. При сборке модель включается в файлы игры, и во время партии она работает прямо на компьютере игрока.

Почему сделать простого соперника не так-то просто

Когда бот начал меня обыгрывать, я решил, что он уже достаточно сильный. Но в игру придут и те, кто только что узнал правила. Для них нужен лёгкий уровень. Я планировал для этого уменьшить бюджет поиска: бот проверит меньше продолжений, чаще пропустит угрозу и даст новичку шанс выиграть.

Но подобрать подходящее значение не получалось. Бот либо всё ещё играл слишком сильно, либо ставил точки куда попало. Хотелось, чтобы новичок мог с ним побороться и победить, но без ощущения, что ему поддаются.

Сначала я не понимал, что мне делать. А потом решил написать для лёгкого уровня отдельного бота, который играет полностью алгоритмически, без нейросети, по эвристическим правилам. Например: «Если тебя сейчас окружат, поставь точку в разрыв цепочки противника, чтобы помешать окружению». Тестирование на новичках показало, что им комфортно играть с таким ботом. Интересно получилось: изначально я пытался использовать этот подход для создания сильного соперника, а пригодился он для лёгкого.

Текущее состояние и планы

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

В демо есть поля 15×15 и 20×20 и три уровня сложности: лёгкий, средний и сложный. Можно освоиться с правилами на лёгком уровне или сразу попробовать обыграть нейросеть. Меня на поле 20×20 сложный уровень стабильно обыгрывает.

К релизу я планирую добавить большие поля, вплоть до классического 39×32. Технически бот уже может на них играть и отвечает быстро, но пока играет слабо — до этих размеров обучение ещё не добралось. Ещё планирую «Хардкор» — четвёртый уровень сложности с увеличенным бюджетом поиска и оптимизациями (чтобы бот по-прежнему отвечал быстро). Всё это ещё в работе. Релиз планирую в декабре.

Если игра заинтересовала — добавьте Just Dots в список желаемого в Steam. Так вы сможете вернуться к ней позже, а для меня это самая полезная поддержка перед релизом.

Демо можно скачать на той же странице. Попробуйте победить ИИ — особенно интересно, как он справится с теми, кто много играл в «Точки» и играет лучше меня.