動機

minmax

在局面確定的雙人對弈裡,常進行對抗搜索,構建一棵每個節點都為一個確定狀態的搜索樹。奇數層為己方先手,偶數層為對方先手。搜索樹上每個葉子節點都會被賦予一個估值,估值越大代表我方贏面越大。

一層從children中挑大的node,下一層就是從children中挑小的node 之後就是前序去更新上下界,如果下界大於上界就是此點不用再找了

def minmax(root, a, b, isMax):
    if not root.children:
        return root.val
    if isMax:
        for node in root.children:
            a = max(a, minmax(node, a, b, not isMax)) # 挑最大,變下界
            if a >= b: # 不用再看了
                break
        return a 
    else:
        for node in root.children:
            b = min(b, minmax(node, a, b, not isMax)) # 挑最小,變上界
            if a >= b: # 不用再看了
                break
        return b