alphabeta
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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