还有众多基于Alpha-Beta算法的派生、变种算法)在程序中直接借鉴了Alpha-Beta搜索算法并辅以了历史启发。本节先介绍Alpha-Beta搜索算法:在中国象棋里,双方棋手获得相同的棋盘信息。他们轮流走棋,目的就是将死对方,或者避免被将死。Р由此,可以用一棵“博弈树”(图2)来表示下棋的过程——树中每一个结点代表棋盘上的一个局面,对每一个局面(结点)根据不同的走法又产生不同的局面(生出新的结点),如此不断直到再无可选择的走法,即到达叶子结点(棋局结束)。中国象棋的博弈树的模型大概如下图所示,可以把其中连接结点的线段看作是着法,不同的着法自然产生不同的局面。Р图 2博弈树Р该树包含三种类型的结点:Р奇数层的中间结点(以及根结点),表示轮到红方走棋;Р偶数层的中间结点,表示轮到黑方走棋;Р叶子结点,表示棋局结束。Р现在让计算机来下中国象棋,它应当选择一步对它最有利的着法(最终导致它取胜的着法)。获得最佳着法的方法就是“试走”每一种可能的着法,比较它们所产生的不同后果,然后从中选出能够产生对自己最有利的局面的着法。Р结合上面所讲的博弈树,若给每个结点都打一个分值来评价其对应的局面(这一任务由后面所讲的局面评估来完成),那么可以通过比较该分值的大小来判断局面的优劣。假定甲乙两方下棋,甲胜的局面是一个极大值(一个很大的正数),那么乙胜的局面就是一个极小值(极大值的负值),和棋的局面则是零值(或是接近零的值)。如此,当轮到甲走棋时他会尽可能地让局面上的分值大,相反轮到乙走棋时他会选尽可能地让局面上的分值小。反映到博弈树上,即如果假设奇数层表示轮到甲方走棋,偶数层表示轮到乙方走棋。那么由于甲方希望棋盘上的分值尽可能大,则在偶数层上会挑选分值最大的结点——偶数层的结点是甲走完一步棋之后的棋盘局面,反映了甲方对棋局形势的要求。同样道理,由于乙方希望棋盘上的分值尽可能小,那么在奇数层上
全文预览