import random


def monteCarloTrial(player, state, stepsLeft):
    """
    Perform recursive Mote Carlo Trials, transitioning between states by randomly
    choosing among available actions.

    Performs at most stepsLeft moves, if stepsLeft = 0 or if there are no
    applicable actions for `player` in `state`, it will return the state value.

    Parameters
    ----------
    player : int in {0,1}
       Current player.
    state : Object representing game state.
       See `gameexamples.py` for examples.
    stepsLeft : int >= 0
       Maximum number of recursive levels to perform.

    Returns
    -------
    float
       Value of final state.
    """
    if stepsLeft == 0:
        return state.value()

    actions = state.applicableActions(player)
    if not actions:
        return state.value()

    player2 = 1 - player
    best = float('inf') if player == 0 else - float('inf')
    action = random.choice(actions)
    state2 = state.successor(player, action)
    v = monteCarloTrial(player2, state2, stepsLeft - 1)
    if player == 0:
        best = min(best, v)
    else:
        best = max(best, v)
    return best