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
