import math


def num_random_constructions(n):
    """
    Gives the number of random constructions we feel necessary to capture most of the space in our Monte Carlo Tree
    Search. We start with the theoretical maximum number of constructions up to 4 steps (2, 24, 1344, 244608), which
    were found manually by assuming that a new circle is generated each step and it intersects twice with every other
    circle and line in the diagram. This obviously over-counts the number of constructions, but forms a decent estimate.

    We also multiply it by some buffer, since we choose our random constructions with replacement, so we're bound to get
    duplicates occasionally.

    :param n: number of steps in constructions
    :return: An estimate of the maximum number of constructions of length n
    """
    buffer = .5  # Chosen to be less than one only for speed purposes.
    num_constructions: int  # Estimated maximum number of constructions
    if n == 0:
        return 1
    elif n == 1:
        num_constructions = 2
    elif n == 2:
        num_constructions = 24
    elif n == 3:
        num_constructions = 1344
    elif n == 4:
        num_constructions = 244608
    else:
        num_constructions = 250000
    return math.ceil(num_constructions * buffer)