Ruby: implementing alpha-beta pruning for tic-tac-toe
0
votes
0
votes
Posted by: NullVoxPopuli on 08/21/2015 | Add Revision
So, alpha-beta pruning seems to be the most efficient algorithm out there aside from hard coding (for tic tac toe). However, I'm having problems converting the algorithm from the C++ example given in the link: http://www.webkinesia.com/games/gametree.php
Players are either 1 or 0, so doing 1 - player will switch the player
WIN = 1
LOSS = -1
DRAW = 0
INFINITY = 100
def calculate_ai_next_move
best_move = -1
best_score = -INFINITY
cur_player = COMPUTER
self.remaining_moves.each do |move|
self.make_move_with_index(move, cur_player)
score = -self.alphabeta(-INFINITY,INFINITY, 1 - cur_player)
self.undo_move(move)
if score > best_score
best_score = score
best_move = move
end
end
return best_move
end
def alphabeta(alpha, beta, player)
best_score = -INFINITY
if not self.has_available_moves?
return WIN if self.has_this_player_won?(player) == player
return LOSS if self.has_this_player_won?(1 - player) == 1 - player
else
self.remaining_moves.each do |move|
break if alpha > beta
self.make_move_with_index(move, player)
move_score = -alphabeta(-alpha, -beta, 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
currently, the algorithm is playing terribly. It will initially pick the last space, and then choose the first (from left to right) available space after that.
Any idea with whats wrong with it?
Also, I've been doing TDD, so I know that self.has_this_player_won?, self.undo_move and self.remaining_moves is correct.