《算法的乐趣》第七十节

置换表是一种以空间换时间的辅助算法，用于提高启发式搜索效率。

置换表是一种以空间换时间的辅助算法，用于提高启发式搜索效率。它存储已搜索棋局的结果（含评估值、搜索深度、落子方法等），搜索时先查表，命中即可直接使用或缩小搜索窗口，避免重复搜索。评估值分精确值、α值、β值三种；若表中搜索深度不小于所需深度，可直接采用结果。置换表通常用哈希表组织，棋类多采用Zobrist哈希算法。替换原则有深度优先替换和始终替换两种，各有优缺点，常用双置换表结合二者，也有分类置换表等扩展方案。

开局库和终局库是存储经典开局、残局走法的数据库。开局和终局阶段棋子少，启发式搜索易失效，AI直接从库中取已知走法，直到库中无对应局面才开始真正搜索；进入中局再用搜索算法。终局库因变化更多，规模远大于开局库。

井字棋是3×3九宫格的简单博弈游戏，用一维长度9的数组表示棋盘，数组值为玩家ID或空。棋局状态由棋盘数组、当前玩家ID和评估算子构成。判断三子一线时，事先把横、竖、斜共8种连线的下标整理成表，直接查表即可，避免复杂的下标计算，用数据表实现一致性处理。