# Ruby: implementing alpha-beta pruning for tic-tac-toe

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.

You need a minimal test case that reproduces the problem - input a board that will be solved with one step of the algorithm, and follow it with a debugger, or print statements if that isn't possible.

You can find out which return is actually returning the nil value - you could insert a breakpoint on the line previous to each return statement, or add a unique print statement before each return. Then track backwards to discover where the nil was introduced.

Another way would just be to step through the whole get_best_move function using a debugger and check it's doing what you expect (the code is short enough for this approach to be realistic).

Other observations:

• COMPUTER isn't defined
• This looks more like minimax than alpha-beta
• It's not clear from your question if it's the calculate_ai_next_move or the get_best_move that is returning nil.
• oh, COMPUTER is a static variable defined at the top of the class. – NullVoxPopuli Feb 1 '11 at 13:39
• @CiscolPPhone, I just updated my question, the code has changed. – NullVoxPopuli Feb 1 '11 at 19:44
• @DerNalia We prefer that you ask a new question instead of making massive scope changing edits to your existing one. Better for records, and rep and stuff. :) – Jesse Dorsey Feb 1 '11 at 20:15