動機
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