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

Question

Я пытаюсь получить алгоритм minmax (компьютер AI) для работы в моей игре tic-tac-toe. Я застрял на этом несколько дней. По сути, я не понимаю, почему компьютерный ИИ просто помещает его маркер ("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 

Answer 1

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

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 

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