# Cmput 455 sample code
# Written by Martin Mueller
# Creates the sample tree of 
# https://en.wikipedia.org/wiki/Alpha–beta_pruning 
# returns dictionary with the tree in adjacency list form
# In the names, children of the root are labeled a, b, c.
# Below that level, 'l' stands for left-most child,
# 'r' for right-most child, and
# 'm' for middle child when there are three children.

def generateSampleTree():
    tree = {}
    #d=0 root
    tree['root'] = ['a','b','c']
    #d=1
    tree['a'] = ['al','ar']
    tree['b'] = ['bl','br']
    tree['c'] = ['cl','cr']
    #d=2
    tree['al'] = ['all','alr']
    tree['ar'] = ['arr']
    tree['bl'] = ['bll','blr']
    tree['br'] = ['brr']
    tree['cl'] = ['cll']
    tree['cr'] = ['crl','crr']
    #d=3
    tree['all'] = ['alll','allr']
    tree['alr'] = ['alrl','alrm','alrr']
    tree['arr'] = ['arrr']
    tree['bll'] = ['blll']
    tree['blr'] = ['blrl','blrr']
    tree['brr'] = ['brrr']
    tree['cll'] = ['clll']
    tree['crl'] = ['crll','crlr']
    tree['crr'] = ['crrl']
    #d=4: leaves
    tree['alll'] = []
    tree['allr'] = []
    tree['alrl'] = []
    tree['alrm'] = []
    tree['alrr'] = []
    tree['arrr'] = []
    tree['blll'] = []
    tree['blrl'] = []
    tree['blrr'] = []
    tree['brrr'] = []
    tree['clll'] = []
    tree['crll'] = []
    tree['crlr'] = []
    tree['crrl'] = []

    score = {}
    score['alll'] = 5
    score['allr'] = 6
    score['alrl'] = 7
    score['alrm'] = 4
    score['alrr'] = 5
    score['arrr'] = 3
    score['blll'] = 6
    score['blrl'] = 6
    score['blrr'] = 9
    score['brrr'] = 7
    score['clll'] = 5
    score['crll'] = 9
    score['crlr'] = 8
    score['crrl'] = 6
    
    return tree, score