За последний месяц я создавал простой шахматный движок на С# и добился в этом хорошего прогресса. Он использует простой алгоритм альфа-бета.
Чтобы исправить Horizon-Effect, я попытался реализовать Quiescence Search (и несколько раз потерпел неудачу, прежде чем это сработало). Мощность двигателя, кажется, немного улучшилась от этого, но он ужасно медленный!
Раньше я мог выполнять поиск на глубине 6 слоев примерно за 160 секунд (где-то в середине игры), с поиском в состоянии покоя компьютеру требуется около 80 секунд, чтобы сделать ход на глубине поиска 3!
Счетчик узлов грубой силы составляет около 20000 узлов на глубине 3, в то время как счетчик покоящихся узлов достигает 20 миллионов!
Поскольку это мой первый шахматный движок, я действительно не знаю, нормальные ли эти числа или я мог ошибиться в своем алгоритме покоя. Я был бы признателен, если бы кто-то более опытный мог сказать мне, каково обычное соотношение узлов BF/Quiescent.
Кстати, просто чтобы взглянуть на: (этот метод вызывается деревом BF всякий раз, когда глубина поиска равна 0)
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;
}