《算法的乐趣》第七十三节

本节首先介绍在黑白棋搜索中应用走法排序启发，依据此前统计的每种走法的好值（即对手行动力的负值）对走法排序，以便更早建立准确的剪枝窗口，提高剪枝效率。

本节首先介绍在黑白棋搜索中应用走法排序启发，依据此前统计的每种走法的好值（即对手行动力的负值）对走法排序，以便更早建立准确的剪枝窗口，提高剪枝效率。随后实现带α-β剪枝的负极大值搜索算法，并引入置换表：搜索前先查表，若存在深度足够的条目则直接使用其精确值或上下界值来更新剪枝窗口；搜索结束后再按结果更新窗口并回写置换表。将棋盘模型、估值函数与搜索算法接入棋类框架后得到黑白棋对战程序，测试表明搜索深度每多一层优势明显，深度4层对3层几乎全胜，而较强AI在终局可达18～22层。

接着进入五子棋部分。五子棋在15×15棋盘上轮流落子，先成五子连线者胜，其棋型分为“冲”（两端有界）和“活”（两端无界）两类，如冲四、活四、活三、跳活三等。因先手优势明显且存在必胜走法，比赛设有“禁手”规则，禁止黑棋走四四、三三、长连等棋型，走禁手即判负。因此五子棋AI除搜索与估值外，还需识别棋型并在生成走法时过滤禁手。

最后建立棋盘数学模型：沿用黑白棋的WarrenSmith一维数组模型，演示程序改用9×9小棋盘，需111个数组元素（81个位置加30个标志位），并相应调整方向步进量与坐标换算关系。该模型便于实现连珠检测——从落子点沿四条线正反向统计同色棋子，总数不小于5即判胜；也便于棋型识别，通过定义起点与步进量组成的“线”来遍历横、竖、斜四个方向，为后续估值函数打下基础。