Отладка рекурсивного MinMax в TicTacToe

Я пытаюсь заставить алгоритм minmax (компьютерный ИИ) работать в моей игре в крестики-нолики. Я застрял на этом в течение нескольких дней. По сути, я не понимаю, почему компьютерный ИИ просто размещает свой маркер ("O") в последовательном порядке из частей доски 0-8.

Например, в качестве игрока-человека, если я выберу 1, то компьютер выберет 0:

 O| X| 2
--+---+--
 3| 4| 5
--+---+--
 6| 7| 8

Далее, если я выберу 4, то компьютер выберет 2:

 O| X| O
--+---+--
 3| X| 5
--+---+--
 6| 7| 8

И так далее:

 O| X| O
--+---+--
 O| X| O
--+---+--
 X| 7| X

Я отлаживал алгоритм minmax настолько, насколько мог, но становится очень трудно следить за тем, что происходит.

Вот класс ComputerPlayer с алгоритмом (и без всех моих операторов печати). С методом minmax у меня много проблем. (Я не уверен на 100% в использовании worst_score или даже связанной с ним логики.)

class ComputerPlayer < Player
  def move(game_board)
    minmax(game_board) #minmax to create @best_move

    game_board.place_piece(@best_move, marker)
  end

  def minmax(board, player_tracker = 0) 
    if board.game_over?
      return score(board)
    else
      worst_score  = (1.0/0.0) #Infinity
      best_score  = -(1.0/0.0) #-Infinity
      @best_move  = board.get_available_positions.first

      new_marker = player_tracker.even? ? 'O' : 'X'
      player_tracker += 1

      board.get_available_positions.each do |move|
        new_board = board.place_piece(move, new_marker)
        current_score = minmax(new_board, player_tracker)
        if new_marker == marker #if the player is the computer player
          if current_score > best_score
            @best_move = move
            best_score = current_score
          end
        else
          if current_score < worst_score
            worst_score = current_score
          end
        end
      end
    end
    return best_score
  end

  def score(board)
    if board.winner == "O" #'O' == 'O', 'nil' == 'O'
      10
    elsif board.winner == "X" #'X' != 'O', 'nil' != 'O'
      -10
    elsif board.winner == nil
      0
    end
  end
end

ruby tic-tac-toe algorithm minmax
person funfuntime    schedule 23.04.2015    source источник

Ответы (1)


arrow_upward
3
arrow_downward

Проблема в том, что minmax всегда возвращает best_score.

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

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

def minmax(board, player_tracker = 0, iteration = 0) #minmax
    if board.game_over?
        return score(board, iteration)
    end

    new_marker = player_tracker.even? ? 'O' : 'X'

    scores = {}
    board.get_available_positions.each do |move|
        new_board = board.place_piece(move, new_marker)
        scores[move] = minmax(new_board, player_tracker + 1, iteration + 1)
    end

    if player_tracker.even?
        @best_move = scores.sort_by {|_key, value| value}.reverse.to_h.keys[0]
    else
        @best_move = scores.sort_by {|_key, value| value}.to_h.keys[0]
    end

    return scores[@best_move]
end

Чтобы даже повысить точность, я переписал процедуру подсчета очков, чтобы также учитывать итерации, необходимые для создания доски для подсчета очков. Возможность выиграть в 1 итерации должна быть предпочтительнее, чем победа в 3 итерациях, верно?

def score(board, iteration)
    # "O", "X", "nil"
    if board.winner == "O" #'O' == 'O', 'nil' == 'O'
      10.0 / iteration
    elsif board.winner == "X" #'X' != 'O', 'nil' != 'O'
      -10.0 / iteration
    elsif board.winner == nil
      0
    else
      raise "ERROR"
    end
end

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

person Philip Bijker    schedule 24.04.2015
comment
Таким образом, хеш результатов поддерживает все результаты ОБОИХ игроков? - person funfuntime; 27.04.2015
comment
Scores — это локальная переменная, которая будет отслеживать все оценки в рамках итерации. Таким образом, для каждой итерации он будет отслеживать все результаты для одного игрока. - person Philip Bijker; 28.04.2015