Problem with alpha-beta pruning method, returns beta? maybe I don't understand how this works
Shouldn't it return a 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
constants:
WIN = 1
LOSS = -1
DRAW = 0
INFINITY = 100
COMPUTER = 0
HUMAN = 1
test case:
# 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 fi开发者_运维知识库rst) 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
relevant methods and other things to help read the code above:
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
You ignored my comment in a previous question. has_this_player_won?
returns a boolean value which can never be equal to an integer player
. Besides, your logic at the beginning is wrong: the game can have a winner even if there are no more moves left. And finally, the first call to the recursive function should be made with alpha=-inf, beta=+inf
. The relevant sections of code:
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)
精彩评论