Skip to content

Instantly share code, notes, and snippets.

@kartikkukreja
Last active August 29, 2015 14:24
Show Gist options
  • Save kartikkukreja/d61f9f4c571157604dee to your computer and use it in GitHub Desktop.
Save kartikkukreja/d61f9f4c571157604dee to your computer and use it in GitHub Desktop.
Alpha Beta Search
# alpha is the MAX's best option on path to root. Initialized to -infinity.
# beta is the MIN's best option on path to root. Initialized to +infinity.
def value(problem, state, player, alpha, beta):
if problem.isTerminalState(state): return problem.getTerminalUtility(state)
if player == "MAX": return maxValue(problem, state, player, alpha, beta)
if player == "MIN": return minValue(problem, state, player, alpha, beta)
def maxValue(problem, state, player, alpha, beta):
v = -infinity
for successor in problem.getSuccessors(state):
v = max(v, value(problem, successor, "MIN", alpha, beta))
if v >= beta: return v
alpha = max(alpha, v)
return v
def minValue(problem, state, player):
v = +infinity
for successor in problem.getSuccessors(state):
v = min(v, value(problem, successor, "MAX", alpha, beta))
if v <= alpha: return v
beta = min(beta, v)
return v
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment