扑克游戏规则

扑克游戏规则

双明手求解器的改进

扑克游戏规则 时间:2019年10月27日 14:04

  与棋类项目相比(明棋),桥牌是不完备信息的博弈。前不久阿尔法狗战胜了人类围棋顶尖高手李世石。那么计算机有没有可能战胜人类桥牌顶尖高手呢?我的结论是很难。不仅现在如此,将来也是对机器的巨大挑战,即使电脑偶尔战胜人类高手,也不会形成棋类那样对人类的压倒性优势。一是不完备信息的问题。桥牌的信息采集的难度远大于棋类。棋类的信息完全公开,一眼可见。而桥牌要从每一手叫牌和出牌的过程推测对手所剩牌张,还要考虑本方和对方的约定(包括叫牌约定和打牌约定),以及执行约定时的主观因素,比如态度信号,很难准确通过其判断对手所持具体的牌。另外一个就是游戏过程树和状态树空间的问题。围棋是死的,过程树和状态树空间不过的几百次方而已。桥牌由于存在叫牌的环节,所以相当的灵活。在叫牌阶段,相同的叫品按约定不同,传递的信息不同应该算不同的状态,由于叫品的约定可以人为的设计,就使桥牌的状态空间趋向于无穷大。万次方,即使对叫牌做出一定限制,其状态也很容易超出上述所列数字。机器人难以用暴力穷举战胜人类。只能模仿人的行为来和人竞争,机器的优势大减。而在设计叫品这方面,机器的能力机乎为零,这是更高层次的策略,人可以充分发挥优势所在。当然,如果简化游戏难度,双方使用一套同样的叫牌体系并且不许诈叫(或者说百分之百遵循叫牌体系),电脑的胜算就增加了,再简化难度,没有叫牌只有打牌,电脑的胜算会急剧上升。再简化难度,四家都把牌亮明,打双明手桥牌,则电脑可以完胜人类。这和棋类的道理是相同的,而双明手桥牌的状态树和过程树空间还要小一些,相对容易,本文就解决桥牌双明手求解器的改进问题。

  双明手求解器可以被认为是一个已经解决的问题。本文在1996年发表的Chang博士的《构造一个快速双明手求解器》的基础上,经过一系列的改进得到。

  Chang博士的求解器在Sparc-10工作站上运行,平均15秒得到13墩牌的不精确解。本人经过改进的求解器一般在半分钟内得到13墩牌的解,是精确的解,运行在AMD FX(tm)-6300 3.52GHZ处理器,16G内存,win10 64位操作系统,java1.80_73-b02虚拟机上。和一些现存的先进的双明手软件相比,这个求解器在效率上要低一些,比如和bridge-studio相比。但它是我在理解了Chang博士论文的基础上,经过一定的改进而得。本人掌握全部技术细节,并愿意全部公开,以达到抛砖引玉的效果。

  另外还参考了《重庆大学学报》程克非等的论文《计算机桥牌双明手解的hash表改进》,辽宁科技大学张志刚的《双明手桥牌打牌的辅助分析程序研究》和辽宁科技大学王彩霞等的《桥牌游戏搜索空间的研究》

  我们假设用暴力穷举的办法解决打牌的问题。那么我们会面临一个什么局面呢?首先,一个牌手的手中13张牌之外,39张牌分配给其它3个人,共有C3913C2613C1313≈1017,即1017种状态。用暴力的办法解决出牌(第一张)是否是10171021呢?答案是否定的。因为还要考虑到在打牌开始之前就已经存在的信息。而这个信息的可能性有多少呢,这就麻烦了。假设我们的信息很简单,只知道某种状态有或没有,则有2的1017次方种可能的信息。即10的3.01亿亿次方种信息。这个数和围棋的状态树与过程树空间的10的几百次方相比,是不是大了不少呢?如果我们的信息不只知道某种状态可能出现或不出现,而是更精确的知道可能出现的概率大小。则全部信息的可能性又比2的1017这个数在得多的多。这就是桥牌不可能用暴力穷举的原因。

  我的这种结构的好处在于ddsearch返回falser的情况只执行一次。而ddsearch在返回truer的情况下只需要某一种行牌的结果为true即可,ddsearch返回为false时,则需要搜索全部可能的行牌,全部为false时才返回false。这就是我的算法的优势。

  我在两个方面改进了原文的哈希表,一是在哈希表条目的数量上,Chang博士原先的论文中的哈希表包含220个条目。考虑到现在的PC机内存普遍都增大了,可以使用更大的哈希表空间。

  我在经过多次实验之后,发现使用包含228个条目的哈布表,效率最高,在有8g内存的64位windows系统上可以正常运行。

  我使用的哈希表共有218种不同的哈希关键字,在哈希表条目为228时是1024路重散列,在哈希表条目为229时是2048路重散列。虽然后者与前者相比,展开结点数略少,但是由于每次对是否哈希命中/冲突做检查时,要检索2048个条目,所以效率反而降低了。

  而1024路重散列的效率要比512路重散列要高。对于我的包含218种不同哈希关键字的哈希表来说,1024路重散列的效率是比较高的。

  那么这个哈希表具体怎么构造呢?我首先参考了Dan Emmons的方法。用四个字节表示每个花色套四个顶张大牌的位置。每两个位为一对,表示持有对应牌的牌手的编号。接下来的8个字节存储每个牌手各个花色套的长度,用四个连续的位为一组存储对应牌手某一个花色套的长度。最后一个字节包含的是要出下一张牌的牌手。取前两个字节和最后一个字节的两位(只有两位有用的信息)做为哈希关键字,关键字的长度共18位,即有218种哈希关键字。其余的字节作为内容存储在对应的哈希表条目下。这一改进使得求解器的效率大大提高。

  另外的哈希表改进是参考了程克非等的论文后做出的。任意一个没有王牌的局面下,4种花色可以互换而不影响计算的结果。如果有王牌,则余下的3门花色可以互换。因此可以标准化4种花色的次序,使局面减少。

  我对花色的排序是,首先将牌花色靠前,其次张数多的花色靠前,再有对张数一样多的花色,计算牌张位置权重,权重大的靠前,前面都一样时低级花色靠前,高级花色靠后。

  应用上述的改进,使得效率提高了20%-30%。另外,程克非等人的论文中说的总是按照北家为引牌方编码局面。本人经试验不,并没有提高效率,原因是很难出现四个人手中的牌恰好和轮转1,2,3位后完全相同。

  我对单套分析做出的重大改进就是扩展了单套分析的范围。在Chang博士的原文中,他只对长度不超过9的花色套进行单套分析,而我对长度为任一值的花色套进行单套分析。

双明手求解器的改进的相关资料:
  本文标题:双明手求解器的改进
  本文地址:http://www.kemtu.com/shijieqiaopaimingjiajingcaipaili/10271522.html
  简介描述:与棋类项目相比(明棋),桥牌是不完备信息的博弈。前不久阿尔法狗战胜了人类围棋顶尖高手李世石。那么计算机有没有可能战胜人类桥牌顶尖高手呢?我的结论是很难。不仅现在如...
  文章标签:桥牌双明手
  您可能还想阅读以下相关文章:
----------------------------------