鱼C论坛

 找回密码
 立即注册
查看: 4290|回复: 1

[技术交流] GNU Bridge剖析之Double Dummy Solver

[复制链接]
发表于 2014-11-6 12:58:13 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 andalousie 于 2014-11-6 21:27 编辑

GNUBridge是现在网上罕见的开源的桥牌软件。其编程语言为Java。我曾经搜到过很多只有叫牌或者只有DoubleDummy Solver(双明手求解器,简称DDS)的内容。但是GNUBridge是我唯一能找到的完整的开源桥牌软件。我这次打算学习一下它的DDS的代码。关于GNUBridge我曾经发过一篇没什么人看的帖子,链接在这里我在改善一个桥牌软件gnubridge
控制器DealController
控制器中有一些SwingWorker类的派生类,用来实现多线程。方法就是去override原来的doInBackground函数。有两个类跟我们研究的solver有关系。SearchController还有SearchWorkerSearchController中有存最佳move的对象bestMove,并且包含有计时的内容,但计时不是我们的重点。只是简单提一下,如果计时结束某一深度搜索的结果还没出来,那么我们就直接舍弃了这个搜索结果。(也许怪可惜的,但是暂时没有好的利用方法)
我说一下它在干什么吧,简而言之,就是调用好几次findBestMoveAtDepth函数,创建一些SearchWorker对象,他们建立的时间差不多,但是由于第一个参数传入的数值不同,也就是搜索深度不同,能搜索出结果的时间也不同,但是我们强制限定了时间,于是,出不了结果的就成为了TimeoutException,只有规定时间内的那个最深的结果保存了下来。
具体看呢,findBestMoveAtDepthSearchWorkerdoInBackground里就是调用了DoubleDummySolversearch函数和getBestMove函数,其他就不是它所能管的了。
正题,DoubleDummySolver
构造函数很常规,就是为该用的变量分配了内存空间。search函数则是典型的BFS做法,先把根节点压入栈中,然后处理根节点;处理的最后,会将有用的子节点推到栈中,继续逐层访问。只有两个技术(或者说是算法)需要提。一个是checkDuplicatePositions方法,会用PositionLookup类中的方法检查是否访问过相同的状态,如果有,就直接调出原来的数据,不往下搜了;另一个是removeSiblingsInSequence方法,用来排除出牌过程中完全等价的牌,(例如手中拿着AK,那么出A和出K是等价的)
作者设想中会有多种postEvaluationPrunningStrategies,可是他最终只使用了alpha-beta剪枝这一种策略。简单来说,就是从底向上进行剪枝。不过在了解剪枝之前,我想有必要解释一下calculateValue()方法。
计算节点的赢墩数
我可以很明确的告诉你,calculateValue()方法就是计算某一结点处我方赢墩数的方法。我需要讲一下,我下面会用一些口语化的术语,比如我方玩家所在的位置,称为max位置;敌方就会是min位置。大家看代码一眼就会觉得自己已经明白代码在干什么了,因为方法名称就是英文,很好懂:是leaf就怎么样,不是leaf又怎么样。我也不会为讲这个来专门写一小块儿占文档地方的。我是要说明这个方法是用前后的差别的。因为在之后的剪枝过程会用到。
提前扯一点,我们会发现后面针对一个节点剪枝的时候,只把这个节点的赢墩数计算出来了,其他节点就没理他。那么我们用的是什么?答案是UNINITIALIZED,也就是-1
Alpha-beta剪枝的过程
DoubleDummySolver(也就是外部)看,代码就是简简单单的在从下向上剪枝。DoubleDummySolvervisit(),是一个地地道道的递归函数。在这个函数里,我们和作者想法一样简单,正如注释中说的,(注释还没来及改),只有在一个节点成为leaf或者查出PositionLookup中存着完全一样的节点(identical twin)或者某一墩的最后一个节点的时候,我们才会调用visit函数,让程序一层一层剪枝。那么或许要问,剪到什么时候停呢?首先在外部我们看到的控制条件是canPrune()。当canPrune()返回false的时候,无论如何我们也不会再向上(我们知道,数据结构中的树从来都是倒着长的,向上就是向根部)。这个条件是这么写的:
  1. !isRoot()                                          //不是根节点
  2. && !parent.isPruned()                        //父亲健在(没被prune过)
  3. && parent.isLastVisitedChild(this);      //搜索过程中,父亲是爷爷的孩子里
  4.                                          //最后一个被拜访(visit)的
复制代码
至少在外面我们看到的是这样子的,在访问某一层的某一结点的前面,总计算一下它的值。但是仔细看,我们发现不太对,因为prune函数里面仍有若干判断条件。我们以alpha剪枝为例,讲到如果shouldBeAlphaPruned()那么就alphaPrune()。看起来总是好像没什么。但shouldBeAlphaPruned()里面的条件真不少啊!!!
  1. valueSet                                           //该节点已经calculate过了,放心用~
  2. && !isRoot()                                     //不是根节点
  3. && !parent.isRoot()                            //不是根节点的孩子
  4. && hasAlphaAncestor()                      //存在不是根节点、健在且是max位置的祖先节点
  5. && !parent.isAlpha()                          //但父亲不是max位置
  6. && (getTricksTaken(getMaxPlayer()) <= parent.getLocalAlpha());
  7.                                          //我方玩家这一张牌的赢墩数没有超过
  8.                                          //前一个min位置的赢墩数
复制代码
我们发现这正是Ginsberg曾经提到过的浅层剪枝(shallow pruning)。在gnubridge的官方博客里面,部门也看到深层剪枝(deep pruning)还没有实现。最后就是真正prune的过程了。每次prune之前又会有一些检查:
  1. !parent.isRoot()
  2. && !parent.isPruned() && !parent.isAlpha() &&
  3. !parent.parent.isRoot();
复制代码
由于上面已经判断过这里面的一些条件了,所以我觉得这里可能会略微耗时。简述一下吧,在符合了一切这些判断条件之后,就是直接把parentprune掉。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2014-11-6 16:42:00 | 显示全部楼层
强烈支持楼主ing……
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 20:04

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表