在井字游戏中调试递归 MiniMax

Question

我正在尝试让 minmax 算法（计算机 AI）在我的井字游戏中发挥作用。我已经坚持了好几天了。从本质上讲，我不明白为什么计算机 AI 只是按照棋盘 0-8 的顺序放置它的标记 ("O")。

例如，作为人类玩家，如果我选择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 class（没有我所有的打印语句）。 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 总是 returns 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

有了这两个例程的替换，计算机采取的步骤似乎更合乎逻辑。

在井字游戏中调试递归 MiniMax

Debugging Recursive MinMax in TicTacToe

ruby

algorithm

tic-tac-toe

minmax