By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
 440,034 Members | 2,000 Online
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 440,034 IT Pros & Developers. It's quick & easy.

# AlphaBeta Search

 P: n/a 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 Jan 13 '07 #1
Share this Question
2 Replies

 P: n/a Chris wrote: I know this probably seems trivial, but I can't seem to find the bug in my alphabeta search implementation. This is another alphabeta implementation (all the nicest algorithms are inside this AIMA codebase): http://aima.cs.berkeley.edu/python/games.html Later when you program works you can find this helpful to improve your algorithm: http://citeseer.ist.psu.edu/11954.html Bye, bearophile Jan 13 '07 #2

 P: n/a bearophileH...@lycos.com wrote: Chris wrote: I know this probably seems trivial, but I can't seem to find the bug in my alphabeta search implementation. This is another alphabeta implementation (all the nicest algorithms are inside this AIMA codebase): http://aima.cs.berkeley.edu/python/games.html Later when you program works you can find this helpful to improve your algorithm: http://citeseer.ist.psu.edu/11954.html Thanks. I actually already knew about the AIMA implementation, and used that and an alternative version on wikipedia to fix my code. It turns out my heuristic_value function was incorrect. I've also managed to get it working with a transposition table, which has really sped things up. Jan 13 '07 #3

### This discussion thread is closed

Replies have been disabled for this discussion.