如何使用alpha beta剪枝实现转置表
如何使用alpha beta剪枝实现转置表
提问于 2021-01-18 01:50:28
我正在尝试在我的negamax中实现转换表。但首先，我想了解伪代码中的所有概念：
` alphaOrig := (α，β，depth，α，β，color) is alphaOrig negamax
(* Transposition Table Lookup; node is the lookup key for ttEntry *)
ttEntry := transpositionTableLookup(node)
if ttEntry is valid and ttEntry.depth ≥ depth then
if ttEntry.flag = EXACT then
return ttEntry.value
else if ttEntry.flag = LOWERBOUND then
α := max(α, ttEntry.value)
else if ttEntry.flag = UPPERBOUND then
β := min(β, ttEntry.value)
if α ≥ β then
return ttEntry.value
if depth = 0 or node is a terminal node then
return color × the heuristic value of node
childNodes := generateMoves(node)
childNodes := orderMoves(childNodes)
value := −∞
for each child in childNodes do
value := max(value, −negamax(child, depth − 1, −β, −α, −color))
α := max(α, value)
if α ≥ β then
break
(* Transposition Table Store; node is the lookup key for ttEntry *)
ttEntry.value := value
if value ≤ alphaOrig then
ttEntry.flag := UPPERBOUND
else if value ≥ β then
ttEntry.flag := LOWERBOUND
else
ttEntry.flag := EXACT
ttEntry.depth := depth
transpositionTableStore(node, ttEntry)
return value但我想知道的一件事是旗帜是什么？如EXACT、UPPERBOUND和LOWERBOUND
回答 1
Stack Overflow用户
回答已采纳
发布于 2021-01-18 13:49:51
在使用alpha beta的Negamax搜索中，通常从无限窗口(alpha=-inf，beta=inf)开始。然后，在搜索过程中，由于截止，这个窗口会变窄，这会导致增加alpha或降低beta。
这些标志指示您找到的节点类型。如果您在搜索窗口中找到了一个节点(alpha < score < beta)，这意味着您有一个确切的节点。下限表示>=测试版的分数，上限表示<=α的分数。
你可以阅读更多关于它的here，这也是一个很好的页面，可以找到你需要的所有国际象棋编程。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/65764015
复制相关文章
相似问题
腾讯云开发者
