正文

估值函数与优化搜索2006-07-30 00:21:00

【评论】 【打印】 【字体: 】 本文链接:http://blog.pfan.cn/rickone/16973.html

分享到:

前面说了最小最大原理,为什么要最小最大原理?为什么要搜索?我们可以更简单的看对弈这件事儿,下棋的时候,从一开始到结束,每当我要走棋时,我会考虑怎么走?有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分,然后是否战胜世界冠军已经不重要了,我觉得这才是人工智能!

阅读(9396) | 评论(4)


版权声明:编程爱好者网站为此博客服务提供商,如本文牵涉到版权问题,编程爱好者网站不承担相关责任,如有版权问题请直接与本文作者联系解决。谢谢!

评论

loading...
您需要登录后才能评论,请 登录 或者 注册