Кратко о правилах: игроки поочерёдно ставят точки двух цветов в перекрестия линий. Цель — окружить точки соперника замыканием вокруг них непрерывной цепи своих точек.

Вводная информация

Быстро найти какой-то наработанный теоретический материал по этой теме не удалось. В интернете можно разыскать буквально пару тупиковых обсуждений написания искусственного интеллекта для этой игры. Вне стран СНГ точек, можно сказать, вообще не существует. Однако гуглёж на польском таки выдал мне открытый репозиторий с реализацией точек на Си и аж двумя версиями ИИ. Это открытие стало моей отправной точкой для написания собственного решения.

Я поставил для себя следующие цели:

• Перевести проект c Си на родной C#.

• Написать ИИ, который бы как минимум обыгрывал ИИ из найденного репозитория.

• Исследовать возможность использования нейросети.

В мире до сих пор нет нормальных решений для этой игры. Да и плохих нагуглилось всего шесть: 2 приложения в Google Play, 2 от польского разработчика, 1 сайт и 1 приложение AppStore. Я поиграл во всё, и во всех играх ИИ был чрезвычайно слаб. Поэтому у меня не было иллюзий, что я смогу написать решение, которое бы превосходило человека. Весомости моему прогнозу придавал тот факт, что до нейросетей ИИ для го также не блистал умом. У меня же нет ни вычислительных, ни интеллектуальных ресурсов, чтобы повторить успех AlphaGo или KataGo.

Идея

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

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

Реализация

Сразу выявилась проблема бесполезного блуждания поиска, если помеченные точки являются соседями, как показано на видео ниже. Чёрные точки создают «лестницу», из-за которой поиск циклов большую часть времени работает вхолостую.

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

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

Время поиска уникальных циклов стало адекватным. Ну почти. Перебрать вообще все циклы не представляется возможным, поэтому я ограничил время поиска на регион (про регионы чуть позже). Решение этой проблемы, пусть и не полное, было ключевым фактором в возможности осуществления моей задумки. Т.к. основная проблема решена, то начну с разбора работы ИИ с самого начала.

На первом этапе методом заливки происходит разделение вражеских точек на регионы и их объединение, если они расположены достаточно близко друг к другу. Регион — это по сути «остров» из набора точек или компонента связности графа, если говорить в терминологии теории графов. Далее в каждом регионе помечаются (на демке — чёрными точками) соседи вражеских точек. По ним будет осуществляться поиск циклов. Разделение на регионы необходимо, чтобы знать где этот поиск запускать.

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

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

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

Каждый цикл включает в себя следующие данные: координаты точек цикла, координаты вражеских точек во внутренней области цикла (Ray casting algorithm) и координаты собственных точек на цикле. По этим данным можно оценить прогресс заполнения цикла, количество очков при замыкании цикла и вычислить по какой-нибудь формуле его стоимость.

На пятом этапе происходит удаление одинаковых циклов и сортировка оставшихся согласно стоимости.

Все этапы проходятся как за свой цвет, так и за цвет врага, потому что ИИ должен не только нападать, но и уметь защищаться. Для этого отыскиваются быстро достижимые замыкания (1–3 точки до замыкания), которые передаются в обработчики шаблонов. Обработчики «говорят», куда ставить точку, чтобы защититься, если расположение вражеских точек попадает под один из шаблонов обработчика. Примеры ниже:

Левый пример. Куда синим поставить точку, чтобы избежать захвата территории?

Правый пример. Куда синим поставить точку, чтобы стопроцентно захватить территорию? Окружностью показан ошибочный вариант.

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

Примеры партий:

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

Нейросеть

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

Сначала я пытался повторить его код на C# с помощью портированного Torch'a, но такой подход оказался малопродуктивным. Мало того что это занимало большое количество времени, дополнительно возникал большой риск где-нибудь облажаться. После долгих мучений у меня родился план: делаю копипасту проекта, изменяю код под свои нужды, обучаю сеть, сохраняю её в формате ONNX и с помощью пакета Sentis импортирую в Unity. Sentis пока в пре-альфе, но пощупать его можно уже сейчас. Жизнеспособность плана была проверена на крестиках-ноликах 3x3.

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

1. Первой обучается соединяющая сеть. Вместо мешающей сети используются рандомные ходы.

2. На втором шаге обучается мешающая сеть.

3. Когда мешающая начинает побеждать в большинстве случаев, начинается обучаться соединяющая сеть.

4. 2-й и 3-й шаги можно повторять до приемлемого результата.

С первым и вторым шагом проблем не возникло, а вот третий шаг стал последним. После недели обучения (CPU) соединяющая сеть так и не смогла существенно превзойти мешающую. Она упёрлась в потолок и выигрывала всего 70% игр. Дальнейшее обучение я посчитал нецелесообразным. По записям игр (сохранял первые 10 игр из каждой партии по 500 игр) было видно, что соединяющая сеть ведёт себя чрезвычайно тупо. Ни о каком преимуществе перед шаблонами и тем более перед человеком речи не шло.

Из-за того что я полный нуб в машинном обучении, выяснить, в чём проблема, у меня не получилось.

Итог

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