Quiescense 搜索问题

Question

我目前正在使用国际象棋库在 python 中开发国际象棋引擎。我尝试使用国际象棋编程 wiki 中的伪代码来实现静止搜索，但是一旦我在测试位置上运行代码，搜索就会花费很长时间（例如 10-20 分钟）。

我试图让它打印在静止搜索期间搜索的动作，它只是打印连续的许多动作流。 这是我的代码：

    def search_all_captures(self, alpha, beta):

        evaluation = self.evaluate()
        if evaluation >= beta:
            return beta
        alpha = max(alpha, evaluation)

        moves = [capture for capture in self.board.generate_legal_captures()]

        move_dict = {}


        # Ordering moves
        for move in moves:
            guess = 0
            move_piece = self.board.piece_at(move.from_square)
            captured_piece = self.board.piece_at(move.to_square)

            if captured_piece:
                guess += 10 * vals_dict[captured_piece.piece_type] - vals_dict[move_piece.piece_type]

            if move.promotion:
                guess += vals_dict[move.promotion]

            if self.board.attackers(1 - self.color, move.to_square):
                for attacker in self.board.attackers(1 - self.color, move.to_square):
                    piece = self.board.piece_at(attacker).piece_type
                    guess -= vals_dict[piece]

            move_dict[move] = guess

        moves.sort(reverse=True, key=lambda move: move_dict[move])

        for move in moves:
            print(move)
            self.board.push(move)
            evaluation = -self.search_all_captures(-beta, -alpha)
            self.board.pop()

            if evaluation >= beta:
                return beta

            alpha = max(alpha, evaluation)

        return alpha

以下是该位置的 FEN 字符串：r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w - - 0 1

Answer 1

我会尝试通过手工计算来回答基础知识，但我已经很长一段时间没有认真做这些事情了，启发式确实会改变。您的基本立场是：

静止只会考虑要移动的玩家可以获得物质优势或至少不会失去任何优势的移动（以便处理所有中立交换）。静止搜索通常不会考虑高价值的棋子牺牲——事实上，它的存在是为了防止引擎扔掉棋子，只是为了再多一步延迟不可避免的将死。

我认为对你的代码做一些小的改变就足够了，这样它只探索递归捕获当猜测> = 0时玩家在移动中获得净物质增益的行

if move_dict[move] >= 0 :
   evaluation = -self.search_all_captures(-beta, -alpha)

我看不出它在哪里识别检查中的 K，这也是非静态状态。

正在考虑的白人立即捕获行动具有净或零物质收益：

1a. BXB (Ba6 is en prise) +2.5 (nonQi)
1b. d5xe6  +0
1c. g2xh3  +0

1a 后。黑人反应捕捉是

1d. ... b4xN +1.5 (nonQi)
1e. ... e6xd5 +0
1f. ... h3xg2 +0
1g. ... BxB   +0

并且很明显，除非黑c3的N步棋总是有有利的吃子杀手棋来反驳1b，1c。

1天后。白人捕获的是

2h. b2xc3 +1 (Qi) - no threats to capturing piece (*)
2i. Bxc3  +1 (Qi)
2j. d5xe6 +0 (nonQ)
2k. g2xh3 +0 (nonQ)

但是 2h、2j 中的任何一个都足以修剪该分支的其余部分。 (*) 但是，黑人回复 2. ... e6xd5 允许 3. ... QxN （这就是为什么探索零和互换是个好主意）

如果 K 处于受制状态或者对手有任何选择来占领并立即获得物质收益，那么该位置就不是静止的。因此，任何受到较低价值棋子或棋子威胁的棋子也会使其变得非静止。有时，典当捕获可以生成发现检查，因此通常值得探索（其中一些）它们，但这是一个品味问题。

一个更简单的选择是考虑每个方块的交换值。 IOW 是否存在弱点，移动的玩家只需按价值递增的顺序交换棋子和棋子即可赢得材料。

如果每个层表有一个杀手级动作，那么在进行动作生成之前几乎总是值得尝试一下（特别是如果它是合法捕获）。

我希望更新的人很快就会纠正我分析中的任何错误，但这应该给你足够的时间来测试你的代码。目标是以尽可能少的努力进行准确评估。