计算机博弈程序——搜索引擎

 

搜索算法

对博弈树的搜索，根据估价函数计算的各种局面的估值，找到最己方最有利的着法

 

1.基础：

极大极小值算法（Minimax Algorithm）

深度优先搜索（Depth First Search）

负极大值算法（Negamax Algorithm）

 

2.改进：

 

1）Alpha-Beta搜索

思路：利用剪枝大大减少搜索节点的数目

大概减少至节点数目平方根的两倍

伪代码（采用负极大值形式）：

 

2）Fail-soft Alpha-Beta搜索

思路：限制Alpha-Beta搜索的alpha beta值，减去更多节点，并且一旦搜索失败，返回当前值，避免了搜索失败无法获得任何信息而重新搜索的情况

效率接近Alpha-Beta搜索

伪代码：

 

3）Aspiration Search 渴望搜索：

思路：猜测搜索结果在某个值附近，从而在给出的一个小范围内运用Alpha-Beta搜索，并且在fail high 和fail low时调整该范围，属于一种窄窗搜索

猜值是提高效率的重要问题，一般利用浅层节点的值

真实效率存在争议

伪代码：

 

4）Minimal Window Search/PVS 极小窗口搜索

思路：第一次以完整窗口搜索得到窗中的值，后继搜索每次以一个极小的窗口（v,v+1）建立极小的搜索树，窄窗搜索

也叫PVS和NegaScout搜索算法

搜索深度为5时，大约是Alpha-Beta效率的250%

 

5）MTD算法

思路：利用空窗Alpha-Beta搜索的高剪枝率和边界，通过fail high和fail low使窗口上下界多次逼近。对于多次搜索的节点采用置换表提高效率。结合了空窗探测和内存增强，因此称为Memory-enhanced Test Driver with node n and value f—MTD

初始值和置换表对搜索效率有决定作用，还与估值精度有关，估值精度粗较好

 

6）SSS*算法

一种状态空间的最佳优先算法

虽然搜索节点数目少于Alpha-Beta搜索但是缺点明显：

难以理解，内存需求太大，节点队列插入删除费时，已证明与Alpha-Beta+TT等效

 

3.算法增强手段

 

1）Transposition Table置换表

记录搜索过的节点，免于过多重复搜索

需要：查找速度非常快，最好类似随机存取

      记录的储存也要快，不能有排序等额外操作

      有限空间内实现

实现：Hash表

结构示例:

Struct HASHITEM{

       Int64 checksum;  //哈希值，非常重要！

      Int depth ;

       Enum{exact,lower_bound,upper_bound

}entrytype;

Double eval;

}hashtable[SIZE];

深入考虑的问题：

清除哈希表：采取不清空和覆盖

哈希表层次：对于六子棋，相同局面的棋子数目必然相同，因此它们一定在同一层！

叶节点：层次越深，命中率越高，浅层搜索性能降低

散列度和尺寸：Zobrist哈希技术。表尺寸曽一倍，性能提高7%

 

2）History Heuristic历史启发

由于节点排列顺序对基于Alpha-Beta搜索的算法性能影响巨大，，可以根据已搜索的部分对节点顺序进行调整，找到一个好走法，对其历史得分做增量，将走法序列按照增量排序，

需要：将走法映射到历史得分数组

       确定适当权值

实现：用二维数组记录走法起始和终点位置，用一个数表示走法在数组中的位置，这个数有移动前和移动后两部分Bit表示

说明：历史启发不依赖特定的棋类知识，确定适当映射和增量因子即可使用任何棋类

考虑的问题：

如何对历史记录进行排列：由于元素较少，且排序次数较少，各种算法差别不大，冒泡亦可

 

 

3）Killer Heuristic 杀手启发

为每一层记录引发剪枝最多的走法（杀手），下次搜索同样深度，如杀手走法存在，优先搜索

同样不依赖具体棋类知识

 

 

4）Iterative Deepening迭代深化

不同时期搜索的消耗是不同的，比如残局可能搜索更深，通过迭代深化来控制时间而不是深度来增加可能的效率。虽然有重复，但是更快速！

伪代码：

 

以下是各种算法和增强手段组合的时间空间性能