def minmax_decision(state):
    def max_value(state):
        if is_terminal(state):
            return utility_of(state)
        v = -infinity
        for (a, s) in successors_of(state):
            v = max(v, min_value(s))
        print('V: ' + str(v))
        return v

    def min_value(state):
        if is_terminal(state):
            return utility_of(state)
        v = infinity
        for (a, s) in successors_of(state):
            v = min(v, max_value(s))
        return v

    infinity = float('inf')
    action, state = argmax(successors_of(state), lambda a: min_value(a[1]))
    return action

'''
def is_terminal(state):

    board_is_full = True  # starter med at sætte et fuldt bræt
    for i in range(len(state)):  # looper igennem længden af state og hvis det ikke er fyldt med X eller O er det ikke fyldt
        if state[i] != 'O' and state[i] != 'X':
            board_is_full = False
            break

    if board_is_full:  # returnerer hvis brættet er fyldt
        return True

    #bruger resultatet af utility_of(state) til at se om der er vundet eller tabt, ellers returneres false.
    utility = utility_of(state)
    if utility == 1 or utility == -1:
        return True
    else:
        return False
'''

def is_terminal(state):
    no_options = True
    for entry in state:
        if entry > 2:    # hvis bunken er større end 2, kan man stadig dele bunken.
            no_options = False
            break

    if no_options:
        return True

    utility = utility_of(state)
    if utility == 0 or utility == 1:
        return True
    else:
        return False


def utility_of(state):
    """
    returns +1 if winner is X (MAX player), -1 if winner is O (MIN player), or 0 otherwise
    :param state: State of the checkerboard. Ex: [0; 1; 2; 3; X; 5; 6; 7; 8]
    :return:
    """
    for entry in state:
        if entry == 2 and len(state) % 2 == 1:
            return 1
        elif entry == 2 and len(state) % 2 == 0:
            return 0

    return -1



def successors_of(state):
    """
    returns a list of tuples (move, state) as shown in the exercise slides
    :param state: State of the checkerboard. Ex: [0; 1; 2; 3; X; 5; 6; 7; 8]
    :return:
    """

    # Figure out whos' turn it is.

    min_turn = False
    if len(state) % 2 == 1:
        min_turn = True

    # Generate valid moves
    valid_moves = []
    for i in range(len(state)):
        if state[i] == 1 or state[i] == 2:
            continue
        count = 1
        while count < state[i]/2:
            new_state = state.copy()
            new_state[i] = new_state[i]-count
            new_state.append(count)
            new_state.sort(reverse=True)
            valid_moves.append((count,new_state))
            count += 1
    return valid_moves



def display(state):
    print("-----")
    print(state)
    '''
    for c in [0, 3, 6]:
        print(state[c + 0], state[c + 1], state[c + 2])
    '''

def main():
    board = [7]
    while not is_terminal(board):
        board[minmax_decision(board)] = 'X'
        if not is_terminal(board):
            display(board)
            board[int(input('Your move? '))] = 'O'
    display(board)


def argmax(iterable, func):
    return max(iterable, key=func)


if __name__ == '__main__':
    main()