# Cmput 455 sample code
# Alphabeta algorithm
# Written by Martin Mueller

from search_basics import INFINITY

def alphabeta(state, alpha, beta):
    if state.endOfGame():
        return state.staticallyEvaluateForToPlay() 
    for m in state.legalMoves():
        state.play(m)
        value = -alphabeta(state, -beta, -alpha)
        if value > alpha:
            alpha = value
        state.undoMove()
        if value >= beta: 
            return beta   # or value in failsoft (later)
    return alpha

def alphabeta_with_move(state, alpha, beta):
    # this code only supports remembering the move at the root
    assert alpha == -INFINITY
    assert beta == INFINITY
    if state.endOfGame():
        return state.staticallyEvaluateForToPlay(), None 
    best_move = None
    for m in state.legalMoves():
        state.play(m)
        value = -alphabeta(state, -beta, -alpha)
        if value > alpha:
            alpha = value
            best_move = m
        state.undoMove()
        if value >= beta: 
            return beta, best_move   # or value in failsoft (later)
    return alpha, best_move


# initial call with full window
def callAlphabeta(rootState):
    return alphabeta_with_move(rootState, -INFINITY, INFINITY)