Пятница, 13 ноября 2020 02:50

Нейронная сеть для игры в крестики-нолики

Оцените материал
(5 голосов)

Сегодня - подробный, с примерами кода и живой демкой (все честно) рассказ о кодинге программы, имитирующей работу современных Artificial Intelligence, заточенных под процесс той или иной игры в качестве виртуального партнера и соперника.

Написанное на ruby приложение для игры в крестики-нолики использует для поиска оптимальных ходов игры нейронную сеть на основе ruby-fann.

 

Нейронная сеть для игры в крестики-нолики
Нейронная сеть для игры в крестики-нолики

 

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

 

Build Your Own Tic-Tac-Toe Robot. Article on Medium.com.

 

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

 

Увидеть на гитхабе.

 

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

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

 

Примечание: если вам удалось обыграть AI - это явно нештатная ситуация. Игра будет остановлена и программа автоматически пересоздаст csv-файл.

 

Что же это за лог такой? Никаких секретов, взгляните, вот несколько его строк, полностью отражающих ход одной из игр:

 

9,"[1, 2, 3, 4, 5, 6, 7, 8, 9]",0.3,0,X,3,7
6,"[1, 2, 3, 4, 5, 6, 7, 8, :X]",0.1,1,O,3,7
1,"[1, 2, 3, 4, 5, :O, 7, 8, :X]",0.3,2,X,3,7
2,"[:X, 2, 3, 4, 5, :O, 7, 8, :X]",0.1,3,O,3,7
8,"[:X, :O, 3, 4, 5, :O, 7, 8, :X]",0.3,4,X,3,7
3,"[:X, :O, 3, 4, 5, :O, 7, :X, :X]",0.1,5,O,3,7
7,"[:X, :O, :O, 4, 5, :O, 7, :X, :X]",0.3,6,X,3,7

 

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

 

Tic-Tac-Toe with a Neural Network
Tic-Tac-Toe with a Neural Network

 

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

 

  prioritization = []
  game.players_move_order.map do |i|
    prioritization << if i == game.check
                        0.3
                      elsif game.check == 'draw'
                        0.2
                      else
                        0.1
                      end
  end

 

Хм, а вот теперь подумайте и скажите. Какой ход в любой момент игровой ситуации на поле 3x3, используемом для игры в крестики-нолики, являлся бы для вас безусловно оптимальным? Или, иными словами, если у вас перед глазами лог игры, что именно вам необходимо, чтобы, задержав взгляд на строчке, описывающей очередной ход, и не читая дальше - уверенно заявить, что в данной ситуации этот ход наилучший? Поставьте себя на место AI, вся "интеллектуальная мощь" которого заключена в нескольких коротких скриптах; здесь необходимо что-то совсем простое и безошибочное, без долгих логических рассуждений и необходимости просчитывать на несколько ходов вперед.

Все не просто, а очень просто: если ход последний, он - наилучший. Вот вам и вся логика:

 

        if row[6].to_i - row[3].to_i == 1
            x_data.push([row[0].to_i])
            y_data.push([1]) # Присваиваем высший приоритет, т.е. максимально возможный вес, переопределяя начальный.
        end

 

А - худший ваш ход? - если ход предпоследний, т.е. выигрывает ваш противник. Согласны? Причем предпишем нашему AI следующую логику: если в числе ходов десятков тысяч сыгранных рандомно партий отыщется для текущей позиции хотя бы один, подпадающий под обозначенную таким образом градацию "наилучший" - все логические цепочки разом окончены, реализуем один-единственный этот ход, заканчивающий партию выигрышем. Аналогично, худший ход можно сразу же исключить из массива возможных, избавив нейронную сеть от лишнего труда. Не будем забывать, что лог и статистика игр, от которых придется отталкиваться AI - созданы полностью рандомно, и это очень шаткий фундамент, согласитесь, т.к. два виртуальных игрока при первом запуске приложения делают ходы вслепую, не имея никаких навыков. Обычно для обучения такого рода используется уже умеющая играть сетка, и результаты в этом случае анализировать проще. А здесь... попытайтесь провести аналогию с описанным выше математическим фокусом: нам с вами придется крайне внимательно "читать между строк", разрабатывая схему работы AI.

 

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

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

А уж нам с вами, хм... что бы там ни было, сам Бог велел.

 

Ну вот, начало положено. А дальше... будем посмотреть.

Продолжение материала.

Последнее изменениеПонедельник, 22 мая 2023 20:08

3 комментарии

  • Комментировать Aleksej Воскресенье, 05 февраля 2023 18:15 написал Aleksej

    Новая версия AI играет более уверенно и стабильно, рекомендую. https://masterpro.ws/tic-tac-toe-with-neural-network-resurrections

  • Комментировать Aleksej Суббота, 05 декабря 2020 14:41 написал Aleksej

    IvankEn, вы сделали скороспелый и оттого заведомо неверный вывод: ошибка заключена в использовании слова "стабильно". Попросту переформируйте csv-файл, выигрыши прекратятся, вот вам и вся стабильность. Повторюсь, в основе логики AI здесь - история сыгранных партий, а она способна разниться. В том и суть (или, вернее сказать, юмор) данной реализации - в попытке сымитировать основанную на эмпирическом опыте логику человека.

  • Комментировать IvankEn Суббота, 05 декабря 2020 05:55 написал IvankEn

    5 2 3 7 -- последовательность команд, при которой человек стабильно обыгрывает ИИ

Оставить комментарий

Добавьте ваш комментарий

Poker onRails

Text To Speech

Tic-Tac-Toe with a Neural Network

Комментарии в блоге