Skip to content

Instantly share code, notes, and snippets.

@craine
Created Oct 3, 2017
Embed
What would you like to do?
class AlphaBetaPlayer(IsolationPlayer):
"""Game-playing agent that chooses a move using iterative deepening minimax
search with alpha-beta pruning. You must finish and test this player to
make sure it returns a good move before the search time limit expires.
"""
def get_move(self, game, time_left):
"""Search for the best move from the available legal moves and return a
result before the time limit expires.
Modify the get_move() method from the MinimaxPlayer class to implement
iterative deepening search instead of fixed-depth search.
**********************************************************************
NOTE: If time_left() < 0 when this function returns, the agent will
forfeit the game due to timeout. You must return _before_ the
timer reaches 0.
**********************************************************************
Parameters
----------
game : `isolation.Board`
An instance of `isolation.Board` encoding the current state of the
game (e.g., player locations and blocked cells).
time_left : callable
A function that returns the number of milliseconds left in the
current turn. Returning with any less than 0 ms remaining forfeits
the game.
Returns
-------
(int, int)
Board coordinates corresponding to a legal move; may return
(-1, -1) if there are no available legal moves.
"""
self.time_left = time_left
best_move = (-1, -1)
try:
for depth in range(1, 200):
best_move = self.alphabeta(game, depth=depth)
except SearchTimeout:
pass
# Return the best move from the last completed search iteration
return best_move
def terminal_test(self, game):
""" Return True if the game is over for the active player
and False otherwise.
"""
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, self)
depth += 1
if self.terminal_test(game):
return self.score()
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, self)
depth += 1
if self.terminal_test(game):
return self.score()
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")):
"""Implement depth-limited minimax search with alpha-beta pruning as
described in the lectures.
This should be a modified version of ALPHA-BETA-SEARCH in the AIMA text
https://github.com/aimacode/aima-pseudocode/blob/master/md/Alpha-Beta-Search.md
**********************************************************************
You MAY add additional methods to this class, or define helper
functions to implement the required functionality.
**********************************************************************
Parameters
----------
game : isolation.Board
An instance of the Isolation game `Board` class representing the
current game state
depth : int
Depth is an integer representing the maximum number of plies to
search in the game tree before aborting
alpha : float
Alpha limits the lower bound of search on minimizing layers
beta : float
Beta limits the upper bound of search on maximizing layers
Returns
-------
(int, int)
The board coordinates of the best move found in the current search;
(-1, -1) if there are no legal moves
Notes
-----
(1) You MUST use the `self.score()` method for board evaluation
to pass the project tests; you cannot call any other evaluation
function directly.
(2) If you use any helper functions (e.g., as shown in the AIMA
pseudocode) then you must copy the timer check into the top of
each helper function or else your agent will timeout during
testing.
"""
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
alpha = max(alpha, v)
return best_move
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment