AlphaBeta Search

[Chris]

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