8

上个月,我一直在用 c# 创建一个简单的国际象棋引擎,并取得了一些不错的进展。它使用简单的 Alpha-Beta 算法。

为了纠正地平线效应,我尝试实现静止搜索(并且在它起作用之前失败了几次)。引擎的力量似乎从那开始变得安静了一点,但速度非常慢!

以前,我可以在大约 160 秒内搜索到 6 层深度(处于游戏中期状态的某个地方),使用静止搜索,计算机需要大约 80 秒才能在搜索深度 3 上移动!

暴力节点计数器在深度 3 处约为 20000 个节点,而静态节点计数器高达 2000 万!

由于这是我的第一个国际象棋引擎,我真的不知道这些数字是否正常,或者我是否可能在我的静止算法中犯了错误。如果有经验的人能告诉我BF节点/静止节点的通常比率是多少,我将不胜感激。

顺便说一句,只是看一下:(每当 searchdepth 为 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;

    }
4

1 回答 1

2

我不熟悉英文术语 - 是HitMove从板上删除一块的举动吗?

在那种情况下,在我看来,您似乎使用GetAllHitMoves获取静止搜索的“嘈杂”移动列表,然后对这些移动进行比通常的 3 层或 6 层更进一步的评估。虽然这被称为递归,所以只要有可能的 HitMoves 剩余,您就会一遍又一遍地评估它。限制您的静止搜索应该可以解决您的性能问题。

至于选择静止搜索的限制 - wiki 状态:

现代国际象棋引擎可能会搜索比最小值深 2 或 3 倍的某些动作。

于 2015-07-01T07:08:29.223 回答