— Стало быть, эта штуковина только выглядит так, будто умеет думать? — Э… да.— А на самом деле не думает? — Э… нет.
— То есть просто создаёт впечатление, будто бы думает, а на самом деле это всё показуха?
— Э… да. — Ну точь-в-точь как все мы.
Терри Пратчетт "Санта-Хрякус"
Триумфальные победы AlphaGo (и впоследствии AlphaZero) всколыхнули интерес общественности как к нейросетям, так и к настольным играм. Конечно, есть люди, которые считают, что AlphaZero «побеждает нечестно», поскольку на самом деле учится не совсем с нуля, а использует поиск Монте-Карло, в дополнение к тому, что ему советует нейросеть (говоря серьёзно, использование языковых моделей, в применении к настольным играм, выглядит интригующим и я желаю всяческих успехов в этом направлении), но хочется поэкспериментировать с чем-то не требующим грандиозных вычислительных мощностей и получить на выходе что-то, пусть и не играющее «на уровне Бога», но вполне пригодное для того чтобы играть с ним было интересно.
Мне важен результат и я готов использовать минимакс, Монте-Карло или даже нейросети, лишь бы добиться хоть какого-то успеха (особенно с учётом некоторых ограничений накладываемых JavaScript на производительность, по сравнению с компилируемыми языками и массовым использованием GPU). Разумеется, начинать эксперименты с Го несколько самонадеянно. К счастью, это не проблема. Я знаю много других игр.
Игра "Гекс", независимо придуманная двумя известными математиками, Питом Хейном и Джоном Нэшем в 40-ых годах прошлого века, выглядит достойным кандидатом для экспериментов. Правила очень простые: игроки по очереди ставят по одному камню своего цвета на пустые поля доски. Для победы необходимо соединить противоположные стороны доски непрерывной цепочкой камней своего цвета. В целях компенсации преимущества первого хода, используется «правило пирога»: второй игрок может сменить цвет, сразу же после выполнения в игре самого первого хода.
Эта игра словно предназначена для машинного обучения. Камни, поставленные на доску, впоследствии не перемещаются и не убираются с доски, что ограничивает максимальную продолжительность партии. Кроме того, довольно очевидно, что один из игроков обязательно победит, а поскольку цели игроков исключают друг друга, никакие ничьи в игре невозможны.
В то же время, тактика игры вовсе не тривиальна. Прежде всего, как и в Го, в Гексе существуют «хорошие формы». Речь идёт о неразрезаемости. Конечно, если мы играем вплотную, камень к камню, разрезать такое соединение нельзя, но соединяясь таким образом, мы продвигаемся по доске слишком медленно. При размещении камней по диагонали, продвижение идёт гораздо быстрее, без какого либо ущерба надёжности. Если удастся соединить неразрезаемыми формами обе свои стороны, мы победили!
Если конечно не забывать ставить камень в парную точку, при попытке разрезания формы противником. Соединение по диагонали («мост») самая простая и чаще всего используемая форма. Вообще же, известных форм довольно много. Кроме того, как показывает практика, в этой игре гораздо плодотворнее думать о том как не дать противнику соединиться, чем пытаться соединить свои стороны самому. Если удастся помешать победить противнику, победа никуда не уйдёт. Теперь, когда мы немного разобрались с тактикой, вот вам задачка от Камерона Брауна:
Ход белых
Решение
Начинаем с попытки разрезания моста (11). Чёрные отвечают вполне закономерно и ход может показаться бесполезным, но это не так.
Прорываемся сквозь строй белых (13). У чёрных есть отличный ответ и попытка была бы обречена на неудачу, если бы не предыдущий ход. Соединяемся (15):
и победа у белых в кармане…
Начинаем с попытки разрезания моста (11). Чёрные отвечают вполне закономерно и ход может показаться бесполезным, но это не так.
Прорываемся сквозь строй белых (13). У чёрных есть отличный ответ и попытка была бы обречена на неудачу, если бы не предыдущий ход. Соединяемся (15):
и победа у белых в кармане…
Cтоит сказать о том, почему алгоритмы, столь хорошо зарекомендовавшие себя в Шахматах, для Гекса малоприменимы. Прежде всего, коэффициент ветвления дерева состояний в игре Гекс очень высок. Если в Шахматах, из начальной позиции, доступно всего 20 ходов, то в Гексе, на доске 11x11, их более сотни. Может показаться что разница не так велика, но при углублении перебора мы сталкиваемся со степенной функцией.
Вторая причина заключается в отсутствии удобной оценочной функции. В Шахматах, в первом приближении, оценка сводится к подсчёту материала (фигур на доске). Это очень быстро и хорошо работает, поскольку значение функции оценки монотонно и достаточно плавно увеличивается, по мере приближения игрока к победе. В Гексе, как и в Го, отдельные камни на доске не имеют значения. Важно их взаимное расположение. В результате, поскольку у нас нет оценочной функции, мы не можем останавливать перебор на какой-то фиксированной глубине, как это делается в шахматных алгоритмах.
Строго говоря, это не совсем так
Ещё в 1950-ом году, Клод Шеннон и Эдвард Мур сконструировали аналоговую машину, довольно неплохо игравшую в Гекс. Машина представляла собой сеть сопротивлений с выключателями в ячейках доски. Ход человека размыкал электрические цепи, а измерение напряжения на отдельных узлах сети (визуализируемое простыми электрическими лампочками) подсказывало лучший ответный ход.
Я экспериментировал с этим, вычисляя максимальный поток в графе. К сожалению, успеха на этом направлении добиться не удалось. Такая оценка ресурсозатратна сама по себе, а высокий коэффициент ветвления буквально свёл на нет все усилия. За 10 секунд перебора мне удавалось углубиться всего на 2 полухода, чего совершенно недостаточно для того чтобы начали работать какие либо оптимизации альфа-бета отсечения. Возможно это работало бы в нейтивных сборках на C++, но для JavaScript этот путь, по всей видимости, закрыт.
Я экспериментировал с этим, вычисляя максимальный поток в графе. К сожалению, успеха на этом направлении добиться не удалось. Такая оценка ресурсозатратна сама по себе, а высокий коэффициент ветвления буквально свёл на нет все усилия. За 10 секунд перебора мне удавалось углубиться всего на 2 полухода, чего совершенно недостаточно для того чтобы начали работать какие либо оптимизации альфа-бета отсечения. Возможно это работало бы в нейтивных сборках на C++, но для JavaScript этот путь, по всей видимости, закрыт.
К счастью, при использовании метода Монте-Карло, этого и не требуется. Суть подхода заключается в том, что симуляция игры каждый раз ведётся до победы одного из игроков. При этом, все допустимые ходы из начальной позиции и все ответы противника проверяются полностью, а последующие ходы выбираются случайно. Количество просмотров и количество побед для каждого хода из начальной позиции фиксируются. Очевидно, что при таком подходе вычислять оценочную функцию не требуется, но возникает другой вопрос: в соответствии с каким критерием выбирать начальные ходы, чтобы максимально исследовать наилучшие ходы, с одной стороны и при этом не забывать о всех остальных ходах? Решению этого вопроса посвящена знаменитая "задача о многоруком бандите".
Здесь w[i] — количество побед при выборе i-го хода, n[i] — количество проверок хода, а N — общее количество симуляций. Коэффициент c подбирается экспериментально и определяет насколько значима разведка ещё не исследованных ходов по сравнению с более глубоким исследованием ходов, обеспечивающих большее количество побед. По завершении всех симуляций (или когда закончится время на обдумывание хода) выбирается ход с наибольшим количеством проверок (ход с наибольшим количеством побед может оказаться просто недостаточно исследованным). Можно ли как-то улучшить этот алгоритм? Конечно.
И это приводит нас к нейросетям
Как я уже сказал, допустимых правилами ходов в Гексе много. Особенно в начале игры, когда это действительно важно. Конечно, MCTS должен просмотреть их все, но небольшая подсказка поможет сконцентрироваться на наиболее перспективных ходах. Как отличить хорошие ходы от плохих? Прежде всего, нельзя допускать разрезания мостов. Это должно работать даже не как AI, а скорее на уровне инстинктов.
Далее, мы можем захотеть сделать игру нашего бота более похожей на то, как играют люди. Это просто — надо взять достаточно большую базу данных игр людей друг с другом, и обучить нейросеть на её основе. Обученная модель будет предсказывать наиболее вероятные ходы из той или иной позиции. Полученные вероятности Q[i] называются априорными. Просто добавим их к нашему критерию выбора в качестве дополнительного слагаемого, не забыв поделить на N, для того чтобы обеспечить уменьшение их влияния, по мере получения результатов симуляций.
Архитектура модели почерпнута из замечательной книги, посвященной использованию нейросетей в применении к игре Го. Несколько свёрточных слоёв определяют наличие на доске базовых паттернов, после чего плотные слои формируют матрицу априорных вероятностей для возможных ходов. Поскольку речь идёт о вероятностях и выборе одного хода из нескольких возможных, softmax используется в качестве функции активации в последнем слое, а categoricalCrossentropy определяет функцию потерь. Функция активации relu, в промежуточных слоях, помогает бороться с возможными проблемами переобучения посредством регуляризации.
Потребовалось несколько суток для получения исходных данных, после чего выяснилось, что подавляющее число игр велось на доске 10x10. Впрочем, 15255 игр, для первичного обучения модели, оказалось вполне достаточно. Ещё один важный момент: данные для обучения крайне желательно перемешивать таким образом, чтобы позиции относящиеся к одной и той же игре не следовали друг за другом (и не попадали таким образом в один пакет обучения). Всякого рода сортировками я предпочитаю заниматься внутри базы данных. Просто выгружаем результат разбора игр, добавляя к каждой строке случайное число, потом сортируем и выгружаем в csv для последующего обучения.
Есть ещё кое что важное, о чём стоит упомянуть. В какой-то момент бот начал вести себя странно. Он выигрывал, но делал это не благодаря, а скорее вопреки своим ходам. Вообще, складывалось впечатление, что бот пытается соединить верх и низ доски, пытаясь играть за первого, а не за второго игрока. Попытки исправить это продолжались довольно долго, пока я не понял, что чтобы не путать себя и бота, любую позицию следует рассматривать с точки зрения первого игрока, при необходимости отразив доску относительно главной диагонали. Это всё сильно упростило и дело пошло на лад.
Если отражение доски использовалось как при обучении модели так и в ходе работы бота, то поворот доски имел отношение только к процессу обучения. Когда я работал с уже обученной моделью для игры Го, то заметил, что рекомендуемые ей ходы не симметричны. Так первый ход всегда выполнялся в пункт 4-4 в правый верхний угол (понятно, что начальные ходы в остальные три угла совершенно равноценны). В тот момент (поскольку модель была уже обучена), я заменил один вызов predict шестнадцатью, восемь раз повернув и отразив доску и изменив цвет камней (лучший ход противника — это и твой лучший ход), но более правильным решением было бы добавление всех этих отражений и поворотов в обучающую выборку. При обработке изображений, такая операция называется обогащением исходных данных. В случае Гекса, доска более хитрая и достаточно всего одного поворота (относительно центра доски).
Далее, мы можем захотеть сделать игру нашего бота более похожей на то, как играют люди. Это просто — надо взять достаточно большую базу данных игр людей друг с другом, и обучить нейросеть на её основе. Обученная модель будет предсказывать наиболее вероятные ходы из той или иной позиции. Полученные вероятности Q[i] называются априорными. Просто добавим их к нашему критерию выбора в качестве дополнительного слагаемого, не забыв поделить на N, для того чтобы обеспечить уменьшение их влияния, по мере получения результатов симуляций.
Архитектура модели почерпнута из замечательной книги, посвященной использованию нейросетей в применении к игре Го. Несколько свёрточных слоёв определяют наличие на доске базовых паттернов, после чего плотные слои формируют матрицу априорных вероятностей для возможных ходов. Поскольку речь идёт о вероятностях и выборе одного хода из нескольких возможных, softmax используется в качестве функции активации в последнем слое, а categoricalCrossentropy определяет функцию потерь. Функция активации relu, в промежуточных слоях, помогает бороться с возможными проблемами переобучения посредством регуляризации.
Потребовалось несколько суток для получения исходных данных, после чего выяснилось, что подавляющее число игр велось на доске 10x10. Впрочем, 15255 игр, для первичного обучения модели, оказалось вполне достаточно. Ещё один важный момент: данные для обучения крайне желательно перемешивать таким образом, чтобы позиции относящиеся к одной и той же игре не следовали друг за другом (и не попадали таким образом в один пакет обучения). Всякого рода сортировками я предпочитаю заниматься внутри базы данных. Просто выгружаем результат разбора игр, добавляя к каждой строке случайное число, потом сортируем и выгружаем в csv для последующего обучения.
Пара слов о форматах данных
Прежде всего, я позволил себе внести небольшие изменения в FEN-нотацию. Поскольку все фигуры в игре одного типа, буквы от 'a' до 'k' кодирует непрерывные последовательности камней одного цвета. Заглавные буквы используются для камней первого игрока. Цифры от '1' до '9' по прежнему кодируют пустые поля. Позиция на доске задаётся числом от 0 до 120 (просто перебираем позиции по порядку: сверху-вниз и слева-направо). Исходные данные выглядят иначе:
Каждая пара символов определяет очередной ход. Первая буква задаёт столбец, вторая строку (мне пришлось потратить некоторое количество времени чтобы выяснить это). Этот формат данных также был расширен. Мне понадобилось хранить оценку позиции на момент выполнения хода (ниже я расскажу, для чего это понадобилось). Поскольку это число из интервала (-1, 1), достаточно записывать знак и несколько цифр после десятичной точки. В результате получилось что-то в этом духе:
Вас может сбить с толку, что числа записаны не перед каждой парой символов, но этому есть простое объяснение. Оценку позиции в этой игре производил только второй игрок.
BbFeDfChEgEhGgGhHhFgGeHgDhCjDiDjEiHcEdFbDcDbEb
Каждая пара символов определяет очередной ход. Первая буква задаёт столбец, вторая строку (мне пришлось потратить некоторое количество времени чтобы выяснить это). Этот формат данных также был расширен. Мне понадобилось хранить оценку позиции на момент выполнения хода (ниже я расскажу, для чего это понадобилось). Поскольку это число из интервала (-1, 1), достаточно записывать знак и несколько цифр после десятичной точки. В результате получилось что-то в этом духе:
Eb-08FgHf03GhHh03GiHi03HgIg03CiGe03IfEf03DhJf-JeKd03KeGd03BjEg03EhFh03GgCh03JcAj03Ak
Вас может сбить с толку, что числа записаны не перед каждой парой символов, но этому есть простое объяснение. Оценку позиции в этой игре производил только второй игрок.
Есть ещё кое что важное, о чём стоит упомянуть. В какой-то момент бот начал вести себя странно. Он выигрывал, но делал это не благодаря, а скорее вопреки своим ходам. Вообще, складывалось впечатление, что бот пытается соединить верх и низ доски, пытаясь играть за первого, а не за второго игрока. Попытки исправить это продолжались довольно долго, пока я не понял, что чтобы не путать себя и бота, любую позицию следует рассматривать с точки зрения первого игрока, при необходимости отразив доску относительно главной диагонали. Это всё сильно упростило и дело пошло на лад.
Если отражение доски использовалось как при обучении модели так и в ходе работы бота, то поворот доски имел отношение только к процессу обучения. Когда я работал с уже обученной моделью для игры Го, то заметил, что рекомендуемые ей ходы не симметричны. Так первый ход всегда выполнялся в пункт 4-4 в правый верхний угол (понятно, что начальные ходы в остальные три угла совершенно равноценны). В тот момент (поскольку модель была уже обучена), я заменил один вызов predict шестнадцатью, восемь раз повернув и отразив доску и изменив цвет камней (лучший ход противника — это и твой лучший ход), но более правильным решением было бы добавление всех этих отражений и поворотов в обучающую выборку. При обработке изображений, такая операция называется обогащением исходных данных. В случае Гекса, доска более хитрая и достаточно всего одного поворота (относительно центра доски).
Технология разработки бота для DagazServer была уже отработана ранее. Полученный в результате бот играет в Гекс довольно неплохо, но сила его игры зависит, в первую очередь, от качества обучения модели. Обучение с учителем — это только первый шаг, поскольку не позволяет играть лучше тех людей, игры которых составили обучающую выборку. Чтобы двигаться дальше, требуется ещё один инструмент, позволяющий боту играть самому с собой или с другой версией бота.
Что на счёт REINFORCE?
Обучающие данные — это то, чего больше всего не хватает при обучении с учителем. По этой причине, мы используем данные повторно, снова и снова, проводя обучение на большом количестве эпох. Было бы лучше обучаться на уникальных данных, но исходные данные слишком ценны. Их всегда недостаточно! Но даже если данные имеются в достаточном количестве, мы не всегда можем быть уверены в их качестве. Вот одна игра, из тех что я скачал. Самая первая (картинка кликабельна)!
Серьёзно, кто-то практиковался в абстрактном искусстве, а в результате игра попала в обучающие данные. Чему хорошему может научиться модель на таких примерах? К сожалению, данных действительно очень много и совершенно невозможно проверить их все вручную. Но мы всегда можем получить новые данные, заставив бота играть самого с собой.
Это одно из назначений HexAuto. Другое его применение заключается в том, что мы можем автоматизировать сравнение силы различных ботов по итогом серий их игр друг с другом. Победы в одной игре недостаточно для того чтобы определить что один бот сильнее другого. Слабый бот мог победить вследствие случайного стечения обстоятельств. Для более корректной оценки используется биномиальный тест.
Если один бот победил другого 51 раз в серии из 100 игр, можно сделать вывод от том, что они равны по силе (0.5) с вероятностью 92%. Если же побед было 60, равенство ботов по силе маловероятно (5%). Нам необходимо большое количество игр, как для дообучения модели, так и для сравнительной оценки ботов. Насколько качественно будут играть боты зависит от выбранного алгоритма. Можно просто семплировать вероятности предсказанных ходов (что будет работать экстремально быстро), либо запустить полноценный MCTS, используя вероятности полученные от модели в качестве априорных. Разница очевидна:
В 77 раз медленнее, но зато гораздо осмысленнее! Кстати, обратите внимание: модели в этих двух прогонах использовались одни и те же, но при использовании sample-ai уверено лидировал первый игрок, в то время как для mcts-ai вторая модель подошла гораздо лучше. Объяснением этому может быть то, что вторая модель менее обучена и предоставляет MCTS большую свободу в выборе хода. В любом случае, достаточно очевидно, что обучать модель следует с учётом того как она будет использоваться. То что хорошо подходит для простого алгоритма, может оказаться неподходящим для более продвинутого.
Как бы там ни было, теперь у нас имеется потенциально бесконечный источник качественных данных. Каким образом это использовать? От «обучения с учителем» можно перейти к «обучению с подкреплением». По завершении игры, мы знаем кто из игроков победил. Это означает, что можно формировать обучающие данные таким образом, чтобы подкрепить ходы победителя и сделать менее вероятными выбор ходов ведущих к поражению. REINFORCE именно об этом.
Однако, здесь есть одна проблема: не все ходы выполненные в ходе игры вносят равноценный вклад в достижение победы. Подкрепляя слабые ходы мы можем не только затянуть процесс обучения, но и научить модель плохому. Интуитивно понятно, что ход «переломивший игру», выполненный из проигрышного положения, намного ценнее обычного тихого хода из позиции, в которой игроку ничего не угрожает, но как это формализовать? Мне нравится метод «актор-критик», формирующий подкрепление в зависимости от оценки позиции, с точки зрения игрока. Откуда взять оценку? У нас есть нейросеть, вот пусть она и считает!
Здесь, помимо выхода политики, добавлен дополнительный выход оценки (для чего пришлось перейти от последовательного API к функциональному). Подкрепление каждого хода формируется как R-E (где R означает награду — 1 у победителя и -1 у проигравшего, а E — оценку текущей позиции с точки зрения игрока). Поскольку выход оценки — непрерывное вещественное значение, в качестве функции потерь берётся mse, а tanh используется как функция активации в последнем слое.
Настройка обучения с подкреплением имеет свою специфику. Как правило, такие модели обучаются «с нуля» и качество обучающих данных, по крайней мере в начале процесса обучения, далеко от идеального (а по правде сказать, близко к рандомному). По этой причине, к таким данным следует относиться с крайней осторожностью. Не следует использовать такие данные повторно, устанавливая количество эпох больше 1, а размер пакета следует выбирать побольше (например 1024), чтобы как-то сгладить возможные огрехи в обучающих данных.
Также, при обучении с подкреплением, не следует использовать адаптивные алгоритмы оптимизации, такие как adagrad или adam, отдав предпочтение старому доброму стохастическому градиенту. Скоростью обучения рекомендуется управлять вручную, задавая в начале малые значения (~0.001) и постепенно увеличивая по мере необходимости. Это может помочь не пролетать мимо минимума функции потерь в процессе обучения.
Серьёзно, кто-то практиковался в абстрактном искусстве, а в результате игра попала в обучающие данные. Чему хорошему может научиться модель на таких примерах? К сожалению, данных действительно очень много и совершенно невозможно проверить их все вручную. Но мы всегда можем получить новые данные, заставив бота играть самого с собой.
Это одно из назначений HexAuto. Другое его применение заключается в том, что мы можем автоматизировать сравнение силы различных ботов по итогом серий их игр друг с другом. Победы в одной игре недостаточно для того чтобы определить что один бот сильнее другого. Слабый бот мог победить вследствие случайного стечения обстоятельств. Для более корректной оценки используется биномиальный тест.
>>> from scipy.stats import binom_test
>>> binom_test(51, 100, 0.5)
0.9204107626128211
>>> binom_test(60, 100, 0.5)
0.056887933640980784
Если один бот победил другого 51 раз в серии из 100 игр, можно сделать вывод от том, что они равны по силе (0.5) с вероятностью 92%. Если же побед было 60, равенство ботов по силе маловероятно (5%). Нам необходимо большое количество игр, как для дообучения модели, так и для сравнительной оценки ботов. Насколько качественно будут играть боты зависит от выбранного алгоритма. Можно просто семплировать вероятности предсказанных ходов (что будет работать экстремально быстро), либо запустить полноценный MCTS, используя вероятности полученные от модели в качестве априорных. Разница очевидна:
sample-ai
Won [1]: Fc03GfFg03HdGh448IdHc03AfEf03AkJb03JdBi999HfIg999DeCj991ChBg03GgFh330JjBh03AdKc03BdBa553IcIb666GiDd03BkCc03IfBe03CdDc03CeCk03AeHh03FaBb03EhJg03AjCi03EkKf03AiAh03EdKd03EcFe03BcKb03GbCb03CaFd03AgGc03GeDa03GjCf03BfGa03FbDh03EgDg03CgFf03DfDj03HiFi03FjKh03AbAc03AaJi03DkHg03HkIk03KiIj03HjEi03DiEj03HbIa
o * o * . o * . * . .
o * * . . o o o * * *
* o * * o * * * o . *
o o o * o * . o o o *
o * o o . * o . . . .
o o * o * * o o o . *
o * o * o * o * * * .
* * o * o * * * . . *
o * * o * * o o . * o
o . * * * o o o * o .
o o * o o . . o * . .
FEN: aAaA1aA1A2/aB2cC/AaBaCa1A/cAaA1cA/aAb1Aa4/bAaBc1A/aAaAaAaC1/BaAaC2A/aBaBb1Aa/a1CcAa1/bAb2aA2-w
Total: 9/1 (10), time = 23.952
mcts-ai
Lose [2]:Hc03IiFf445EhDg03CiGg03FhHh03GiGj03HiJh03JiGh03FiKi03KhBi03BjAk03AjDi03Dh
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . * . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . * . . . . .
. . . * . . * . . . .
. . . o o o * * . * o
. * o * . o o o o o *
o o . . . . * . . . .
* . . . . . . . . . .
FEN: 92/92/7A3/92/92/5A5/3A2A4/3cB1Aa/1AaA1eA/b4A4/A91-w
Total: 2/8 (10), time = 1773.71
В 77 раз медленнее, но зато гораздо осмысленнее! Кстати, обратите внимание: модели в этих двух прогонах использовались одни и те же, но при использовании sample-ai уверено лидировал первый игрок, в то время как для mcts-ai вторая модель подошла гораздо лучше. Объяснением этому может быть то, что вторая модель менее обучена и предоставляет MCTS большую свободу в выборе хода. В любом случае, достаточно очевидно, что обучать модель следует с учётом того как она будет использоваться. То что хорошо подходит для простого алгоритма, может оказаться неподходящим для более продвинутого.
Как бы там ни было, теперь у нас имеется потенциально бесконечный источник качественных данных. Каким образом это использовать? От «обучения с учителем» можно перейти к «обучению с подкреплением». По завершении игры, мы знаем кто из игроков победил. Это означает, что можно формировать обучающие данные таким образом, чтобы подкрепить ходы победителя и сделать менее вероятными выбор ходов ведущих к поражению. REINFORCE именно об этом.
Однако, здесь есть одна проблема: не все ходы выполненные в ходе игры вносят равноценный вклад в достижение победы. Подкрепляя слабые ходы мы можем не только затянуть процесс обучения, но и научить модель плохому. Интуитивно понятно, что ход «переломивший игру», выполненный из проигрышного положения, намного ценнее обычного тихого хода из позиции, в которой игроку ничего не угрожает, но как это формализовать? Мне нравится метод «актор-критик», формирующий подкрепление в зависимости от оценки позиции, с точки зрения игрока. Откуда взять оценку? У нас есть нейросеть, вот пусть она и считает!
Здесь, помимо выхода политики, добавлен дополнительный выход оценки (для чего пришлось перейти от последовательного API к функциональному). Подкрепление каждого хода формируется как R-E (где R означает награду — 1 у победителя и -1 у проигравшего, а E — оценку текущей позиции с точки зрения игрока). Поскольку выход оценки — непрерывное вещественное значение, в качестве функции потерь берётся mse, а tanh используется как функция активации в последнем слое.
В этом месте начинаются проблемы
Прежде всего, два выхода модели вычисляются по разному и значения функций потерь на них вполне могут различаться на порядки (что для процесса обучения очень плохо). К сожалению, перенос масштабирующих коэффициентов из Tensorflow пока ещё только в планах. В моём случае, значения функций потерь на выходах различаются примерно в 4 раза и с этим можно жить. Второй момент более странный и выглядит более проблемным.
В своей книге, Max Pumperla и Kevin Ferguson утверждают, что при использовании в качестве функции потерь categoricalCrossentropy, изменение знака подкрепления приводит к обращению вектора градиента политики, что даёт возможность уменьшать вероятность не успешных ходов. К сожалению, как только я передаю на выход политики отрицательные значения подкрепления, всё сразу же ломается: значения функции потерь уходят в отрицательную область (чего быть не должно) и обучение уже больше никуда не идёт. Возможно, знающие люди подскажут в чём тут дело.
В своей книге, Max Pumperla и Kevin Ferguson утверждают, что при использовании в качестве функции потерь categoricalCrossentropy, изменение знака подкрепления приводит к обращению вектора градиента политики, что даёт возможность уменьшать вероятность не успешных ходов. К сожалению, как только я передаю на выход политики отрицательные значения подкрепления, всё сразу же ломается: значения функции потерь уходят в отрицательную область (чего быть не должно) и обучение уже больше никуда не идёт. Возможно, знающие люди подскажут в чём тут дело.
Настройка обучения с подкреплением имеет свою специфику. Как правило, такие модели обучаются «с нуля» и качество обучающих данных, по крайней мере в начале процесса обучения, далеко от идеального (а по правде сказать, близко к рандомному). По этой причине, к таким данным следует относиться с крайней осторожностью. Не следует использовать такие данные повторно, устанавливая количество эпох больше 1, а размер пакета следует выбирать побольше (например 1024), чтобы как-то сгладить возможные огрехи в обучающих данных.
Также, при обучении с подкреплением, не следует использовать адаптивные алгоритмы оптимизации, такие как adagrad или adam, отдав предпочтение старому доброму стохастическому градиенту. Скоростью обучения рекомендуется управлять вручную, задавая в начале малые значения (~0.001) и постепенно увеличивая по мере необходимости. Это может помочь не пролетать мимо минимума функции потерь в процессе обучения.
За 20 суток непрерывной работы HexAuto получил около 10000 качественных партий в Гекс (как я уже говорил, MCTS-бот работает не быстро). Осталось понять, что с этим делать. Можно было бы запустить дообучение исходной модели, но у меня возникла идея получше. Обучение новой модели «с нуля», на новых исходных данных, позволит оставить за скобками все те странные игры, попавшие в первоначальную обучающую выборку по недоразумению (без кропотливой ручной проверки более чем 15000 партий). Это данные, в которых я уверен.
Кроме того, помните я говорил, что обучение с учителем не позволяет научить модель играть лучше чем худший из игроков в обучающей выборке? Так оно и было бы, используй бот рекомендации нейросети напрямую, но в нашем случае основную работу выполняет MCTS, а нейросеть просто даёт ему подсказки. Из этого следует, что мы можем получить новый опыт из игр MCTS-бота и использовать его для лучшего обучения модели.
Как проходит обучение?
Поскольку данных мало и они качественные, используем их по полной, в большом количестве эпох. Размер пакета берётся большим (1024), чтобы сглаживать возможные огрехи в игре ботов. Обучение протекает довольно шустро:
Это обнадёживает. Ставим количество эпох побольше (100) и…
Так выглядит переобучение. До какого-то момента модель обучается прекрасно, но потом новые данные идут «мимо кассы». Как с этим бороться? Нам поможет прореживание! Добавляем дополнительные слои и запускаем процесс. Это медленнее (примерно в 2 раза), но результат выглядит обнадёживающе:
Похоже на то, что теперь дальнейшее обучение модели просто вопрос времени.
accuracy
loss
Это обнадёживает. Ставим количество эпох побольше (100) и…
accuracy
loss
Так выглядит переобучение. До какого-то момента модель обучается прекрасно, но потом новые данные идут «мимо кассы». Как с этим бороться? Нам поможет прореживание! Добавляем дополнительные слои и запускаем процесс. Это медленнее (примерно в 2 раза), но результат выглядит обнадёживающе:
accuracy
loss
Похоже на то, что теперь дальнейшее обучение модели просто вопрос времени.
Вы можете сами увидеть, насколько хорошо играет бот, зарегистрировавшись на DagazServer (регистрация бесплатная и не требует ввода персональных данных). Если же вариант с регистрацией вас решительно не устраивает, можно посмотреть на версию игры на GitHub Pages. Должен предупредить, что в этом случае взаимодействие с ботом более опосредованное и иногда «виснет» (перезагрузка страницы по F5 в таких случаях обычно помогает). Обратите внимание на подсветку рекомендуемых ходов на доске (это просто рекомендация модели, MCTS не задействован). На текущий момент, мне удаётся его обыгрывать (особенно когда я не зеваю), но я всерьёз рассчитываю на то, что дальнейшее обучение позволит значительно улучшить качество игры.
Update 17.11.2022
Вчерашний запуск показал не очень качественную игру бота против человека. По результатам разбора полётов ужесточил обработку первого хода и вернулся к одной из старых моделей.
Попутно выяснилось, что производительность бота на сервере (виртуалка) серьёзно уступает ПК на котором я отлаживаюсь.
Пришлось увеличить время обработки хода до 10 секунд, но всё равно заветные 10000 итераций не добираются даже ближе к концу игры (а они очень нужны в самом начале). Так что бот на сервере играет закономерно хуже. Есть ещё кое какие идеи по поводу последующего обучения модели, но это уже на следующей неделе, поскольку обучение занимает много времени и я могу этим заниматься только в выходные.
Локально она показала неплохую игру
> hex-bot-v2@1.0.0 start C:\Users\User\hex-bot-v2
> node index.js
INIT
{
id: 10604,
setup_required: true,
game_id: 29,
variant_id: 225,
ai_flags: null,
width: null,
height: null,
game: 'Hex',
filename: 'hex',
players_total: 2,
last_setup: '?turn=0;&setup=92/92/92/92/92/92/92/92/92/92/92-w',
is_dice: 0,
is_admin: false,
ai_timeout: 1000,
player_num: 1,
uid: 14954
}
[10604] fen = 92/92/92/92/92/92/92/92/92/92/92
move = g6, value=1000, time = 1
{
id: 10604,
setup_required: true,
game_id: 29,
variant_id: 225,
ai_flags: null,
width: null,
height: null,
game: 'Hex',
filename: 'hex',
players_total: 2,
last_setup: '?turn=1;&setup=92/92/92/92/92/6A4/92/92/92/92/92-b',
is_dice: 0,
is_admin: false,
ai_timeout: 1000,
player_num: 1,
uid: 14954,
time_limit: null,
additional_time: 0
}
[10604] fen = 92/92/92/92/92/5aA4/92/92/92/92/92
cpu
============================
Hi, looks like you are running TensorFlow.js in Node.js. To speed things up dramatically, install our node backend, visit https://github.com/tensorflow/tfjs-node for more details.
============================
Load time: 989
Predict time: 267
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . + + . . . .
. . . . . + . . . . .
. . . + + . . + . . .
. . . + + o * + . . .
. . + + + . . . . . .
. + . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
d7: n = 113, w = 56, p = 0.3562183678150177, e = 0
e7: n = 113, w = 66, p = 0.03258887678384781, e = 0
f9: n = 106, w = 61, p = 0.0000028124461550760316, e = 0
d6: n = 100, w = 56, p = 0.008620398119091988, e = 0
j2: n = 99, w = 56, p = 0.00024358583323191851, e = 0
c6: n = 96, w = 53, p = 0.0007067034021019936, e = 0
e5: n = 95, w = 50, p = 0.09140952676534653, e = 0
d8: n = 93, w = 51, p = 0.00036295480094850063, e = 0
b6: n = 89, w = 48, p = 0.000013703950571652967, e = 0
j11: n = 88, w = 47, p = 0.0000015722501984782866, e = 0
Time = 7070, N = 7500
move = e7, value=15.064658045593921, time = 7070
{
id: 10604,
setup_required: true,
game_id: 29,
variant_id: 225,
ai_flags: null,
width: null,
height: null,
game: 'Hex',
filename: 'hex',
players_total: 2,
last_setup: '?turn=1;&setup=92/92/92/92/92/5aA4/4A6/92/92/92/92-b',
is_dice: 0,
is_admin: false,
ai_timeout: 1000,
player_num: 1,
uid: 14954,
time_limit: null,
additional_time: 0
}
[10604] fen = 92/92/92/92/92/4bA4/4A6/92/92/92/92
Load time: 0
Predict time: 152
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . + . . + . .
. . . + . . . . . . .
. . . + + . . . . . .
. . . . o o * . . . .
. . + + * + + . . . .
. + . . . + . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
g5: n = 188, w = 121, p = 0.00007440061017405242, e = 0
f7: n = 156, w = 67, p = 0.9311296343803406, e = 0
b8: n = 138, w = 70, p = 0.3800925016403198, e = 0
f9: n = 132, w = 77, p = 1.770902713360556e-7, e = 0
a10: n = 126, w = 72, p = 9.020714486496217e-8, e = 0
f8: n = 122, w = 60, p = 0.29038721323013306, e = 0
d10: n = 120, w = 67, p = 0.0071227047592401505, e = 0
c8: n = 113, w = 62, p = 0.000010491111424926203, e = 0
d7: n = 111, w = 60, p = 0.0267222598195076, e = 0
i5: n = 110, w = 60, p = 4.7156991200836273e-8, e = 0
Time = 7074, N = 8900
move = g5, value=21.121222334569147, time = 7074
{
id: 10604,
setup_required: true,
game_id: 29,
variant_id: 225,
ai_flags: null,
width: null,
height: null,
game: 'Hex',
filename: 'hex',
players_total: 2,
last_setup: '?turn=1;&setup=92/92/92/92/6A4/4bA4/4A6/92/92/92/92-b',
is_dice: 0,
is_admin: false,
ai_timeout: 1000,
player_num: 1,
uid: 14954,
time_limit: null,
additional_time: 0
}
[10604] fen = 92/92/92/92/6A4/4bA4/4Aa5/92/92/92/92
Load time: 0
Predict time: 113
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . + . . . . .
. . . . + . * . . . .
. . . . o o * . . . .
. . . . * o + . . . .
. . . . . + . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
g7: n = 179, w = 91, p = 0.46867063641548157, e = 0
f4: n = 129, w = 64, p = 0.13096025586128235, e = 0
d6: n = 124, w = 64, p = 0.000011476244253572077, e = 0
g8: n = 124, w = 64, p = 0.000003983141141361557, e = 0
k2: n = 122, w = 63, p = 1.2536909821392328e-7, e = 0
i5: n = 120, w = 61, p = 1.782942149475275e-7, e = 0
b6: n = 118, w = 60, p = 8.086317393463105e-7, e = 0
g9: n = 118, w = 60, p = 2.03362304773691e-8, e = 0
h9: n = 117, w = 59, p = 6.810767505527338e-10, e = 0
f5: n = 110, w = 54, p = 0.000002063915189864929, e = 0
Time = 7039, N = 9200
move = g7, value=19.45440712965982, time = 7039
{
id: 10604,
setup_required: true,
game_id: 29,
variant_id: 225,
ai_flags: null,
width: null,
height: null,
game: 'Hex',
filename: 'hex',
players_total: 2,
last_setup: '?turn=1;&setup=92/92/92/92/6A4/4bA4/4AaA4/92/92/92/92-b',
is_dice: 0,
is_admin: false,
ai_timeout: 1000,
player_num: 1,
uid: 14954,
time_limit: null,
additional_time: 0
}
[10604] fen = 92/92/7a3/92/6A4/4bA4/4AaA4/92/92/92/92
Load time: 0
Predict time: 112
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . o . . .
. . . . . + . . . . .
. . . . . . * . . . .
. . . . o o * . . . .
. . . . * o * . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
f4: n = 232, w = 125, p = 0.999126136302948, e = 0
h7: n = 147, w = 87, p = 0.0007273855153471231, e = 0
d6: n = 135, w = 78, p = 5.328457675091158e-9, e = 0
g3: n = 134, w = 77, p = 2.233676710261534e-8, e = 0
i5: n = 130, w = 74, p = 8.75612613526755e-7, e = 0
j9: n = 122, w = 68, p = 2.209392824942258e-12, e = 0
k1: n = 122, w = 68, p = 3.030690365335431e-8, e = 0
d5: n = 121, w = 67, p = 8.176841959084413e-8, e = 0
c3: n = 116, w = 63, p = 2.543234423581166e-15, e = 0
i4: n = 116, w = 63, p = 4.464618896804495e-9, e = 0
Time = 7024, N = 9100
move = f4, value=25.491704208328755, time = 7024
{
id: 10604,
setup_required: true,
game_id: 29,
variant_id: 225,
ai_flags: null,
width: null,
height: null,
game: 'Hex',
filename: 'hex',
players_total: 2,
last_setup: '?turn=1;&setup=92/92/7a3/5A5/6A4/4bA4/4AaA4/92/92/92/92-b',
is_dice: 0,
is_admin: false,
ai_timeout: 1000,
player_num: 1,
uid: 14954,
time_limit: null,
additional_time: 0
}
[10604] fen = 92/92/6b3/5A5/6A4/4bA4/4AaA4/92/92/92/92
Load time: 0
Predict time: 195
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . + o o . . .
. . . . . * . . . . .
. . . . . . * . . . .
. . . . o o * . . . .
. . . . * o * . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
f3: n = 219, w = 128, p = 0.9999359846115112, e = 0
g2: n = 163, w = 110, p = 7.888054653903964e-9, e = 0
f9: n = 162, w = 109, p = 9.721892268999e-8, e = 0
h9: n = 127, w = 80, p = 1.6378491445034893e-12, e = 0
i4: n = 125, w = 78, p = 2.1828991739192283e-11, e = 0
c4: n = 114, w = 69, p = 2.1093462532206786e-9, e = 0
c9: n = 105, w = 62, p = 7.274028046566627e-9, e = 0
f10: n = 103, w = 60, p = 2.509963508146029e-7, e = 0
j1: n = 102, w = 59, p = 1.9311984900127754e-8, e = 0
e1: n = 101, w = 58, p = 1.8024677583827753e-10, e = 0
Time = 7059, N = 8500
move = f3, value=25.761675097047405, time = 7059
{
id: 10604,
setup_required: true,
game_id: 29,
variant_id: 225,
ai_flags: null,
width: null,
height: null,
game: 'Hex',
filename: 'hex',
players_total: 2,
last_setup: '?turn=1;&setup=92/92/5Ab3/5A5/6A4/4bA4/4AaA4/92/92/92/92-b',
is_dice: 0,
is_admin: false,
ai_timeout: 1000,
player_num: 1,
uid: 14954,
time_limit: null,
additional_time: 0
}
[10604] fen = 92/92/5Ab3/5Aa4/6A4/4bA4/4AaA4/92/92/92/92
Load time: 0
Predict time: 119
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . * o o . . .
. . . . . * o . . . .
. . . . . + * . . . .
. . . . o o * . . . .
. . . . * o * . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
f5: n = 264, w = 163, p = 1.8999639749526978, e = 0
h9: n = 158, w = 119, p = 5.8430742510336576e-15, e = 0
f9: n = 146, w = 108, p = 2.722197800508752e-9, e = 0
h8: n = 136, w = 99, p = 1.742388316960941e-10, e = 0
g2: n = 124, w = 88, p = 2.6496033145306797e-10, e = 0
c4: n = 115, w = 80, p = 1.9052490696225277e-9, e = 0
i10: n = 113, w = 78, p = 1.6652832067411312e-14, e = 0
j2: n = 109, w = 74, p = 4.1680041817926394e-7, e = 0
i9: n = 105, w = 71, p = 6.396081581039326e-13, e = 0
b7: n = 103, w = 69, p = 9.847889170799817e-10, e = 0
Time = 7036, N = 8700
move = f5, value=30.34134007585335, time = 7036
{
id: 10604,
setup_required: true,
game_id: 29,
variant_id: 225,
ai_flags: null,
width: null,
height: null,
game: 'Hex',
filename: 'hex',
players_total: 2,
last_setup: '?turn=1;&setup=92/92/5Ab3/5Aa4/5B4/4bA4/4AaA4/92/92/92/92-b',
is_dice: 0,
is_admin: false,
ai_timeout: 1000,
player_num: 1,
uid: 14954,
time_limit: null,
additional_time: 0
}
[10604] fen = 92/92/5Ab3/5Aa4/5B4/4bA4/4AaA4/92/5a5/92/92
Load time: 1
Predict time: 111
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . * o o . . .
. . . . . * o . . . .
. . . + . * * . . . .
. . . . o o * . . . .
. . . . * o * . . . .
. . . . . + . + + . .
. . . . . o + . . . .
. . . . . . . . . . .
. . . . . . . . . . .
h8: n = 247, w = 163, p = 0.776493489742279, e = 0
g9: n = 174, w = 121, p = 0.012051773257553577, e = 0
f8: n = 156, w = 105, p = 0.03498733788728714, e = 0
e8: n = 138, w = 91, p = 0.00007620630640303716, e = 0
g8: n = 138, w = 91, p = 0.0002636779972817749, e = 0
i8: n = 131, w = 81, p = 0.1347949057817459, e = 0
g2: n = 117, w = 73, p = 0.00012349066673777997, e = 0
h7: n = 113, w = 70, p = 0.00015255737525876611, e = 0
d7: n = 113, w = 70, p = 0.00024106141063384712, e = 0
j8: n = 111, w = 68, p = 0.00011995271052001044, e = 0
Time = 7056, N = 9100
move = h8, value=27.13987473903967, time = 7056
{
id: 10604,
setup_required: true,
game_id: 29,
variant_id: 225,
ai_flags: null,
width: null,
height: null,
game: 'Hex',
filename: 'hex',
players_total: 2,
last_setup: '?turn=1;&setup=92/92/5Ab3/5Aa4/5B4/4bA4/4AaA4/7A3/5a5/92/92-b',
is_dice: 0,
is_admin: false,
ai_timeout: 1000,
player_num: 1,
uid: 14954,
time_limit: null,
additional_time: 0
}
[10604] fen = 92/92/5Ab3/5Aa4/5B4/4bA4/4AaA4/7A3/5a2a2/92/92
Load time: 0
Predict time: 106
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . * o o . . .
. . . . . * o . . . .
. . . . . * * . . . .
. . . . o o * . . . .
. . . . * o * . . . .
. . . . + + . * . . .
. . . . + o . . o . .
. . . . . . + + . . .
. . . . . . . . . . .
g10: n = 460, w = 404, p = 0.3124961853027344, e = 0
f8: n = 294, w = 231, p = 0.5743585824966431, e = 0
h9: n = 155, w = 115, p = 0.0020819492638111115, e = 0
k8: n = 139, w = 101, p = 0.00010255465895170346, e = 0
k9: n = 125, w = 88, p = 0.000009723629773361608, e = 0
c9: n = 124, w = 87, p = 0.0001435191952623427, e = 0
g9: n = 123, w = 86, p = 0.0004532948660198599, e = 0
a8: n = 120, w = 83, p = 1.2418826145221828e-7, e = 0
c10: n = 115, w = 79, p = 0.0001548130385344848, e = 0
e2: n = 114, w = 78, p = 0.0000010005476269725477, e = 0
Time = 7025, N = 9100
move = g10, value=50.5438962751346, time = 7025
{
id: 10604,
setup_required: true,
game_id: 29,
variant_id: 225,
ai_flags: null,
width: null,
height: null,
game: 'Hex',
filename: 'hex',
players_total: 2,
last_setup: '?turn=1;&setup=92/92/5Ab3/5Aa4/5B4/4bA4/4AaA4/7A3/5a2a2/6A4/92-b',
is_dice: 0,
is_admin: false,
ai_timeout: 1000,
player_num: 1,
uid: 14954,
time_limit: null,
additional_time: 0
}
[10604] fen = 92/92/5Ab3/5Aa4/5B4/4bA4/4AaA4/7A3/5b1a2/6A4/92
Load time: 0
Predict time: 118
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . * o o . . .
. . . . . * o . . . .
. . . . . * * . . . .
. . . . o o * . . . .
. . . . * o * . . . .
. . . . . . . * . . .
. . . . . o o + o . .
. . . . . . * . . . .
. . . . . . . . . . .
h9: n = 316, w = 281, p = 1.899999976158142, e = 0
g2: n = 146, w = 138, p = 1.2555153801610747e-16, e = 0
f2: n = 146, w = 139, p = 1.4711345155709656e-19, e = 0
e2: n = 124, w = 114, p = 5.351740423408923e-22, e = 0
a10: n = 123, w = 113, p = 1.7834925973268616e-18, e = 0
g1: n = 123, w = 113, p = 1.412217530349207e-23, e = 0
d4: n = 123, w = 113, p = 2.3861010277243758e-20, e = 0
b7: n = 119, w = 108, p = 6.675623821627526e-18, e = 0
c3: n = 119, w = 108, p = 1.0351424215503468e-21, e = 0
e3: n = 115, w = 104, p = 1.7145580017148948e-20, e = 0
Time = 7069, N = 9400
move = h9, value=33.61344537815126, time = 7069
{
id: 10604,
setup_required: true,
game_id: 29,
variant_id: 225,
ai_flags: null,
width: null,
height: null,
game: 'Hex',
filename: 'hex',
players_total: 2,
last_setup: '?turn=1;&setup=92/92/5Ab3/5Aa4/5B4/4bA4/4AaA4/7A3/5bAa2/6A4/92-b',
is_dice: 0,
is_admin: false,
ai_timeout: 1000,
player_num: 1,
uid: 14954,
time_limit: null,
additional_time: 0
}
[10604] fen = 6a4/92/5Ab3/5Aa4/5B4/4bA4/4AaA4/7A3/5bAa2/6A4/92
Load time: 0
Predict time: 188
. . . . . . o . . . .
. . . . + . + . . . .
. . . . . * o o . . .
. . . . . * o . . . .
. . . . . * * . . . .
. . . . o o * . . . .
. . . . * o * . . . .
. . . . . . . * . . .
. . . . . o o * o . .
. . . . . . * . . . .
. . . . . . . . . . .
e2: n = 303, w = 298, p = 0.9087823033332825, e = 0
g2: n = 177, w = 173, p = 0.07272938638925552, e = 0
f2: n = 165, w = 162, p = 0.0044675408862531185, e = 0
h2: n = 145, w = 139, p = 0.0002212047402281314, e = 0
j3: n = 138, w = 131, p = 0.000039961047150427476, e = 0
c10: n = 118, w = 108, p = 4.582106694073218e-9, e = 0
h1: n = 116, w = 106, p = 0.00016876423615030944, e = 0
c2: n = 116, w = 106, p = 9.981785353829764e-8, e = 0
i4: n = 116, w = 106, p = 1.4992888708320606e-8, e = 0
c7: n = 116, w = 106, p = 4.5079733723696336e-8, e = 0
Time = 7016, N = 9600
move = e2, value=31.559212582022703, time = 7016
{
id: 10604,
setup_required: true,
game_id: 29,
variant_id: 225,
ai_flags: null,
width: null,
height: null,
game: 'Hex',
filename: 'hex',
players_total: 2,
last_setup: '?turn=1;&setup=6a4/4A6/5Ab3/5Aa4/5B4/4bA4/4AaA4/7A3/5bAa2/6A4/92-b',
is_dice: 0,
is_admin: false,
ai_timeout: 1000,
player_num: 1,
uid: 14954,
time_limit: null,
additional_time: 0
}
[10604] fen = 5b4/4A6/5Ab3/5Aa4/5B4/4bA4/4AaA4/7A3/5bAa2/6A4/92
Load time: 0
Predict time: 109
. . . . + o o . . . .
. . . . * . + . . . .
. . . . . * o o . . .
. . . . . * o . . . .
. . . . . * * . . . .
. . . . o o * . . . .
. . . . * o * . . . .
. . . . . + . * . . .
. . . . . o o * o . .
. . . . . . * . . . .
. . . . . . . . . . .
e1: n = 299, w = 291, p = 1.8437700271606445, e = 0
c6: n = 111, w = 110, p = 0.000030445729862549342, e = 0
g2: n = 111, w = 109, p = 0.03426429256796837, e = 0
g8: n = 110, w = 109, p = 7.1233769993739315e-9, e = 0
k9: n = 110, w = 109, p = 1.709794084092664e-8, e = 0
d7: n = 110, w = 109, p = 7.816795459802961e-7, e = 0
a11: n = 106, w = 104, p = 3.5467370707031876e-10, e = 0
e11: n = 106, w = 104, p = 0.00000770689166529337, e = 0
b10: n = 106, w = 104, p = 8.142529850374558e-8, e = 0
h4: n = 106, w = 104, p = 2.86959431911038e-11, e = 0
Time = 7001, N = 9900
move = e1, value=30.1989698010302, time = 7001
{
id: 10604,
setup_required: true,
game_id: 29,
variant_id: 225,
ai_flags: null,
width: null,
height: null,
game: 'Hex',
filename: 'hex',
players_total: 2,
last_setup: '?turn=1;&setup=4Ab4/4A6/5Ab3/5Aa4/5B4/4bA4/4AaA4/7A3/5bAa2/6A4/92-b',
is_dice: 0,
is_admin: false,
ai_timeout: 1000,
player_num: 1,
uid: 14954,
time_limit: null,
additional_time: 0
}
[10604] fen = 4Ab4/4Aa5/5Ab3/5Aa4/5B4/4bA4/4AaA4/7A3/5bAa2/6A4/92
Load time: 0
Predict time: 107
. . . . * o o . . . .
. . . . * o . . . . .
. . . . + * o o . . .
. . . . . * o . . . .
. . . . . * * . . . .
. . . . o o * . . . .
. . . . * o * . . . .
. . . . . . . * . . .
. . . . . o o * o . .
. . . . . . * . . . .
. . . . . . . . . . .
e3: n = 329, w = 324, p = 1.8999874591827393, e = 0
j6: n = 117, w = 116, p = 6.977174914213347e-13, e = 0
i1: n = 114, w = 112, p = 3.2668245886213754e-10, e = 0
a11: n = 112, w = 110, p = 8.904922928548004e-19, e = 0
h4: n = 112, w = 109, p = 1.3495988765630765e-15, e = 0
a3: n = 112, w = 110, p = 4.1308729774602034e-18, e = 0
h2: n = 112, w = 110, p = 1.8529665649080762e-11, e = 0
i6: n = 112, w = 110, p = 1.954497536038602e-10, e = 0
a6: n = 112, w = 110, p = 8.364533024551868e-13, e = 0
j3: n = 112, w = 110, p = 7.436654764214623e-11, e = 0
Time = 7020, N = 10000
move = e3, value=32.9, time = 7020
{
id: 10604,
setup_required: true,
game_id: 29,
variant_id: 225,
ai_flags: null,
width: null,
height: null,
game: 'Hex',
filename: 'hex',
players_total: 2,
last_setup: '?turn=1;&setup=4Ab4/4Aa5/4Bb3/5Aa4/5B4/4bA4/4AaA4/7A3/5bAa2/6A4/92-b',
is_dice: 0,
is_admin: false,
ai_timeout: 1000,
player_num: 1,
uid: 14954,
time_limit: null,
additional_time: 0
}
[10604] fen = 4Ab4/4Aa5/4Bb3/5Aa4/5B4/4bA4/4AaA4/6aA3/5bAa2/6A4/92
Load time: 0
Predict time: 106
. . . . * o o . . . .
. . . . * o + . . . .
. . . . * * o o . . .
. . . . . * o . . . .
. . . . . * * . . . .
. . . . o o * . . . .
. . . . * o * + . . .
. . . . . . o * . . .
. . . . . o o * o . .
. . . . . . * . . . .
. . . . . . . . . . .
h7: n = 330, w = 329, p = 1.7807644605636597, e = 0
j6: n = 118, w = 117, p = 3.947205584609037e-8, e = 0
d2: n = 118, w = 117, p = 3.888484201297615e-9, e = 0
c8: n = 118, w = 116, p = 3.167467355069675e-8, e = 0
b7: n = 118, w = 117, p = 2.261221654364931e-9, e = 0
f10: n = 118, w = 117, p = 2.9993076165052424e-13, e = 0
c5: n = 118, w = 117, p = 4.85928658422452e-12, e = 0
k4: n = 118, w = 117, p = 2.305140800462624e-11, e = 0
g11: n = 118, w = 117, p = 2.4010398647078546e-7, e = 0
a8: n = 118, w = 117, p = 9.024734771135808e-16, e = 0
Time = 6938, N = 10000
move = h7, value=33, time = 6938
{
id: 10604,
setup_required: true,
game_id: 29,
variant_id: 225,
ai_flags: null,
width: null,
height: null,
game: 'Hex',
filename: 'hex',
players_total: 2,
last_setup: '?turn=1;&setup=4Ab4/4Aa5/4Bb3/5Aa4/5B4/4bA4/4AaB3/6aA3/5bAa2/6A4/92-b',
is_dice: 0,
is_admin: false,
ai_timeout: 1000,
player_num: 1,
uid: 14954,
time_limit: null,
additional_time: 0
}
[10604] fen = 4Ab4/4Aa5/4Bb3/5Aa4/5B4/4bA4/4AaB3/6aA3/5bAa2/6A4/6a4
Load time: 0
Predict time: 105
. . . . * o o . . . .
. . . . * o + . . . .
. . . . * * o o . . .
. . . . . * o . . . .
. . . . . * * . . . .
. . . . o o * . . . .
. . . . * o * * . . .
. . . . . . o * . . .
. . . . . o o * o . .
. . . . . . * + . . .
. . . . . + o . . . .
f11: n = 246, w = 245, p = 1.163718342781067, e = 0
h10: n = 176, w = 175, p = 0.534814715385437, e = 0
g2: n = 124, w = 123, p = 0.12146802991628647, e = 0
j1: n = 108, w = 107, p = 0.002648537512868643, e = 0
i10: n = 108, w = 107, p = 0.0014305689837783575, e = 0
e10: n = 107, w = 106, p = 0.0000034792210499290377, e = 0
i11: n = 107, w = 106, p = 0.0000024592443423898658, e = 0
k3: n = 107, w = 106, p = 1.1634190855147608e-7, e = 0
d1: n = 107, w = 106, p = 0.000015162101590249222, e = 0
k1: n = 107, w = 106, p = 0.000004100490059499862, e = 0
Time = 6774, N = 10000
move = f11, value=24.6, time = 6774
Попутно выяснилось, что производительность бота на сервере (виртуалка) серьёзно уступает ПК на котором я отлаживаюсь.
Всё очень печально
info: 11:07:11 - [10607] fen = 92/92/92/6A4/2Aa2A4/2AaA2A3/a1Ab1A2a1/1AaAd3/1AaBaA4/1a9/92
info: 11:07:21 - a11: n = 1716, w = 974, p = 0.03789157420396805, e = 0
info: 11:07:21 - e3: n = 152, w = 23, p = 0.7905672788619995, e = 0
info: 11:07:21 - a10: n = 131, w = 37, p = 0.0037098501343280077, e = 0
info: 11:07:21 - k7: n = 125, w = 34, p = 0.0031722544226795435, e = 0
info: 11:07:21 - i7: n = 101, w = 23, p = 0.0003447399358265102, e = 0
info: 11:07:21 - c1: n = 92, w = 19, p = 4.2609440242813434e-7, e = 0
info: 11:07:21 - i8: n = 89, w = 17, p = 0.019992226734757423, e = 0
info: 11:07:21 - b5: n = 85, w = 16, p = 0.00009703390969661996, e = 0
info: 11:07:21 - j10: n = 85, w = 16, p = 0.00016607441648375243, e = 0
info: 11:07:21 - a1: n = 78, w = 13, p = 2.968519652313262e-7, e = 0
info: 11:07:21 - Time = 10064, N = 7600
info: 11:07:21 - move = a11, value=225.75976845151953, time = 10064
info: 11:07:29 - [10607] fen = 92/92/92/6A4/2Aa2A4/2AaA2A3/a1Ab1A2a1/1AaAd3/1AaBaA4/b9/A91
info: 11:07:39 - e3: n = 143, w = 4, p = 0.7782242894172668, e = 0
info: 11:07:39 - i7: n = 122, w = 20, p = 0.00003623754673753865, e = 0
info: 11:07:39 - i8: n = 117, w = 17, p = 0.032243840396404266, e = 0
info: 11:07:39 - f7: n = 114, w = 17, p = 7.779815405228874e-7, e = 0
info: 11:07:39 - k7: n = 114, w = 17, p = 0.00437212735414505, e = 0
info: 11:07:39 - j3: n = 108, w = 15, p = 0.000016538942873012275, e = 0
info: 11:07:39 - j5: n = 103, w = 13, p = 0.000005267845153866801, e = 0
info: 11:07:39 - i10: n = 103, w = 13, p = 0.0000021333116819732822, e = 0
info: 11:07:39 - k2: n = 103, w = 13, p = 1.892011880499922e-7, e = 0
info: 11:07:39 - i9: n = 100, w = 12, p = 0.0028137783519923687, e = 0
info: 11:07:39 - Time = 10051, N = 7600
info: 11:07:39 - move = i7, value=16.050519668464677, time = 10051
info: 11:07:54 - [10607] fen = 92/92/92/6A4/2Aa2A4/2AaA2A3/a1Ab1A1Aa1/1AaAe2/1AaBaA4/b9/A91
info: 11:08:04 - e5: n = 119, w = 1, p = 0.40592119097709656, e = 0
info: 11:08:04 - k6: n = 106, w = 9, p = 0.0023655954282730818, e = 0
info: 11:08:04 - b3: n = 92, w = 5, p = 9.913237590808421e-7, e = 0
info: 11:08:04 - e3: n = 91, w = 0, p = 0.15580372512340546, e = 0
info: 11:08:04 - k7: n = 89, w = 4, p = 0.00490249739959836, e = 0
info: 11:08:04 - c11: n = 89, w = 4, p = 0.0018651771824806929, e = 0
info: 11:08:04 - h11: n = 88, w = 4, p = 0.000028602476959349588, e = 0
info: 11:08:04 - j6: n = 85, w = 3, p = 0.0007209799368865788, e = 0
info: 11:08:04 - h4: n = 85, w = 3, p = 0.0009782741544768214, e = 0
info: 11:08:04 - b2: n = 85, w = 3, p = 0.0000020216734810674097, e = 0
info: 11:08:04 - Time = 10095, N = 7000
Пришлось увеличить время обработки хода до 10 секунд, но всё равно заветные 10000 итераций не добираются даже ближе к концу игры (а они очень нужны в самом начале). Так что бот на сервере играет закономерно хуже. Есть ещё кое какие идеи по поводу последующего обучения модели, но это уже на следующей неделе, поскольку обучение занимает много времени и я могу этим заниматься только в выходные.
Комментарии (10)
celen
16.11.2022 12:59Не понимаю, куда в задачке Брауна сходили черные ходом 14 и почему бы им не сходить этим ходом на B7, не дав белым сделать победный 15-ый ход на картинке. Понятно, что после 14:B7 никакие 15:B8 белым завершить цепочку уже не помогут.
adeshere
16.11.2022 16:18+2Мы в школьное время (1970-е) тоже изобрели игру с очень похожими правилами, причем, как мне кажется, независимо от Хейна и Нэша. Называется "удержание плазмы". Игра идет на квадратном поле, и первый игрок должен соединить центр квадрата с любой из стенок. Первый игрок начинает с центра и ставит один камень за свой полуход, а второй игрок ставит два камня за полуход. Прикол нашей игры был в иллюзии тривиальности оптимальной тактики (которая на деле оказывалась достаточно многослойной). Обычно после объяснения правил у новичка создавалось впечатление что белые легко выигрывают. Но... начиналась игра, и он без вариантов проигрывал. Подглядев тактику черных, новичок играет вторую партию черными, будучи уверен в легкой победе... и снова без вариантов проигрывает! Уверенный, что теперь-то он понял, как надо правильно играть белыми, новичок снова меняет цвет... и еще раз проигрывает без вариантов. В зависимости от сообразительности новичка, опытный партнер мог выиграть четыре-пять раз, пока наконец новичку открывался главный секрет игры - "ход конем".
Вообще, у нас в компании юных наукоградцев таких самопальных "игр на клетчатой бумаге" было в то время десятка два - как своих, так и творчески переработанных "гостевых". Даже одно время возникла идея собрать их все в одной книжке и опубликовать. Но потом появились компьютерные игрушки, и идея стала неактуальной. Хотя, как неожиданно выяснилось несколько лет назад, в Лабиринт некоторые продвинутые школьники играют до сих пор!
Aniro
Что-то оно совсем странно играет:
красный я, первый ход B2 чтобы дать небольшую фору, потом тупо по прямой
GlukKazan Автор
Это у него бывает, да.