def min_max(game_spec, board_state, side, max_depth, evaluation_func=None):
    """Runs the min_max_algorithm on a given board_sate for a given side, to a given depth in order to find the best
    move

    Args:
        game_spec (BaseGameSpec): The specification for the game we are evaluating
        evaluation_func (board_state -> int): Function used to evaluate the position for the plus player, If None then
            we will use the evaluation function from the game_spec
        board_state (3x3 tuple of int): The board state we are evaluating
        side (int): either +1 or -1
        max_depth (int): how deep we want our tree to go before we use the evaluate method to determine how good the
        position is.

    Returns:
        (best_score(int), best_score_move((int, int)): the move found to be best and what it's min-max score was
    """
    best_score = None
    best_score_move = None
    evaluation_func = evaluation_func or game_spec.evaluate

    moves = list(game_spec.available_moves(board_state))
    if not moves:
        # this is a draw
        return 0, None

    for move in moves:
        new_board_state = game_spec.apply_move(board_state, move, side)
        winner = game_spec.has_winner(new_board_state)
        if winner != 0:
            return winner * 10000, move
        else:
            if max_depth <= 1:
                score = evaluation_func(new_board_state)
            else:
                score, _ = min_max(game_spec, new_board_state, -side, max_depth - 1, evaluation_func=evaluation_func)
            if side > 0:
                if best_score is None or score > best_score:
                    best_score = score
                    best_score_move = move
            else:
                if best_score is None or score < best_score:
                    best_score = score
                    best_score_move = move
    return best_score, best_score_move