ruby – 在TicTacToe中调试递归MinMax

发布时间：2020-12-17 02:23:56 所属栏目：百科来源：网络整理

导读：我试图让minmax算法(计算机AI)在我的tic-tac-toe游戏中运行.我已经坚持了几天.基本上,我不明白为什么计算机AI只是从板块0-8按顺序放置它的标记(“O”). 例如,作为人类玩家,如果我选择1,那么计算机将选择0： O| X| 2--+---+-- 3| 4| 5--+---+-- 6| 7| 8 接下

我试图让minmax算法(计算机AI)在我的tic-tac-toe游戏中运行.我已经坚持了几天.基本上,我不明白为什么计算机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类(并且没有我的所有打印语句). minmax方法是我遇到很多麻烦的地方. (我不是百分之百肯定使用的是bad_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

解决方法

问题是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

通过这两个例程替换,计算机采取的步骤似乎更合乎逻辑.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!