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

Minimax бот

Ок, а третий элемент? — здесь чуть сложнее. Это «веса», на самом начальном этапе (в дальнейшем могут быть переопределены) присваиваемые ходам. Что является предварительной подготовкой анализа, выполняемого нейронной сетью непосредственно перед принятием решения о выборе хода. За основу берем простейшую логику: итоговые выигрыш / ничья / проигрыш соответствуют 0.3 / 0.2 / 0.1:

Забегая чуть вперед, скажу, что на данном этапе развития кода я уже не могу обыграть свою программу, хотя играю очень внимательно; любую невнимательность программка тут же обернет в свою пользу, и игра закончится не вничью, как следовало б ожидать, учитывая, что AI играет вторым номером, а — моим проигрышем. Правда, здесь многое зависит от сформированного в самом начале игры csv-файла, содержащего подробный лог 50К рандомно сыгранных (даже на слабом ПК, думаю, это займет не более пары минут) партий.

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

научно-исследовательская работа на тему «искусственный интеллект» автор: Батятин Максим (DevMule) github: https://github.com/DevMule/tick-tack-toe-ai цель работы: исследовать процессы проектирования и создания автоматических систем для решения конкретных задач Я пытался выбрать для проекта простую, знакомую каждому основу что позволит мне, разрабатывая ботов, долгое время не доходить до состояния нераспутываемого хаоса. Мой выбор пал на древнюю игру — «херики-оники». Прежде чем начать разрабатывать ботов, необходимо создать основу для игры.

«Мозг» такого бота должен состоять из сети послойно соединённых между собой нейронов. Каждый нейрон имеет коэффициент веса для каждого входящего сигнала (красный на картинке), плюс общее значение сдвига — bias (зелёный на картинке). Но т.к. сигнал нейрона должен иметь значение от 0 до 1, то после общее значение нейрона проходит через функцию сигмоиды (желтая). Bias сдесь — своеобразный «нормализатор» значения. Для нейрона был создан класс Neuron У класса Neuron реализован метод рассчёта сигнала — Neuron.feedforward() , который выполняет вышеуказанные рассчёты и возвращает значение.

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

Шаг №1 Нейроны и веса

Структура моей нейросети будет трёхслойной: Первый слой — входные узлы — их количество равно количеству ячеек в игровом поле. Т.к. ранее я реализовал доску таким образом, что технически в ячейках содержаться цифры, значения ячеек будем сразу передавать во входные узлы. Второй слой — скрытый — размер такого слоя может быть каким угодно. Семантика этих узлов максимально абстрактна, иными словами каждый из этих узлов несёт в себе какой-то конкретный смысл, но никто не может знать какой именно 🙂 Количество скрытых узлов подбирается «на ощупь». Третий слой — выходные узлы — Их количество в моём случае тоже будет равно количеству ячеек в игровом поле, а их значения будут представлять из себя «вес» пользы каждого хода. Сам выбор хода я реализовал как рандомный выбор с шансом, равным для каждого варианта соотношению: (вес варианта / суммарный вес всех вариантов) UPD 18.01.2020: Выбирается ход с наибольшим значением, это даёт бо́льшую гибкость при обучении — достаточно будет немного изменить вес нейрона чтобы получить нужное значение при этом сильно не меняя веса для других нейронов. Нейроны объединяются в сеть при инициализации класса NeuralNetworkBot . Отлично! Нейросеть готова и при правильных весах и сдвигах в каждом нейроне, она будет выдавать наиболее оптимальный путь. Осталось дело за малым — написать функцию тренировки сети.

Здесь делаем паузу, сходу наблюдая насмешливую ухмылку читателя блога: «Нейронная сеть и Tic Tac Toe? НАФИГА??» Не торопитесь. Автор не говорил, что его целью является повтор того или иного из сотни готовых решений AI для игры в крестики-нолики, чьи разнообразные клоны на всех живых и мертвых языках программирования исчисляются на гитхабе, вероятно, уже тысячами. Нет, это было бы скучно; задача иная — положить перед собой чистый лист бумаги (хотя бы и бумаги электронной) и написать. написать вот так, как увиделось. Поверьте, абсолютно сознательно не искал и не читал в Сети описаний выигрышных стратегий Tic Tac Toe, хотя подобного рода алгоритмы подробно описаны и существуют очень давно, применение их не представляет сложности. Но нет, мы не ищем легких путей.

К слову сказать, на страничке ruby-fann, рубиновой обертки FANN, которую мы будем использовать для построения нейронной сети — в качестве примера приведена ссылка на аналогичное (впрочем, не анализировал) приложение: «a sample project using RubyFann to play tic-tac-toe». Так что. why not? Пусть себе критики потерпят. А мы тем временем приступим.

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

Второе отступление, еще одна ремарка. Когда-то давно прочел описание интересной интермедии, обладающей свойствами как математического фокуса, так и эстрадного номера. Суть заключалась в том, что фокусник, предложивший зрителю задумать число, получает сведения о задуманном — исподволь, как бы между строк. Скажем, реакция зрителя на предложение свершить с задуманным числом ту или иную математическую операцию — умножение, деление, что-то еще — способна предоставить внимательному наблюдателю некую информацию, о чем сам зритель даже не догадывается: время, необходимое для умножения, случайные вопросы — «а что мне делать с дробной частью?», «не делится!», «а если меньше ноля?» и иные реплики — в итоге дают возможность фокуснику продемонстрировать «чтение мыслей», полностью внезапно для зрительного зала сообщив задуманную цифру. Воспоминание именно об этом забавном и многозначительном трюке вертелось в голове, когда продумывал логику AI для игры в крестики-нолики. сейчас объясню.

Для начала необходимо понять суть тренировки. Какие именно процессы должны происходить при тренировке сети? Какие данные необходимы при этом? Для тренировки необходимы существующие данные с некоторой оценкой ходов. Например: Имея на руках конкретные значения для входных и выходных нейронов, можно посчитать изменения для всех весов и сдвигов, необходимые для лучшего соответствия данным выходам. В этой части очень много высшей математики, но основная теория разжёвана в этом туториале. В NeuralNetworkBot тренировка происходит по вызову функции NeuralNetworkBot.train(inputs, outputs) вызывается после завершения игры, в процессе чего бот учится играть как победитель и отучивается играть как проигравший. UPD 19.01.2020: Заметил что эта функция переписывает веса не только последних ходов, но и первых, что нехорошо, потому что бот ходит так, как считает правильным и постоянное переписывание «правильного» опыта в итоге затянет обучение в разы, потому сделал так, что чем ближе состояние истории игры к концу, тем сильнее коэффициент изменения весов. Для набора опыта создал специальный файл, в котором нейросеть играет сама с собой. Переменная epochs , которую я реализовал внутри бота теперь не нужна, так как её заменяет количество игр, в которые играет бот.

Третья (и последняя) ремарка. Логику AI, представляющую из себя эксклюзив, можно в некоторой степени считать ответом автора одному из его старых приятелей, упавшему сейчас в болото нигилизма и солипсизма. Кто не в курсе, о чем речь, погуглите эти два термина; все чаще и чаще встречаю разнообразные проявления этой заразной, как ковид, болезни умонастроения — в среде моих соотечественников. Подробнее здесь. Если вкратце — «мир без правил, все бессмысленно, все вокруг врут, и те правы и эти», etc. Припомните нечто подобное в «Тени» Евгения Шварца. А, возможно, сумеете провести аналогию и с персонажем «Собачьего сердца»?

Более комплексная машина, но тоже представляет из себя только расширение метода совершения хода Суть его содержания понятна уже из названия: Он строит всё дерево возможных ходов и выбирает из них самый ближайший ход для победы или, если победа невозможна, для ничьи. Его победить довольно сложно, однако возможно, расставляя подобные ловушки: Хотя, как понятно из скриншота, minimax бот сам тоже умеет их расставлять 🙂 Суть минимакс алгоритма для игры в крестики-нолики: Корневым узлом является состояние игры вданный момент. Бот рекурсивно строит дерево с узлами — возможными исходами игры для каждого хода. Если состояние игры для узла завершённое — есть победитель или объявлена ничья, то узел является терминальным — он имеет своё значение по умолчанию. Значение терминального узла зависит от состояния игры: сходивший выиграл = 1, никто не выиграл = 0. Далее, при каждом шаге обратной рекурсии, неретминальные узлы приобретают своё значение — если учитывается ход бота, то берётся максимальное из значений дочерних узлов, если ход врага, то минимальное. При каждом шаге обратной рекурсии, значения узлов умножаются на «-1», т.к. игроки меняются поочерёдно. Бот в приоритете выбирает ход с максимальным значением