import copy

global num_branches
num_branches = 0

def minimax(env, alpha, beta):
    global num_branches
    num_branches += 1

    if env.was_winning_move():
        if env.player_at_turn == 'x':
            return 1
        else:
            return -1
    if env.grid_is_full():
        return 0

    env.change_turn()

    if env.player_at_turn == 'x':
        value = -2
        for x in env.available_actions:
            new_env = copy.deepcopy(env)
            new_env.act(action = x)
            value = max(value, minimax(new_env, alpha, beta))
            alpha = max(alpha, value)
            if beta <= alpha:
                break
        return value
    else:
        value = 2
        for x in env.available_actions:
            new_env = copy.deepcopy(env)
            new_env.act(action = x)
            value = min(value, minimax(new_env, alpha, beta))
            beta = min(beta, value)
            if beta <= alpha:
                break
        return value

start = time.time()
state_value = minimax(env, -2, 2)
print(time.time()-start)

print("state_value ", state_value)
print("num_branches ", num_branches)