Skip to content

Instantly share code, notes, and snippets.

@craine
Last active Sep 29, 2017
Embed
What would you like to do?
alphabeta
class AlphaBetaPlayer(IsolationPlayer):
self.time_left = time_left
def terminal_test(self, game):
if self.time_left() < self.TIMER_THRESHOLD:
raise SearchTimeout()
return not bool(game.get_legal_moves())
def max_value(self, game, depth, alpha=float("-inf"), beta=float("inf")):
""" Return the value for a loss (-1) if the game is over,
otherwise return the maximum value over all legal child
nodes.
"""
if self.time_left() < self.TIMER_THRESHOLD:
raise SearchTimeout()
if depth >= self.search_depth:
return self.score(game, game.active_player)
depth += 1
if self.terminal_test(game):
return -1
v = float("-inf")
for m in game.get_legal_moves():
v = max(v, self.min_value(game.forecast_move(m), depth, alpha, beta))
if v >= beta:
return v
alpha = max(alpha, v)
return v
def min_value(self, game, depth, alpha=float("-inf"), beta=float("inf")):
""" Return the value for a win (+1) if the game is over,
otherwise return the minimum value over all legal child
nodes.
:param game:
:param depth:
:return:
"""
if self.time_left() < self.TIMER_THRESHOLD:
raise SearchTimeout()
if depth >= self.search_depth:
return self.score(game, game.active_player)
depth += 1
if self.terminal_test(game):
return 1
v = float("inf")
for m in game.get_legal_moves():
v = min(v, self.max_value(game.forecast_move(m), depth, alpha, beta))
if v >= alpha:
return v
beta = max(beta, v)
return v
def alphabeta(self, game, depth, alpha=float("-inf"), beta=float("inf")):
if self.time_left() < self.TIMER_THRESHOLD:
raise SearchTimeout()
depth = 1
best_score = alpha
best_move = None
for m in game.get_legal_moves():
v = self.min_value(game.forecast_move(m), depth, alpha, beta)
if v > best_score:
best_score = v
best_move = m
return best_move
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment