Skip to content

sunfish

Sunfish主要采用了以下几种算法来实现其国际象棋AI功能:

  1. 极小化极大搜索(Minimax Search): 这是Sunfish决策的核心算法。它通过模拟双方的最佳走法,在博弈树中搜索最优解。
  2. Alpha-Beta剪枝: 在极小化极大搜索的基础上,使用Alpha-Beta剪枝技术来减少不必要的搜索,提高效率。
  3. 静态评估函数: 用于评估棋局优劣,考虑了棋子价值、位置等因素。
  4. 迭代加深(Iterative Deepening): 通过逐步增加搜索深度,在有限时间内找到较好的走法。
  5. 置换表(Transposition Table): 缓存已经计算过的局面,避免重复搜索。

Sunfish的代码结构

Sunfish的111行代码大致可以分为以下几个部分:

  1. 棋盘表示: 使用一个120字符的字符串来表示10x12的棋盘。
  2. 走法生成: 根据当前局面生成所有合法走法。
  3. 评估函数: 对局面进行静态评估。
  4. 搜索函数: 实现极小化极大搜索和Alpha-Beta剪枝。
  5. 主循环: 处理输入输出,调用搜索函数选择最佳走法。

搜索算法

    def search(self, history):
        """Iterative deepening MTD-bi search"""
        self.nodes = 0
        self.history = set(history)
        self.tp_score.clear()

        gamma = 0
        # In finished games, we could potentially go far enough to cause a recursion
<div markdown="1" style="margin-top: -30px; font-size: 0.75em; opacity: 0.7;">
:material-circle-edit-outline: 约 458 个字 :fontawesome-solid-code: 24 行代码 :material-clock-time-two-outline: 预计阅读时间 2 分钟
</div>
        # limit exception. Hence we bound the ply. We also can't start at 0, since
        # that's quiscent search, and we don't always play legal moves there.
        for depth in range(1, 1000):
            # The inner loop is a binary search on the score of the position.
            # Inv: lower <= score <= upper
            # 'while lower != upper' would work, but it's too much effort to spend
            # on what's probably not going to change the move played.
            lower, upper = -MATE_LOWER, MATE_LOWER
            while lower < upper - EVAL_ROUGHNESS:
                score = self.bound(history[-1], gamma, depth, can_null=False)
                if score >= gamma:
                    lower = score
                if score < gamma:
                    upper = score
                yield depth, gamma, score, self.tp_move.get(history[-1])
                gamma = (lower + upper + 1) // 2

迭代加深的 MTD-bi 搜索算法是一种用于国际象棋引擎的搜索算法，它结合了迭代加深和 MTD-bi（Memory-enhanced Test Driver with bounded interval）技术，以高效地找到最佳移动

迭代加深（Iterative Deepening）

逐步增加搜索深度，从浅到深进行多次搜索。每次搜索的结果用于指导下一次更深层次的搜索

MTD-bi 算法

基于边界的搜索算法，它通过反复调用一个边界搜索函数（如 bound 方法）来缩小评分区间，最终找到最佳评分

核心思想是通过二分搜索逐步逼近真实评分