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
Bytes IT Community
+ 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
Share on Google+
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.