象棋蛮力搜索算法最基本的就是极大极小搜索,这种方法适用于所有双方都可看到局面的棋,比如象棋、围棋、五子棋,不适用于扑克、麻将等看不到对方牌的游戏。
算法的原理是每一方走子都为了让自己局面最优。
对于中国象棋,最简单的是代码中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走法表示搜索到的最好走法太好,上一步对方不会这么走,这个搜索也是无效的