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

最小最大原理

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

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

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

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

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;
}

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

评论