Sign in

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

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

Вторая часть материала, озаглавленного Нейронная сеть для игры в крестики-нолики.

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

 

По ходу игры необходимо опасаться вилок, избегая, по возможности, ходов, способных к ним привести. Примем за аксиому, что вас возможно подвести к вилке только после второго или третьего вашего хода (напоминаю, вы играете вторым номером, "ноликами"), и никак иначе. Будем считать, что к вилке привел именно последний ваш ход; такое допущение, ввиду крайней простоты Tic Tac Toe, приемлемо. Как быть с этим?

 

Примечание. Статья содержит лишь очень небольшие фрагменты кода. Тем, кто считает, что для лучшего понимания материала нужно рассмотреть всю кодовую базу (или просто поиграть), оптимально выполнить:

git clone https://github.com/cmirnow/Tic-Tac-Toe-AI-with-Neural-Network.git

 

В настоящий момент я остановился на следующей логике, которая, вполне может статься, изменится в дальнейшем. Но пока что результат устраивает. Определяем (и замораживаем) константу (первоначально используется для определения того, что партия завершена чьим-то выигрышем, к слову. Форки - побочное):

 

  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]] #&&
        #@board[x[0]].class == @board[x[1]].class
    end
  end
  
  def fork_danger_2?
    DANGEROUS_SITUATIONS_2.detect do |x|
      @board[x[0]] == @board[x[2]] &&
        @board[x[0]] != @board[x[1]] #&&
        #@board[x[0]].class == @board[x[1]].class
    end
  end

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

 

И, соответственно, создадим три массива, в которые, при каждом очередном анализе ситуации на доске, станем помещать удовлетворяющие условиям ходы: 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

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

 

CSV::WithProgressBar.read('ss.csv').each.to_a

 

, пауз нет, наш Artificial Intelligence работает практически мгновенно:

  

    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

 

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

То, что в итоге, скармливаем нейронке:

 

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

 

    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-файл (такое случается, но очень нечасто), который в этом случае оптимально пересоздать. Впрочем, описанная ревизия кода, может статься, вовсе не окончательная, итоги подводить рано.

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

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