Sign in

Зарегистрируйтесь, чтобы стать полноправным участником сообщества Masterpro.ws.

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

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

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

 

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

 

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

К слову сказать, на страничке 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 умеет вытащить из хаоса логику и выигрышную стратегию.

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

 

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

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

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

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

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

  • serge Кажется, вы попытались реанимировать обсуждение очень старого материала, В. Как утверждает Википедия, Adbrite закрылся в 2013 году, и я не…

    Пятница, 16 октября 2020

    Опубликовано в: Контекстная реклама AdBrite
  • В. Возникло два вопроса. Здравствуйте. 1й . Adbrite присылает чек? Сюда , в Россию? И что разве наши банки примут чек,это…

    Пятница, 16 октября 2020

    Опубликовано в: Контекстная реклама AdBrite
  • Aleksej Попробуйте так: gem uninstall grpc gem install grpc -v 1.31.1

    Среда, 14 октября 2020

    Опубликовано в: Google-Cloud-Text-To-Speech-Ruby-CLI-App
  • Андрис У меня программа падает сразу после запуска, аварийный останов / дамп сбрасывается на диск. 'lib/gapic/grpc/service_stub.rb:73: [BUG] Illegal instruction' и так…

    Среда, 14 октября 2020

    Опубликовано в: Google-Cloud-Text-To-Speech-Ruby-CLI-App
  • Aleksej Думаю, воскреснет... аккурат первого числа следующего месяца... это, знаете ли, как в одной очень старой книжке, "не ищите живого среди…

    Четверг, 27 августа 2020

    Опубликовано в: API HeadHunter: скрипт для обновления резюме