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 -- http://mail.python.org/mailman/listinfo/python-list
