Chess Quiescence Поиск слишком обширен

За последний месяц я создавал простой шахматный движок на С# и добился в этом хорошего прогресса. Он использует простой алгоритм альфа-бета.

Чтобы исправить 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;

    }

person xXliolauXx    schedule 30.06.2015    source источник
comment
Вы смотрели на этот вопрос SO?   -  person DeadZone    schedule 30.06.2015
comment
Один комментарий, не относящийся к стационарному поиску: для такой игры, как шахматы, обычно намного изменить ту же доску, а затем отменить ход после этого, а не копировать всю доску для каждой проверки.   -  person 500 - Internal Server Error    schedule 01.07.2015
comment
@DeadZone: я просмотрел связанный пост, но проблема, похоже, заключалась в том, что парень генерировал все ходы в поиске покоя (чего я не делаю).   -  person xXliolauXx    schedule 01.07.2015
comment
@Внутренняя ошибка сервера: спасибо за предложение, оно может оказаться полезным позже. Прямо сейчас я не думаю, что имеет значение, копирую ли я Board, так как я рассчитал, что могу копировать Board около 25 000 000 раз в секунду (в то время как весь мой движок в настоящее время просматривает 720 000 узлов/сек.   -  person xXliolauXx    schedule 01.07.2015


Ответы (1)


Я не знаком с английской терминологией - является ли HitMove ходом, при котором вы убираете фигуру с доски?

В этом случае мне кажется, что вы используете GetAllHitMoves, чтобы получить список «шумных» ходов для поиска покоя, которые затем оцениваются дальше, чем обычные 3 или 6 слоев. Однако это вызывается рекурсивно, поэтому вы оцениваете это снова и снова, пока остаются возможные оставшиеся HitMoves. Предоставление предела вашему поиску покоя должно решить ваши проблемы с производительностью.

Что касается выбора лимита для поиска покоя - в вики говорится:

Современные шахматные движки могут искать определенные ходы в 2-3 раза глубже минимума.

person H W    schedule 01.07.2015
comment
Спасибо, кажется, это то, что я искал. Я ограничил поиск в режиме покоя до 4 слоев, и поиск снова стал намного быстрее! Я тогда отмечу твой ответ. - person xXliolauXx; 01.07.2015
comment
Редактировать: Не могли бы вы сказать мне, насколько сильно ограниченный поиск в режиме покоя влияет на результат поиска? ты - person xXliolauXx; 01.07.2015
comment
В каком отношении? Установив предел поиска покоя, вы, очевидно, снова можете получить какой-то эффект горизонта вблизи предела покоя. Однако вы не сможете избежать этого, если не оцените каждый возможный ход (близко к тому, что вы делали раньше). - person H W; 01.07.2015
comment
Еще одно замечание относительно производительности: вы переоцениваете всю доску каждый ход или где-то храните свои расчеты, чтобы вам нужно было оценивать только один ход из каждого узла? Если вы сохраните свои результаты, вы сможете увеличить глубину слоя, сохранив время выполнения примерно на 2-3 минуты (или просто уменьшите время НАМНОГО). - person H W; 01.07.2015
comment
@ H W: 1) Верно, меня немного беспокоит эффект горизонта, возникающий из-за предела поиска. Но, похоже, этого еще не произошло. 2) Я думаю, вы имеете в виду хеш-таблицы/таблицы транспонирования, чтобы сортировать ходы? Это определенно один из следующих шагов, но мне придется изучить его немного подробнее. Спасибо за предложение. - person xXliolauXx; 01.07.2015