tree = {}


def is_winner(state):
    if state[:3] == '111' or state[3:6] == '111' or state[6:9] == '111' or state[:7:3] == '111' or state[1:8:3] == '111' or state[2:9:3] == '111' or state[:9:4] == '111' or state[2:7:2] == '111':
        return -1
    if state[:3] == '222' or state[3:6] == '222' or state[6:9] == '222' or state[:7:3] == '222' or state[1:8:3] == '222' or state[2:9:3] == '222' or state[:9:4] == '222' or state[2:7:2] == '222':
        return 1
    return 0


def fill_tree(state, num, step):
    global tree
    winner = is_winner(state)
    if winner == -1 or winner == 1 or step == 0:
        tree[state] = [winner]
        return
    tree[state] = []
    for i in range(9):
        if state[i] == '0':
            newstate = state[:i]+num+state[i+1:]
            tree[state].append([newstate, 0])
            if num == '1':
                fill_tree(newstate, '2', step-1)
            else:
                fill_tree(newstate, '1', step-1)


def count_tree(state, step):
    global tree
    if len(tree[state]) == 1 and tree[state][0] in [-1, 1, 0]:
        if step == 9:
            return tree[state][0]
        sum = 9-step
        cstep = 9-step
        while cstep > 1:
            cstep-=1
            sum*=cstep
        sum*=tree[state][0]
        return sum
    for v in tree[state]:
        res = count_tree(v[0], step+1)
        v[1] = res
    sum = 0
    if step % 2 == 1:
        flag = 0
        for v in tree[state]:
            if v[1] < 0:
                continue
            sum += v[1]
            flag = 1
        if flag == 0:
            sum = -1
    else:
        for v in tree[state]:
            if v[1] < 0:
                sum = -1
                break
            sum += v[1]
    return sum


ans = {}
def build_json(state):
    global ans
    ans[state] = []
    try:
        if len(tree[state]) == 1 and type(tree[state][0]) is int:
            if tree[state][0] == 1:
                ans[state].append(('smth','smth'))                 # бот победил
            else:
                ans[state].append(('smth', 'smth'))                # бот дошел до ничьи
            return
    except KeyError:
        pass
    for c in tree[state]:
        if type(tree[c[0]][0]) is int:
            ans[state].append((c[0],'draw'))           # ничья, c[0] - ход человека, привел к ничье
        else:
            maxvalue = -1000000000
            maxstate = ''
            for pc in tree[c[0]]:
                try:
                    if len(tree[pc[0]]) == 1 and type(tree[pc[0]][0]) is int and tree[pc[0]][0] > 0:
                        maxstate = pc[0]
                        break
                    if pc[1] > maxvalue:
                        maxvalue = pc[1]
                        maxstate = pc[0]
                except IndexError:
                    pass
            if maxstate == '':
                pass
            ans[state].append((c[0], maxstate))
            build_json(maxstate)


fill_tree('000000000', '1', 9)
count_tree('000000000', 0)
build_json('000000000')
# print(ans)
print(tree)