ruby - alpha-beta 修剪方法有问题，返回 beta？也许我不明白这是怎么回事

Question

它不应该返回一个 DRAW 吗？

def alphabeta(alpha, beta, player)
      best_score = -INFINITY
      if not self.has_available_moves?
        return DRAW
      elsif self.has_this_player_won?(player) == player
        return WIN
      elsif self.has_this_player_won?(1 - player) == 1 - player
        return LOSS
      else
        self.remaining_moves.each do |move|
          if alpha >= beta then return alpha end 

          self.make_move_with_index(move, player)
          move_score = -alphabeta(-beta, -alpha, 1 - player)
          self.undo_move(move)

          if move_score > alpha
            alpha = move_score
            next_move = move
          end
          best_score = alpha
        end
      end
      return best_score
    end

常量:

WIN = 1
LOSS = -1
DRAW = 0
INFINITY = 100

COMPUTER = 0
HUMAN = 1

测试用例:

   # computer is 0, human is 1
   # c h c
   # _ h h
   # _ c h -- computer's turn
   test "make sure alpha-beta pruning works (human went first) 1" do
     @board.state = [0,1,0,nil,1,1,nil,0,1]
     score = @board.alphabeta(100, -100, Board::COMPUTER)
     assert_equal(Board::DRAW, score)

   end

帮助阅读上面代码的相关方法和其他东西:

self.state = Array.new(9)

    WAYS_TO_WIN = [[0, 1, 2], [3, 4, 5], [6, 7, 8], [0, 3, 6], [1, 4, 7], [2, 5, 8],[0, 4, 8], [2, 4, 6]]


 def make_move_with_index(index, player)
        self.state[index] = player
    end


    def undo_move(index)
        self.state[index] = nil
    end

def has_this_player_won?(player)
      WAYS_TO_WIN.each do |way_to_win|
          return true if self.state.values_at(*way_to_win).uniq.size == 1 and self.state[way_to_win[0]] == player
      end

      return false
    end

    def remaining_moves
        self.state.each_with_index.map{|e,i| (e.nil?) ? i : nil }.compact
    end

    def has_available_moves?
        return self.state.include? nil
    end

Answer 1

您在上一个问题中忽略了我的评论。 has_this_player_won? 返回一个 bool 值，该值永远不能等于整数 player。而且，你一开始的逻辑是错误的:即使没有剩下的步数，游戏也可以有赢家。最后，对递归函数的第一次调用应该使用 alpha=-inf, beta=+inf。相关代码部分:

if self.has_this_player_won?(1 - player)
    return LOSS
elsif not self.has_available_moves?
    return DRAW
else
    ...

score = @board.alphabeta(-INFINITY, INFINITY, Board::COMPUTER)