前面说了最小最大原理，为什么要最小最大原理？为什么要搜索？我们可以更简单的看对弈这件事儿，下棋的时候，从一开始到结束，每当我要走棋时，我会考虑怎么走？有N种可行走法，但只能选一种，换个方式想这问题，人工智能不过是作一种‘选择’，而这里的‘选择’要能促使你最终赢棋！

可以选择的前提是要能分出谁高谁低，哪步着法臭，哪步着法妙，于是就需要要一个估值函数Eval(p),p是局面，也就是由这个评价函数分出哪个局面（或者着法，着法可以看成下一个局面）更好，如果Eval(p1)<Eval(p2)，我们就有理由说，或者大胆地说，p2比p1更好！但是很多时候，你并不能断言，你做的决定是最好的，这在于棋类游戏的复杂程度，像一些高深的棋类游戏，棋的变化非常多非常复杂，那你能完全相信你的估值函数吗？不能，有可能，现在看来一步很臭的棋，在不久的将来将会使局面变得很好，这就是妙手，这是经常出现的。出现这样情况的原因是，我们找到的估值函数都是从一个局面来看的，它是静止的，它看不到未来的变化，所以它是非常粗糙的。而搜索的目的正是为了‘更好的’评价棋局，可以把搜索看成是动态的估值！

如何估值？

这和具体的棋类游戏有关，同时也和你最终打包的程序的棋力有关，估得好，棋力高，这是很显然的。不管什么棋类的估值，它都有一个共同点：
对特定的局面估值要非常准确！特定的局面是那些‘胜负’非常明显的局面，你要为‘胜’打一个最高的分HScore，为‘负’打一个负最高的分-HScore，而‘平局’可以适中给分，可以给一个稍大于0的分，在不能获胜的局面里，会趋向于平局。

然后就是要有前瞻性，从一个局面分析，不搜索也不是不可以看得‘深刻’，也可以说是‘全局观’，估值函数要体现游戏的全局观，它是从整体上把握，从一个点看到了一条线！这样才是好的估值。

好了，下一个话题是‘优化搜索’，哦，这可难了，我现在还看不懂一些高级搜索算法。其实用负极大搜索算法编出来的程序是不能搜的，基本上不能搜。因为搜索量实在太大了！在一些规则简单的棋类游戏中，像黑白棋，平均分支因子都有10左右，直接去搜索，是搜不了几层的，这样的指数效应太明显了！最简单和最基本的优化方法是alpha-beta剪枝！

这是一种纯数学上的方法，是在不对搜索的结果影响的前提下剪枝，它可以使分支因子变为原来的开根号那么大（平均情况）！alpha是一个当前最好的值，如果有更好的(>alpha)将更新它，而beta是一个当前最差的值，如果有更差的(>beta)将马上产生截断（也就是不再搜索，而是直接返回原来的beta）代码如下：

int AlphaBeta(int depth, int alpha, int beta)
{
　if (depth == 0)
  {
　　return Evaluate();
　}
　GenerateLegalMoves();
　while (MovesLeft())
  {
　　MakeNextMove();
　　val = -AlphaBeta(depth - 1, -beta, -alpha); //注意到代入子树搜索的alpha,beta值
　　UnmakeMove();
　　if (val >= beta)
    {
　　　return beta;
　　}
　　if (val > alpha)
    {
　　　alpha = val;
　　}
　}
　return alpha;
}

它工作的过程，可以拿个简单的例子演示一下看看（一开始搜索时给alpha最小的值，比-HScore还要小，给beta最大的值，比HScore还要大，这很重要，否则会搜索不出胜局和负局，这是很糟的）。实际上，alpha是当前结点的兄弟结点对应的子树中搜索出来的最好值，而beta是父结点当前搜索的最好值的相反数，父结点和子结点的关系是对立的（是属于对弈的两个人，一个人会处理父结点的局面，一个人会处理子结点的局面），所以父结点的最好反过来就成了子结点的最坏，反过来也是一样。另外一种理解方法，是把alpha-beta看成一个窗口(window)，这个窗口的大小表示当前结点值得搜索的子结点的价值取值范围，往里搜索的过程就是缩小窗口的过程。它的全部效率就体现在beta值的截断作用，它的意思是说，我不用知道一步棋有多差，只要知道比前面的更差，当然我就没有任何理由选择走这步棋了！

好的估值+快速的搜索=强力的程序。我有一种想法，是评价估值的准确性的。估值不可能准确，但我想知道它有多准确，或者平均有多准确，怎么描述这里的准确性？比如，考虑一个局面p，如果直接估值（相当于搜索1层）价值是-200，而如果搜索3层，价值升到了100，而搜索5层价值又涨到了400，因为它在不久的将来有非常好的局面出现，那可否设搜索k层的评价（搜索+估值）值是E(k)，那(E(k2)-E(k1))/(k2-k1)在取了所有可行范围的所有值，再取平均，就认为是你的估值函数的准确性，如果它绝对值越高说明越不准确，越低说明越准确，那可否寻求一种自适应的方法（比如遗传算法）使估值函数的准确性值收敛呢？这样会提高棋力吗？我觉得做一个聪明的人工智能程序，不是在于，你一创造它，它就能战胜人类世界冠军，而是刚开始运行只有200分的棋力，而在和高手下了几个月后棋力涨到了2000分，然后是否战胜世界冠军已经不重要了，我觉得这才是人工智能！

评论