正文

最小最大原理与搜索方法2006-07-28 16:14:00

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

分享到:

我的黑白棋终于算是会走棋了,高兴了好一阵子,而且还能战胜我自己。我想把资料总结一下,以下所述的将从最简单的开始,与黑白棋无关,是广义的棋类博弈算法。网上有好多算法文章介绍,我只是简单概括一下。


最小最大原理

最小和最大是相反的矛盾的,正如下棋的两个人,他们是对手,他们在进行对抗,其中一个叫最小者,另一个叫最大者,最大者(想像成我)希望棋面对‘我’最好(最好是赢棋),最好就是最大,反过来,对手就希望棋面对‘我’最差,最差就是最小,最大就是对已最有利,最小就是对对方最有利。这里的最小最大,是有一个参照物的,不管以谁为参照物,它是固定的。最小和最大是对称的,平等的,就像两个重物挂在一杆称上,不断的在较劲。

而最小最大原理是说什么,它是说‘最大者’在选择最大(好)的棋走的时候,它要选对方在回应这步棋时最小(对对方最好)着法中的最大着法!(着法就是可以走的棋)这里涉及了一棵树,它叫博弈树,根在上面,倒长的一棵树。

根是当前局面,我要从当前局面的所有可行着法中选一个‘我认为’‘最佳’的着法走这步棋,这所有的可行着法,就对应着所有的子树,当走了某一步后,就到达了子树的根,同样的情况发生了,这时你是站在最小者的立场上想棋的,所以最小最大反了过来,孙子曰过‘知已知彼,百战不殆’,你不能站在对方的立场想问题,就无法取得胜利!

注意到,这其实是对博弈树的深度优先搜索,只是搜索的时候有两个对立的处理模块,最大搜索和最小搜索,最大的调用最小的,最小的调用最大的,是一个双递归。像这样:

int Max(int depth)//最大搜索
{
 int best = -INFINITY;
 if (depth <= 0)//depth是控制深度
  {
  return Evaluate();//返回对当前局面的‘看法’,估值
 }
 GenerateLegalMoves();//生成当前所有着法
 while (MovesLeft())//遍历每一个着法
  {
  MakeNextMove();//实施着法
  val = Min(depth - 1);//反过来搜索,站在最小者一方
  UnmakeMove();//撤销着法
  if (val > best)
    {
   best = val;
  }
 }
 return best;
}
 
int Min(int depth)//最小搜索
{
 int best = INFINITY;
 if (depth <= 0)
  {
  return Evaluate();
 }
 GenerateLegalMoves();
 while (MovesLeft())
  {
  MakeNextMove();
  val = Max(depth - 1);
  UnmakeMove();
  if (val < best)
    {
   best = val;
  }
 }
 return best;
}

搜索的深度,可以认为是思考的深度(天啦,语言里也有这么一个概念),如果一个人看问题只看当前局面的情况,而不考虑将来发生的事情,那么说这个人看问题短深,反之则深刻,也就是聪明,要想你的程序够聪明,那就让它搜得更深一些吧,‘深蓝’的前身叫‘深思’正是这个意思。哦~你会想,既然如此,那让它搜无限深,其实这非常不现实,学过数据结构的就知道,一棵深度为n的二叉树的结点数有 2^n-1个,是指数增长的,如果是k叉树呢?具体是多少不确定,但它一定是k^n次方的量级的,这个k就叫分支因子,不要说无限深,比较深都难~~


负极大搜索

最小和最大是对立的,矛盾的,同时也是统一的,最小最大搜索可以用负极大搜索代替,先看代码:

int NegaMax(int depth)
{
 int best = -INFINITY;//INFINITY为定义的一个非常大的数,借以表示无穷大
 if (depth <= 0)
  {
  return Evaluate();//估值函数
 }
 GenerateLegalMoves();
 while (MovesLeft())
  {
  MakeNextMove();
  val = -NegaMax(depth - 1);//注意这里有个负号
  UnmakeMove();
  if (val > best)
    {
   best = val;
  }
 }
 return best;
}

代码很相似,你要问,这样能行吗?这里要注意的是,这里的估值函数有不同,前面是选定了一个参照物,比如最大者,那估值如果是正,则对最大者有利,如果是负则对最大者不利。这里的估值函数,是对当前要落子的一方而言的(所以有必要记录一下一盘棋当前要落子的一方),于是那里取一个负号,就反过来了(其中奥妙还要你拿个简单的例子来试一试)。不在话下。

阅读(21122) | 评论(2)


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

评论

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