Python recursive tree or fowards? Fix and simplify code

Question

I originally was using recursion to minimax my tree from the leaves where only I have scores evaluated, but because I needed to know the depth to know whether to min or max, I switched to starting at depth=0. However, errors since sometimes currentRoot.ia = None since no score has been calculated there that deep. What I want is to keep track of depth, and find the deepest leaves that have had currentRoot.ia evaluated, and minimax from that depth at each leaf.

I check if there are grandchildren since when I evaluate a position to get a score I also add a node of the move that gave that score, so there shouldn't be any scores at the leaf nodes. Scores are from the engine's point of view, so I have to negate at odd depths, although perhaps I could get away with not, if I always max the score.

def minimax(currentRoot, depth):
    if len(currentRoot.children) > 0 and len(currentRoot.children[0].children) > 0: #There are grandchildren
        for child in currentRoot.children:
            minimax(child, depth+1)
    else:           
        if depth%2 == 0:
            currentRoot.score = currentRoot.ia
        else:
            currentRoot.score = -currentRoot.ia
        return currentRoot.score

    measure = min if depth % 2 else max
    currentRoot.score = measure(c.score for c in currentRoot.children)
    return currentRoot.score

@Tadhg currentRoot.score = measure(c.score for c in currentRoot.children) TypeError: unorderable types: NoneType < int — Josh
Next time please post the error in the question, the whole traceback if possible. — Tadhg McDonald-Jensen

Josh Josh · Accepted Answer · 2016-06-24T23:41:49

I'm thinking this might solve my error, but I don't feel it is elegant. I recurse until I found a value so ia is not None, and I go deeper until I find I am at a leaf where the tree has not been evaluated further.

def minimax(currentRoot, depth):
    notAtLeaf = True
    if currentRoot.ia is None:
        notAtLeaf = False
        for child in currentRoot.children:
            minimax(child, depth+1)
    else: #currentRoot.ia is not None
        for child in currentRoot.children:
            if child.ia is not None:
                notAtLeaf = False
                minimax(child, depth+1)

    if notAtLeaf:
        if depth%2 == 0:
            currentRoot.score = currentRoot.ia
        else:
            currentRoot.score = -currentRoot.ia
        return currentRoot.score

    measure = min if depth % 2 else max
    currentRoot.score = measure(c.score for c in currentRoot.children)
    return currentRoot.score

Python recursive tree or fowards? Fix and simplify code

1 Answers