象棋AI算法（一）

参考文献：http://www.xqbase.com/computer/search_minimax.htm

http://www.xqbase.com/computer/search_alphabeta.htm

最近想做一个象棋游戏，但是AI把我难住了。这是这几天的成果：

象棋程序通过使用“搜索”函数来寻找着法。搜索函数获得棋局信息，然后寻找对于程序一方来说最好的着法。

一，最小-最大搜索Minimax Search

首先：最小与最大是相对的，且只针对一方，AI中即为有利于AI 
象棋AI中的最小最大搜索：  简单来讲就是该AI走了，穷举这个过程中对于AI来说的最佳（最大）走法对于我来说最差（最小）的走法。
而这个走法就是我们所要找的AI的最佳走法。

这个过程就跟你与别人下象棋时猜测对方走法然后下棋一样，只不过，电脑可以多想几步，这里的步数就是下面的搜索深度

举个例子：假设搜索深度为4. 那么AI走一步（他认为最佳，记为步数1，搜索深度4）时，会先考虑如果他走这一步1，那我肯定会走相对于这一步来讲
最差的一步2（搜索深度3），然后ai再假设出根据步数2来讲的最佳步数3（搜索深度2），继续考虑我根据步数3走的最差步数4（搜索深度1）
接下，搜索深度为0，给出此时的局面评价函数
             

一个MAX节点的Alpha值等于其后继节点当前最大的最终倒推值，一个MIN节点的Beta值等于其后继节点当前最小的最终倒推值
第二个值是beta，即对于对手来说最坏的值，如果某个着法的结果大于或等于Beta，那么整个结点就作废了
if (val >= beta) {return beta;}
　　　
　　

AlphaBetaint alphaint beta
-AlphaBeta-beta, -alpha
if (val >= beta) {
return beta;
　　}

负无穷大即Alpha，以及正无穷大即Beta：

可能的弱点：

这个算法严重依赖于着法的寻找顺序。如果你总是先去搜索最坏的着法，那么Beta截断就不会发生，因此该算法就如同最小–最大一样，效率非常低。该算法最终会找遍整个博弈树，就像最小–最大算法一样。　

所以，生成全部着法后，排序很重要~ ~ ~

结语：

算法原理方面就到此为止了，比较浅显，大神勿喷~

文章知识点与官方知识档案匹配，可进一步学习相关知识算法技能树首页概览35128 人正在系统学习中