"""Owned finite alternating MAX/MIN tree, exhaustive oracle and real alpha-beta cutoffs."""
import math,json,copy
def tree():
    return {'id':'root','children':[{'id':name,'children':[{'id':name+str(i+1),'value':v} for i,v in enumerate(values)]} for name,values in [('A',[4,9,6]),('B',[2,-5,10]),('C',[5,3,7])]]}
def minimax(n,maxturn,visited):
    if 'value'in n:visited.append(n['id']);return n['value']
    vals=[minimax(c,not maxturn,visited) for c in n['children']];return max(vals) if maxturn else min(vals)
def leaf_ids(n):return [n['id']] if 'value'in n else [v for c in n['children'] for v in leaf_ids(c)]
def run(root):
    visited=[];cuts=[]
    def ab(n,maxturn,alpha,beta):
        if 'value'in n:visited.append(n['id']);return n['value']
        value=-math.inf if maxturn else math.inf
        for i,c in enumerate(n['children']):
            v=ab(c,not maxturn,alpha,beta);value=max(value,v) if maxturn else min(value,v)
            if maxturn:alpha=max(alpha,value)
            else:beta=min(beta,value)
            if alpha>=beta and i+1<len(n['children']):
                cuts.append({'at_node':n['id'],'alpha_lower_bound':alpha,'beta_upper_bound':beta,'returned_fail_soft_bound':value,'skipped_leaf_ids':[x for rest in n['children'][i+1:] for x in leaf_ids(rest)],'partial_node_value_is_not_claimed_exact':True});break
        return value
    # Root separately keeps the first best move; child searches share alpha.
    best=-math.inf;move=None
    for child in root['children']:
        v=ab(child,False,best,math.inf)
        if v>best:best=v;move=child['id']
    return {'root_value':best,'root_selected_move':move,'visited_leaf_ids':visited,'leaf_utility_evaluations':len(visited),'cutoffs':cuts}
def reverse_all(n):
    if 'children'in n:
        n['children'].reverse()
        for c in n['children']:reverse_all(c)
def demo():
    T=tree();full=[];oracle=minimax(T,True,full);exact_children={c['id']:minimax(c,False,[]) for c in T['children']};a=run(T);R=copy.deepcopy(T);reverse_all(R);b=run(R)
    assert oracle==a['root_value']==b['root_value']==4 and a['root_selected_move']==b['root_selected_move']=='A'
    assert len(full)==9 and a['leaf_utility_evaluations']==6 and b['leaf_utility_evaluations']==8
    assert exact_children=={'A':4,'B':-5,'C':3}
    assert a['cutoffs'][0]['returned_fail_soft_bound']==2 and exact_children['B']==-5
    assert set(a['visited_leaf_ids']).isdisjoint(x for c in a['cutoffs'] for x in c['skipped_leaf_ids'])
    return {'payoff_convention':'leaf utility from MAX perspective, opponent utility its negative; deterministic perfect information alternating rootMAX/childrenMIN','authored_tree':T,'exhaustive_minimax_value':oracle,'exhaustive_child_values':exact_children,'exhaustive_leaf_evaluations':len(full),'alpha_beta_original_order':a,'alpha_beta_all_children_reversed':b,'tie_policy':'first root child with best value; equal values do not replace move','learning_or_real_game_or_Berkeley_code_executed':False}
if __name__=='__main__':print(json.dumps(demo(),indent=2,allow_nan=False))