Ruby: implementing alpha-beta pruning for tic-tac-toe
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.