略,目前应用于计算机博弈的搜索算法一般可分为三类:(l)穷尽搜索(ExhaustiveSearch),这种搜索是没有抛弃任何可能成为最佳路径的搜索,不存在风险,得到的最佳走法肯定是在现有评估函数下应该得到的,例如极大极小值搜索、α-β剪枝搜索及其变种等。(2)选择性搜索(SelectiveSearch),即裁剪搜索,这种搜索略去对一些着法的搜索,冒着有可能漏掉最佳走法的风险,而换来局部更深的搜索深度。中国象棋中最常用裁剪算法是空着裁剪(NullMove)等。(3)启发式搜索(Heuristicsearch)利用象棋领域的知识(启发信息)设计搜索算法,着重对走法排序,以简化和加快搜索过程。中国象棋中的启发算法有历史启发、杀手启发、置换表等。搜索算法对于整个下棋引擎来说都是至关重要的。它如同程序的心脏,驱动着整个程序。搜索算法的好坏直接影响着程序执行的效率(从某种角度上,它影响着计算机的下棋水平。因为,计算机必须在有限的时间内完成思考,搜索速度快意味着在相同的时间内程序可以“看”得更远,“想”的更多)。关于棋类对弈程序中的搜索算法,已有成熟的Alpha-Beta搜索算法以及其它一些辅助增强算法(还有众多基于Alpha-Beta算法的派生、变种算法)。我们在程序中直接借鉴了Alpha-Beta搜索算法并辅以历史启发。本节先介绍Alpha-Beta搜索算法:在中国象棋里,双方棋手获得相同的棋盘信息。他们轮流走棋,目的就是吃掉对方的将或帅,或者避免自己的将或帅被吃。图3-1博弈图又此,可以用一棵“博弈树”来表示下棋的过程——树中每一个结点代表棋盘上的一个局面,对每一个局面(结点)根据不同的走法又产生不同的局面(生出新的结点),如此不断进行下去直到再无可选择的走法,即到达叶子结点(棋局结束)。中国象棋的博弈树的模型大概,可以把其中连接结点的线段看作是着法,不同的着法自然产生不同的局面。
全文预览
