Написанное на 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

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

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

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

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