Mini-max for tic-tac-toe

mini_max_tic_tac_toe.py

class MiniMaxBot:
    def __init__(self):
        """ Returns best move given game and player """
        self.memo = {}
        
    def play(self, game, player):
        return self._mini_max(game, player)[0]

    def _mini_max(self, game, player):
        """ Helper function for get_best_move. Returns best move and score given game and player """
        if player not in self.memo:
            self.memo[player] = {}
            
        player_memo = self.memo[player]
        
        if game not in player_memo:
            # Check to see if we've already seen this state
            if game.gameover():
                # Game over, no moves possible
                best_move = None
                best_score = game.score_game(player)
            else:
                alt_player = [alt_player for alt_player in game.legal_players if alt_player != player][0]
                moves = game.get_moves() # Get available moves
                best_score = float("-inf") # Default to worst possible score to ensure any move is selected

                for move in moves:
                    clone = game.copy() # Make a copy of the game to run recursively
                    clone.move(player, move) # Make the proposed move
                     # Figure out what the opponents best move would be (MINI)
                    _, score = self._mini_max(clone, player=alt_player)
                    score *= -1 # Since the game is zero-sum, what's bad for the opponent is good for us
                    if score > best_score: # Best our prior best score
                        best_move = move # Save the move
                        best_score = score # Update the best score
            self.memo[player][game] = (best_move, best_score) # Update the best move and score given the game
        return self.memo[player][game] # Return best move given player and game