Artificial Intelligence, герой нашего времени. Этюд

Хм. Один из пунктов, регламентирующих действия модераторов на Хабре, сформулирован следующим образом: не надо пропускать статьи, слабо относящиеся к IT-тематике или не относящиеся к ней вовсе. Что сходу заставило автора призадуматься, а имеет ли прямое отношение к "IT-тематике" его пост, повествующий о некоторых этапах программирования забавного и увлекательного своего pet-проекта, несложного AI, выстраивающего нейронную сеть на основе ruby-обертки FANN для игры в крестики-нолики? Вопрос не содержит скрытого кокетства, ведь описанию логики программного кода в моем рассказе предназначено далеко не первостепенное значение. "Да это злая ирония!" – скажете вы. – Не знаю.

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

Итак, с места в карьер... после первого запуска программа начинает процесс самообучения, проигрывая сама с собой несколько десятков (минута - две максимум) тысяч партий (число, понятное дело, доступно для редактирования в конфиге; учитывая описываемый далее не вполне обычный алгоритм, положенный в основу логики этого AI - эксперименты такого рода также способны предоставить интересный материал для умозаключений). Здесь имитируется процесс обучения, свойственный многим другим Artificial Intelligence, с той лишь разницей, что оба "игрока" в равной степени играть не умеют, делая абсолютно рандомные ходы. Но правила игры действуют: если случайный ход не соответствует, программа обязана переходить, соответственно и выигрыш достанется той стороне, которая выиграет. Все честно: никаких подчисток и хаков, скрытых предпочтений, никаких тебе фейковых допинг-проб, зачастую в реальной жизни опрокидывающих результаты спортивных игр.

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

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

Если есть на Хабре парочка-другая читателей, которым психология ближе (я не про эйчаров), нежели программирование - сказанное легко облечется для них в канву профессиональной терминологии. Но описываемый мной психологический сценарий - крайность... частные случаи которого, менее заметные и разительные - встречаются, на мой субъективный взгляд, очень часто.

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

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

Хм, "и очень даже просто". (с) Если в логе случайно отыгранных игр присутствует хотя бы одна запись, где ход является последним, он в данной ситуации - наилучший. Не правда ли? Вот вам и вся логика, на основе которой начинаем формировать веса нейронной сети:

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

А как отыскать и исключить худший из возможных ходов? - также несложно. Если ход предпоследний, т.е. выигрывает ваш противник. Возражений нет?

Внезапно, в самый разгар работы над Tic Tac Toe AI with Neural Network пазл сложился (это я уже не о кодинге). Разгадка оказалась удручающе простой, но путь к ней – длинен и непрост: суть в том, что ни малейших попыток понимания в данном случае – как и в случаях иных – не было у моего знакомого и в помине. Странный объект моих отнюдь непрограммистских изысков жил в собственном мире, будто в бункере, видя во внешних объектах лишь проекции, разнообразные и разрозненные частички самого себя.

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

Поясню. “Понимание"... скажите, как вы понимаете этот термин? – в целях экономии времени приведу краткую, в рамках википедии, формулировку: “универсальная операция мышления, связанная с усвоением нового содержания, включением его в систему устоявшихся идей и представлений”. Ирония ситуации в том, что “нового содержания” у моего приятеля не было и быть не могло; нет для него никаких внешних объектов, которые возможно было бы постигать и далее “включать в систему идей и представлений”. Существует только он один или, вернее сказать, он в центре; все остальное вокруг представляется невзрачными тенями, проекциями тех или иных его аффектов. Звучит абсурдно, но, увидев на столичной улице очередную автомобильную пробку, забитую отнюдь не бюджетными авто, персонаж моих психоаналитических исследований неизменно приходил к выводу о том, что экономического кризиса в стране нет, и быть, в силу им увиденного, не может: никакой статистики или аналитики не существует, “для меня есть только то, что я вижу или могу потрогать”.

Возвращаемся к коду. К сожалению, дальше все несколько сложнее, чем то, с чего начали. Чтобы не увеличивать количество рандомных партий, служащих материалом для анализа в ходе игры, и не слишком увлекаться логической эквилибристикой на пустом месте - нам приходится создать парочку костылей, призванных помогать нейронной сети определять веса для ряда игровых ситуаций... в качестве оправдания, таким образом - соображение, что, вытаскивая самого себя за косичку из болота, Мюнхгаузен ведь обладал знаниями и эмпирическим опытом взрослого человека.

Немалую опасность для живущего в мире иллюзорной Матрицы виртуального игрока в крестики-нолики представляют вилки (просчитывать ситуацию на доске хотя бы на один - два хода вперед явно не наш life style). Что же, поиском вилок сейчас и попробуем заняться:

  WINNING_TRIADS = [
    [0, 1, 2],
    [3, 4, 5],
    [6, 7, 8],
    [0, 3, 6],
    [1, 4, 7],
    [2, 5, 8],
    [6, 4, 2],
    [0, 4, 8]
  ].freeze

Далее, при формировании csv-лога ходов, ищем:

  def fork?
    WINNING_TRIADS.select do |x|
      @board[x[0]] == @board[x[1]] && @board[x[2]].class != @board[x[0]].class &&
        place_x?(x[0]) ||
        @board[x[1]] == @board[x[2]] && @board[x[0]].class != @board[x[2]].class &&
          place_x?(x[1]) ||
        @board[x[0]] == @board[x[2]] && @board[x[1]].class != @board[x[2]].class &&
          place_x?(x[0])
    end
  end

Таким образом, если комбинация найдена два раза...

  if @game.fork?.size > 1

...вилка найдена.

Ок, работает. Хотя данный способ не учитывает следующего обстоятельства: вполне возможно, ваш ход приводит к возможности вилки лишь условно, а на практике противник вынужден сделать совсем иной ход, дабы не позволить вам следующим ходом выиграть. Что же, это решаемо.

Определим ряд потенциально опасных ситуаций:

  DANGEROUS_SITUATIONS_1 = [
    [6, 4, 2],
    [0, 4, 8]
  ].freeze

  DANGEROUS_SITUATIONS_2 = [
    [0, 4, 7],
    [0, 4, 5],
    [2, 4, 3],
    [2, 4, 7],
    [3, 4, 8],
    [1, 4, 8],
    [1, 4, 6],
    [5, 4, 6]
  ].freeze

  def fork_danger_1?
    DANGEROUS_SITUATIONS_1.detect do |x|
      @board[x[0]] == @board[x[2]] &&
        @board[x[0]] != @board[x[1]]
    end
  end
  
  def fork_danger_2?
    DANGEROUS_SITUATIONS_2.detect do |x|
      @board[x[0]] == @board[x[2]] &&
        @board[x[0]] != @board[x[1]]
    end
  end

  def fork_danger_3?
    DANGEROUS_SITUATIONS_1.detect do |x|
      @board[x[0]] != @board[x[2]] &&
        @board[x[1]] == @board[x[2]]
    end
  end

И, соответственно, создадим три массива, в которые, при анализе ситуации на доске, AI станет помещать удовлетворяющие условиям ходы: 1. однозначно неприемлемые, 2. потенциально приводящие к вилке и 3. атакующие (т.е. те, в силу которых противник вынужден, во избежание немедленного проигрыша, реализовать единственно возможный для него ход). Разумеется, массивы будут иногда пересекаться, учтем это при построении логики игры. Кроме того, последнее слово за Neural Network.

  array_of_games.each do |row|
      row.each do |e|
        next unless e == current_position

        if row[6].to_i - row[3].to_i == 2 && row[4] == 'O' && row[2].to_f != 0.2
          unacceptable_moves_array << row[0]
        # Find moves that inevitably lead to a fork:
        elsif fork_danger_1 && row[3].to_i == 3 && row[0].to_i.odd?
          unacceptable_moves_array << row[0]
        elsif (fork_danger_2 || fork_danger_3) && row[3].to_i == 3 && row[0].to_i.even?
          unacceptable_moves_array << row[0]
        end
        next if row[5].nil?

        # Find moves that may lead to a fork:
        array_of_moves_to_fork << row[0] if row[3].to_i == row[5].to_i
        # Find attacking moves:
        attack_moves_array << row[0] if row[3].to_i == row[5].to_i && row[6].to_i < 7
      end
    end

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

 array_of_games.each do |row|
      row.each do |e|
        next unless e == current_position

        next if arrays[0].include?(row[0])

        unless arrays[1].include?(row[0]) && !arrays[2].include?(row[0])
          if row[6].to_i - row[3].to_i == 1
            x_data.push([row[0].to_i])
            y_data.push([1])
          elsif row[6].to_i - row[3].to_i == 3
            if arrays[2].include?(row[0])
              x_data.push([row[0].to_i])
              y_data.push([0.9])
            elsif arrays[1].include?(row[0])
              x_data.push([row[0].to_i])
              y_data.push([0.3])
            end
          else
            x_data.push([row[0].to_i])
            y_data.push([row[2].to_f])
          end
        end
      end

Сухой остаток скармливаем нейронке:

    data = nn_data(board, fork_danger_1, fork_danger_2, fork_danger_3, array_of_games)
    fann_results_array = []
      train = RubyFann::TrainData.new(inputs: data[0], desired_outputs: data[1])
      model = RubyFann::Standard.new(
        num_inputs: 1,
        hidden_neurons: [4],
        num_outputs: 1
      )
      model.train_on_data(train, 5000, 500, 0.01)
      data[0].flatten.each do |i|
        fann_results_array << model.run([i])
      end
    result = data[0][fann_results_array.index(fann_results_array.max)]

Интересная деталь: в одной и той же игровой ситуации на доске (и с одним и тем же csv-файлом) этот Neural Network способен выдавать различные варианты ходов.

В итоге - у вас максимум ничья, минимум - проигрыш, выиграть не получится. Разве что подведет рандомно сгенерированный csv-файл (такое случается, но нечасто), который в редком случае вашего выигрыша оптимально пересоздать. Впрочем, описанная ревизия кода - или не только кода - может статься, вовсе не окончательная, итоги подводить рано.

P.S. Описанный код всегда доступен полностью (а не фрагментарно, как диктует формат статьи) в моем гитхабе, разумеется, любой желающий может сделать git clone и поэкспериментировать с кодом, ну или просто поиграть. Я не сторонник запуска ruby-application под виндой, это очень не лучшая идея, но в данном случае работать будет, попробовал. Возможно, получится чуть менее эффектно, чем в консоли линукса, но логика отработает.