《算法的乐趣》第六十九节

本节介绍博弈树搜索的基本方法。由于完整博弈树节点数极其庞大（如围棋可达10^170），实际应用中通常限定搜索深度，到达深度即评估棋局。

本节介绍博弈树搜索的基本方法。由于完整博弈树节点数极其庞大（如围棋可达10^170），实际应用中通常限定搜索深度，到达深度即评估棋局。

核心算法是极大极小值搜索：MAX方总是选择评估值最大的落子，MIN方则选择让对手收益最小的落子，两层交替直至叶子节点。负极大值算法通过将返回值取负，统一了两种节点的搜索逻辑。为提高效率，"α-β"剪枝算法维护[α,β]窗口，当α≥β时剪去无关分支，分为α剪枝和β剪枝两种情况。

估值函数将棋局量化为数字，考虑棋子战力、空间、机动性等因素，其权重组合决定算法水平，通常需在速度与质量间平衡。