I know this probably seems trivial, but I can't seem to find the bug in

my alphabeta search implementation.

I'm testing it with the game of tic-tac-toe. If the first player plays

in a corner, the correct move is to play in the center, but for some

reason my code thinks the center and remaining corner positions are all

equally good moves.

I adopted my code almost exactly from the pseudo-code posted in the

wikipedia article (

http://en.wikipedia.org/wiki/Alpha-beta_pruning).

Can anyone point out if I'm doing anything clearly wrong, or if the

pseudo-code isn't correct? Any help is appreciated.

infinity = 1e99999999

def alphaBeta(root, maxDepth=10):

"""Search game to determine best action; use alpha-beta pruning."""

player = root.turn

def is_terminal(node, depth):

'''The default test cuts off at depth d or at a terminal

state.'''

return depth maxDepth or node.isGameOver()

def heuristic_value(node):

'''Returns heuristic value of game relative to the turn in the

root game.'''

player1Score,player2Score = node.getScore()

if node.turn == player:

score = player1Score-player2Score

else:

score = player2Score-player1Score

return score

def search(node, alpha, beta, depth):

if is_terminal(node, depth):

return heuristic_value(node)

for nextNode in node.getNextNodes():

v = alpha = max(alpha, -search(nextNode, -beta, -alpha,

depth+1))

if alpha >= beta:

break

return v

# Evaluate all choices.

choices = map(lambda node: (search(node, -infinity, infinity, 0),

node.actionHistory[-1]),

root.getNextNodes())

# Chose best action.

score,action = max(choices)

return action