现在的位置: 首页 > 综合 > 正文

电脑象棋开发-极大极小搜索

2018年05月04日 ⁄ 综合 ⁄ 共 958字 ⁄ 字号 评论关闭

象棋蛮力搜索算法最基本的就是极大极小搜索,这种方法适用于所有双方都可看到局面的棋,比如象棋、围棋、五子棋,不适用于扑克、麻将等看不到对方牌的游戏。

算法的原理是每一方走子都为了让自己局面最优。

对于中国象棋,最简单的是代码中SearchFull函数,分析如下:

假设人(红)机(黑)对战,红方走子以后,根据不同计算深度,黑方做如下判断:

1步:找最好的走法

电脑计算当前所有可走路线以后,取局面最好的走法,这种搜索方法搜到的结果是炮2进7打底马(c454)

结果Search.nHistoryTable[54c4] += 1*1

Search.mvResult = c454

这个搜索只有1个循环,下一层迭代直接返回估计值,在这个循环中beta一直是10000,alpha不断更新到当前搜索到的最大值

2步:遍历每一种走法,对于每一种走法,对方都会选择让你的局面最差的走法,选择最好的走法

电脑首先计算当前所有可走线路:a1, a2, ...

对于每一步,计算下一步红方可能的走法,比如对于a1,考虑红方可能走b1, b2, ...

一个典型值是这样的:

alpha      beta

-10000   10000

下一层 -10000 10000

最上层循环的第二次alpha更新为-25,也就是说黑方走了这一步棋以后,红方再走一步,黑方局面最大值是-25

下一层 -10000 25,这一步如果红方搜索到局面值>25,那么说明黑方会选择前面一步走法,而不会走这一步,可以直接返回(即截断),搜索完以后alphabeta为8,25

最上一层循环下一次alpha更新为-8,

以下循环

总的来说alpha-beta算法有2个重点:

1. 对于搜索树中的兄弟节点,搜索过程中alpha值不断增加

2. 对于节点的孩子节点,alpha、beta反转

alpha表示当前搜索到的最佳值,每一个具体的搜索步骤搜到的值可能比alpha小

beta表示对手目前为止搜索到的最佳值,如果搜索到的结果比beta好,则对手不会在上一层选择这一步,可以直接返回

alpha-beta算法搜索的有效性是自低向上保证的,所以这种搜索在没有错误的基础上增加了搜索速度

搜索的每一步,alpha 走法表示搜索到的最好走法评估值比alpha小,这个搜索要抛弃

beta走法表示搜索到的最好走法太好,上一步对方不会这么走,这个搜索也是无效的

抱歉!评论已关闭.