国际象棋:静止搜索主导运行时
Chess: quiescence search dominating runtime
我已经为我的国际象棋引擎实现了带有静态搜索的 alpha-beta 搜索。然而,在大多数情况下,静态搜索占用了总执行时间的 80-90%,正如我的分析器所显示的那样。我的修剪有问题吗?
我已经包含了 alpha-beta 例程和静止例程。
我的静态搜索直接基于this pseudocode。
// Perform the alpha-beta search.
func ab(b *dragontoothmg.Board, alpha int16, beta int16, depth int8, halt chan bool, stop *bool) (int16, dragontoothmg.Move) {
nodeCount++
if *stop {
return alpha, 0
}
found, tableMove, tableEval, tableDepth, tableNodeType := transtable.Get(b)
if found && tableDepth >= depth {
if tableNodeType == transtable.Exact {
return tableEval, tableMove
} else if tableNodeType == transtable.LowerBound {
alpha = max(alpha, tableEval)
} else { // upperbound
beta = min(beta, tableEval)
}
if alpha >= beta {
return tableEval, tableMove
}
}
if depth == 0 {
//return eval.Evaluate(b), 0
return quiesce(b, alpha, beta, stop), 0
}
alpha0 := alpha
bestVal := int16(negInf)
moves := b.GenerateLegalMoves()
var bestMove dragontoothmg.Move
if len(moves) > 0 {
bestMove = moves[0] // randomly pick some move
}
for _, move := range moves {
unapply := b.Apply(move)
var score int16
score, _ = ab(b, -beta, -alpha, depth-1, halt, stop)
score = -score
unapply()
if score > bestVal {
bestMove = move
bestVal = score
}
alpha = max(alpha, score)
if alpha >= beta {
break
}
}
if *stop {
return bestVal, bestMove
}
var nodeType uint8
if bestVal <= alpha0 {
nodeType = transtable.UpperBound
} else if bestVal >= beta {
nodeType = transtable.LowerBound
} else {
nodeType = transtable.Exact
}
transtable.Put(b, bestMove, bestVal, depth, nodeType)
return bestVal, bestMove
}
func quiesce(b *dragontoothmg.Board, alpha int16, beta int16, stop *bool) int16 {
nodeCount++
if *stop {
return alpha
}
var standPat int16
found, _, evalresult, _, ntype := transtable.Get(b)
if found && ntype == transtable.Exact {
standPat = evalresult
} else {
standPat = eval.Evaluate(b)
transtable.Put(b, 0, standPat, 0, transtable.Exact)
}
if standPat >= beta {
return beta
}
if alpha < standPat {
alpha = standPat
}
moves := b.GenerateLegalMoves()
if len(moves) == 0 { // TODO(dylhunn): What about stalemate?
return negInf
}
for _, move := range moves {
if !isCapture(move, b) {
continue
}
unapply := b.Apply(move)
score := -quiesce(b, -beta, -alpha, stop)
unapply()
if score >= beta {
return beta
}
if score > alpha {
alpha = score
}
}
return alpha
}
func isCapture(m dragontoothmg.Move, b *dragontoothmg.Board) bool {
toBitboard := (uint64(1) << m.To())
return (toBitboard&b.White.All != 0) || (toBitboard&b.Black.All != 0)
}
如果我没看错你的代码,你正在搜索所有的捕获。为了节省工作,您可以做的是修剪无望的捕获动作。事实证明,动作差到可以跳过它们是很常见的,所以该技术非常安全。
比如看看这个位置:
芬:rnbqkbnr/pppppppp/8/8/8/8/1PP1PPP1/RNBQKBNR w KQkq - 0 1
共有三个捕获:
- Rxa7
- Qxd7+
- Rxh7
让我们假设引擎首先尝试对女王进行捕获动作。黑方有四种反吃法,但其中任何一种都可能导致截断。
例如,黑棋下Bxd7。现在白方在结果位置有两个捕获,Rxa7 或 Rxh7。
在这里,大多数引擎会认识到白色已经在 material 中退却(与 beta 相比),即使捕获棋子也无济于事。因此,这两个新车捕获都不太可能导致截止。
在这里,您当前的搜索仍然会继续搜索这些着法。检测此类情况并跳过这些动作将节省大量工作。
还有进一步的优化。例如,具有 static exchange evaluation 的强大引擎会立即看到 Qxd7 将赢得一兵,但会失去皇后。由于这是一个糟糕的交易,引擎可以立即跳过此移动。其他两个新车捕获也是如此。
不过,与往常一样,需要权衡取舍。如果你过于激进地修剪,你最终也会修剪好的动作。一般来说,我会建议多花点时间在普通搜索上,而不是在静止搜索上,所以激进的剪枝应该没问题。
我已经为我的国际象棋引擎实现了带有静态搜索的 alpha-beta 搜索。然而,在大多数情况下,静态搜索占用了总执行时间的 80-90%,正如我的分析器所显示的那样。我的修剪有问题吗?
我已经包含了 alpha-beta 例程和静止例程。
我的静态搜索直接基于this pseudocode。
// Perform the alpha-beta search.
func ab(b *dragontoothmg.Board, alpha int16, beta int16, depth int8, halt chan bool, stop *bool) (int16, dragontoothmg.Move) {
nodeCount++
if *stop {
return alpha, 0
}
found, tableMove, tableEval, tableDepth, tableNodeType := transtable.Get(b)
if found && tableDepth >= depth {
if tableNodeType == transtable.Exact {
return tableEval, tableMove
} else if tableNodeType == transtable.LowerBound {
alpha = max(alpha, tableEval)
} else { // upperbound
beta = min(beta, tableEval)
}
if alpha >= beta {
return tableEval, tableMove
}
}
if depth == 0 {
//return eval.Evaluate(b), 0
return quiesce(b, alpha, beta, stop), 0
}
alpha0 := alpha
bestVal := int16(negInf)
moves := b.GenerateLegalMoves()
var bestMove dragontoothmg.Move
if len(moves) > 0 {
bestMove = moves[0] // randomly pick some move
}
for _, move := range moves {
unapply := b.Apply(move)
var score int16
score, _ = ab(b, -beta, -alpha, depth-1, halt, stop)
score = -score
unapply()
if score > bestVal {
bestMove = move
bestVal = score
}
alpha = max(alpha, score)
if alpha >= beta {
break
}
}
if *stop {
return bestVal, bestMove
}
var nodeType uint8
if bestVal <= alpha0 {
nodeType = transtable.UpperBound
} else if bestVal >= beta {
nodeType = transtable.LowerBound
} else {
nodeType = transtable.Exact
}
transtable.Put(b, bestMove, bestVal, depth, nodeType)
return bestVal, bestMove
}
func quiesce(b *dragontoothmg.Board, alpha int16, beta int16, stop *bool) int16 {
nodeCount++
if *stop {
return alpha
}
var standPat int16
found, _, evalresult, _, ntype := transtable.Get(b)
if found && ntype == transtable.Exact {
standPat = evalresult
} else {
standPat = eval.Evaluate(b)
transtable.Put(b, 0, standPat, 0, transtable.Exact)
}
if standPat >= beta {
return beta
}
if alpha < standPat {
alpha = standPat
}
moves := b.GenerateLegalMoves()
if len(moves) == 0 { // TODO(dylhunn): What about stalemate?
return negInf
}
for _, move := range moves {
if !isCapture(move, b) {
continue
}
unapply := b.Apply(move)
score := -quiesce(b, -beta, -alpha, stop)
unapply()
if score >= beta {
return beta
}
if score > alpha {
alpha = score
}
}
return alpha
}
func isCapture(m dragontoothmg.Move, b *dragontoothmg.Board) bool {
toBitboard := (uint64(1) << m.To())
return (toBitboard&b.White.All != 0) || (toBitboard&b.Black.All != 0)
}
如果我没看错你的代码,你正在搜索所有的捕获。为了节省工作,您可以做的是修剪无望的捕获动作。事实证明,动作差到可以跳过它们是很常见的,所以该技术非常安全。
比如看看这个位置:
芬:rnbqkbnr/pppppppp/8/8/8/8/1PP1PPP1/RNBQKBNR w KQkq - 0 1
共有三个捕获:
- Rxa7
- Qxd7+
- Rxh7
让我们假设引擎首先尝试对女王进行捕获动作。黑方有四种反吃法,但其中任何一种都可能导致截断。
例如,黑棋下Bxd7。现在白方在结果位置有两个捕获,Rxa7 或 Rxh7。
在这里,大多数引擎会认识到白色已经在 material 中退却(与 beta 相比),即使捕获棋子也无济于事。因此,这两个新车捕获都不太可能导致截止。
在这里,您当前的搜索仍然会继续搜索这些着法。检测此类情况并跳过这些动作将节省大量工作。
还有进一步的优化。例如,具有 static exchange evaluation 的强大引擎会立即看到 Qxd7 将赢得一兵,但会失去皇后。由于这是一个糟糕的交易,引擎可以立即跳过此移动。其他两个新车捕获也是如此。
不过,与往常一样,需要权衡取舍。如果你过于激进地修剪,你最终也会修剪好的动作。一般来说,我会建议多花点时间在普通搜索上,而不是在静止搜索上,所以激进的剪枝应该没问题。