GNU Bridge剖析之Double Dummy Solver

andalousie

GNUBridge是现在网上罕见的开源的桥牌软件。其编程语言为Java。我曾经搜到过很多只有叫牌或者只有DoubleDummy Solver(双明手求解器，简称DDS)的内容。但是GNUBridge是我唯一能找到的完整的开源桥牌软件。我这次打算学习一下它的DDS的代码。关于GNUBridge我曾经发过一篇没什么人看的帖子，链接在这里我在改善一个桥牌软件gnubridge。

控制器DealController

控制器中有一些SwingWorker类的派生类，用来实现多线程。方法就是去override原来的doInBackground函数。有两个类跟我们研究的solver有关系。SearchController还有SearchWorker，SearchController中有存最佳move的对象bestMove，并且包含有计时的内容，但计时不是我们的重点。只是简单提一下，如果计时结束某一深度搜索的结果还没出来，那么我们就直接舍弃了这个搜索结果。(也许怪可惜的，但是暂时没有好的利用方法)

我说一下它在干什么吧，简而言之，就是调用好几次findBestMoveAtDepth函数，创建一些SearchWorker对象，他们建立的时间差不多，但是由于第一个参数传入的数值不同，也就是搜索深度不同，能搜索出结果的时间也不同，但是我们强制限定了时间，于是，出不了结果的就成为了TimeoutException，只有规定时间内的那个最深的结果保存了下来。

具体看呢，findBestMoveAtDepth在SearchWorker的doInBackground里就是调用了DoubleDummySolver的search函数和getBestMove函数，其他就不是它所能管的了。

正题，DoubleDummySolver

构造函数很常规，就是为该用的变量分配了内存空间。search函数则是典型的BFS做法，先把根节点压入栈中，然后处理根节点；处理的最后，会将有用的子节点推到栈中，继续逐层访问。只有两个技术（或者说是算法）需要提。一个是checkDuplicatePositions方法，会用PositionLookup类中的方法检查是否访问过相同的状态，如果有，就直接调出原来的数据，不往下搜了；另一个是removeSiblingsInSequence方法，用来排除出牌过程中完全等价的牌，(例如手中拿着A和K，那么出A和出K是等价的)。

作者设想中会有多种postEvaluationPrunningStrategies，可是他最终只使用了alpha-beta剪枝这一种策略。简单来说，就是从底向上进行剪枝。不过在了解剪枝之前，我想有必要解释一下calculateValue()方法。

计算节点的赢墩数

我可以很明确的告诉你，calculateValue()方法就是计算某一结点处我方赢墩数的方法。我需要讲一下，我下面会用一些口语化的术语，比如我方玩家所在的位置，称为max位置；敌方就会是min位置。大家看代码一眼就会觉得自己已经明白代码在干什么了，因为方法名称就是英文，很好懂：是leaf就怎么样，不是leaf又怎么样。我也不会为讲这个来专门写一小块儿占文档地方的。我是要说明这个方法是用前后的差别的。因为在之后的剪枝过程会用到。

提前扯一点，我们会发现后面针对一个节点剪枝的时候，只把这个节点的赢墩数计算出来了，其他节点就没理他。那么我们用的是什么？答案是UNINITIALIZED，也就是-1。

Alpha-beta剪枝的过程

从DoubleDummySolver(也就是外部)看，代码就是简简单单的在从下向上剪枝。DoubleDummySolver有visit()，是一个地地道道的递归函数。在这个函数里，我们和作者想法一样简单，正如注释中说的，(注释还没来及改)，只有在一个节点成为leaf或者查出PositionLookup中存着完全一样的节点(identical twin)或者某一墩的最后一个节点的时候，我们才会调用visit函数，让程序一层一层剪枝。那么或许要问，剪到什么时候停呢？首先在外部我们看到的控制条件是canPrune()。当canPrune()返回false的时候，无论如何我们也不会再向上(我们知道，数据结构中的树从来都是倒着长的，向上就是向根部)。这个条件是这么写的：

!isRoot()                                          //不是根节点
&& !parent.isPruned()                        //父亲健在(没被prune过)
&& parent.isLastVisitedChild(this);      //搜索过程中，父亲是爷爷的孩子里
                                         //最后一个被拜访(visit)的

至少在外面我们看到的是这样子的，在访问某一层的某一结点的前面，总计算一下它的值。但是仔细看，我们发现不太对，因为prune函数里面仍有若干判断条件。我们以alpha剪枝为例，讲到如果shouldBeAlphaPruned()那么就alphaPrune()。看起来总是好像没什么。但shouldBeAlphaPruned()里面的条件真不少啊!!!

valueSet                                           //该节点已经calculate过了，放心用~
&& !isRoot()                                     //不是根节点
&& !parent.isRoot()                            //不是根节点的孩子
&& hasAlphaAncestor()                      //存在不是根节点、健在且是max位置的祖先节点
&& !parent.isAlpha()                          //但父亲不是max位置
&& (getTricksTaken(getMaxPlayer()) <= parent.getLocalAlpha());
                                         //我方玩家这一张牌的赢墩数没有超过
                                         //前一个min位置的赢墩数

我们发现这正是Ginsberg曾经提到过的浅层剪枝(shallow pruning)。在gnubridge的官方博客里面，部门也看到深层剪枝(deep pruning)还没有实现。最后就是真正prune的过程了。每次prune之前又会有一些检查：

!parent.isRoot()
&& !parent.isPruned() && !parent.isAlpha() &&
!parent.parent.isRoot();

由于上面已经判断过这里面的一些条件了，所以我觉得这里可能会略微耗时。简述一下吧，在符合了一切这些判断条件之后，就是直接把parent给prune掉。

百日维新

强烈支持楼主ing……