国际象棋静止搜索过于广泛
Chess Quiescence Search ist too extensive
上个月我一直在用 c# 创建一个简单的国际象棋引擎,并取得了一些不错的进展。它使用简单的 Alpha-Beta 算法。
为了更正 Horizon-Effect,我尝试实施静态搜索(但失败了好几次才成功)。发动机的强度似乎从那以后安静了一点,但速度非常慢!
以前,我可以在大约 160 秒内搜索到 6 层深度(处于游戏中期状态),使用静态搜索,计算机需要大约 80 秒才能在搜索深度 3 上移动!
brute-force深度3的节点数在20000左右,而静态节点数高达2000万!
由于这是我的第一个国际象棋引擎,我真的不知道这些数字是否正常,或者我是否在 Quiescence-Algorithm 中犯了错误。如果更有经验的人能告诉我 BF Nodes/Quiescent 节点的通常比例是多少,我将不胜感激。
顺便说一句,看看:
(只要搜索深度为0,BF树就会调用此方法)
public static int QuiescentValue(chessBoard Board, int Alpha, int Beta)
{
QuiescentNodes++;
int MinMax = Board.WhoseMove; // 1 = maximierend, -1 = minimierend
int Counter = 0;
int maxCount;
int tempValue = 0;
int currentAlpha = Alpha;
int currentBeta = Beta;
int QuietWorth = chEvaluation.Evaluate(Board);
if(MinMax == 1) //Max
{
if (QuietWorth >= currentBeta)
return currentBeta;
if (QuietWorth > currentAlpha)
currentAlpha = QuietWorth;
}
else //Min
{
if (QuietWorth <= currentAlpha)
return currentAlpha;
if (QuietWorth < currentBeta)
currentBeta = QuietWorth;
}
List<chMove> HitMoves = GetAllHitMoves(Board);
maxCount = HitMoves.Count;
if(maxCount == 0)
return chEvaluation.Evaluate(Board);
chessBoard tempBoard;
while (Counter < maxCount)
{
tempBoard = new chessBoard(Board);
tempBoard.Move(HitMoves[Counter]);
tempValue = QuiescentValue(tempBoard, currentAlpha, currentBeta);
if (MinMax == 1) //maximierend
{
if (tempValue >= currentBeta)
{
return currentBeta;
}
if (tempValue > currentAlpha)
{
currentAlpha = tempValue;
}
}
else //minimierend
{
if (tempValue <= currentAlpha)
{
return currentAlpha;
}
if (tempValue < currentBeta)
{
currentBeta = tempValue;
}
}
Counter++;
}
if (MinMax == 1)
return currentAlpha;
else
return currentBeta;
}
我不熟悉英文术语 - HitMove
是从棋盘上移除棋子的一步吗?
在那种情况下,在我看来,您使用 GetAllHitMoves
来获取静止搜索的 "noisy" 移动列表,然后比通常的 3 或 6 层进一步评估。不过,这是递归调用的,所以只要有可能的 HitMoves 剩余,你就会一遍又一遍地评估它。限制您的静态搜索应该可以解决您的性能问题。
关于选择静态搜索的限制 - wiki 状态:
Modern chess engines may search certain moves up to 2 or 3 times deeper than the minimum.
上个月我一直在用 c# 创建一个简单的国际象棋引擎,并取得了一些不错的进展。它使用简单的 Alpha-Beta 算法。
为了更正 Horizon-Effect,我尝试实施静态搜索(但失败了好几次才成功)。发动机的强度似乎从那以后安静了一点,但速度非常慢!
以前,我可以在大约 160 秒内搜索到 6 层深度(处于游戏中期状态),使用静态搜索,计算机需要大约 80 秒才能在搜索深度 3 上移动!
brute-force深度3的节点数在20000左右,而静态节点数高达2000万!
由于这是我的第一个国际象棋引擎,我真的不知道这些数字是否正常,或者我是否在 Quiescence-Algorithm 中犯了错误。如果更有经验的人能告诉我 BF Nodes/Quiescent 节点的通常比例是多少,我将不胜感激。
顺便说一句,看看: (只要搜索深度为0,BF树就会调用此方法)
public static int QuiescentValue(chessBoard Board, int Alpha, int Beta)
{
QuiescentNodes++;
int MinMax = Board.WhoseMove; // 1 = maximierend, -1 = minimierend
int Counter = 0;
int maxCount;
int tempValue = 0;
int currentAlpha = Alpha;
int currentBeta = Beta;
int QuietWorth = chEvaluation.Evaluate(Board);
if(MinMax == 1) //Max
{
if (QuietWorth >= currentBeta)
return currentBeta;
if (QuietWorth > currentAlpha)
currentAlpha = QuietWorth;
}
else //Min
{
if (QuietWorth <= currentAlpha)
return currentAlpha;
if (QuietWorth < currentBeta)
currentBeta = QuietWorth;
}
List<chMove> HitMoves = GetAllHitMoves(Board);
maxCount = HitMoves.Count;
if(maxCount == 0)
return chEvaluation.Evaluate(Board);
chessBoard tempBoard;
while (Counter < maxCount)
{
tempBoard = new chessBoard(Board);
tempBoard.Move(HitMoves[Counter]);
tempValue = QuiescentValue(tempBoard, currentAlpha, currentBeta);
if (MinMax == 1) //maximierend
{
if (tempValue >= currentBeta)
{
return currentBeta;
}
if (tempValue > currentAlpha)
{
currentAlpha = tempValue;
}
}
else //minimierend
{
if (tempValue <= currentAlpha)
{
return currentAlpha;
}
if (tempValue < currentBeta)
{
currentBeta = tempValue;
}
}
Counter++;
}
if (MinMax == 1)
return currentAlpha;
else
return currentBeta;
}
我不熟悉英文术语 - HitMove
是从棋盘上移除棋子的一步吗?
在那种情况下,在我看来,您使用 GetAllHitMoves
来获取静止搜索的 "noisy" 移动列表,然后比通常的 3 或 6 层进一步评估。不过,这是递归调用的,所以只要有可能的 HitMoves 剩余,你就会一遍又一遍地评估它。限制您的静态搜索应该可以解决您的性能问题。
关于选择静态搜索的限制 - wiki 状态:
Modern chess engines may search certain moves up to 2 or 3 times deeper than the minimum.