扑克游戏规则

扑克游戏规则

构造一个快速双明手求解器

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

  与其它游戏相比,特别是国际象棋,对计算机桥牌的研究是不成熟的,而最好的桥牌程序也不过是质量中等偏下的。在这篇论文中我们解决的问题是设计一个快速地双明手桥牌游戏求解器。(也就是一个包含全部信息的简单的桥牌游戏。)虽然我们为了寻找最佳打牌路线而生成的博奕树的尺寸是巨大的。大约是),我们表明,通过种种搜索技术和有效地移动排序以及剪枝启发,大多数的双明手桥牌问题都可以在一个合理的时间范围内解决。在这篇论文中,我们先对计算机桥牌及之前的工作在桥牌打牌部分的内容做一个简短的介绍。然后,我们描述双明手求解器的顶层架构,接下来是一些我们在求解器中使用的技术。最后,我们出示实验结果,给出我们的结论,并叙述一些在未来针对真正桥牌比赛中自动出牌要做的工作。

  计算机桥牌对于人工智能研究者来说是一个有趣的且富有挑战的题目。以人工智能的角度来看,桥牌是一个在叫牌和出牌阶段都用不完全信息进行判断的游戏。在叫牌的过程中,只知道52张中的13张牌以及之前的叫牌记录,一个说得过去的程序可能需要描绘叫牌方法和约定的能力,从他的同伴和对手那里收集线索,对他和他的同伴在当前叫牌中所需的牌情进行编码和解码,不论何时只要有可能,对他的对手隐瞒手中的牌,对所有可能的最终定约进行估值并计划达到一个对他的团队最有利的定约。当进行到出牌阶段,最初仍有一半的牌是不可见的,程序应该对一组可能的出牌路线进行估值并选择最佳路线。从已经出过的牌中提取有用的信息,并拥有根据新的信息修正出牌路线的能力。不幸地是,这些工作即使对于普通的牌手来说也是很难的,而让计算机能够模仿和处理好这些问题,看起来也是很困难的。

  在我们到目前为止的研究中,我们跳过了计算机桥牌的叫牌阶段,并且假设在出牌阶段掌握全部信息。因此,在这篇论文中,我们定位于解决桥牌双明手问题;假设具备完全信息(或者说双明手)且是最佳出牌路线(所有玩家以获得极小极大赢墩的可能出牌。)我们的双明手求解器应该能够建议当前的牌手出一张能为他的队伍赢得最多赢墩数的牌。注意双明手桥牌可以看成一个具备完全信息的两个人之间(庄家和防家)的对手博奕游戏——一类可以成功应用αβ搜索计术的游戏。

  在我们进入双明手求解器的实现细节之前。让我们简要回顾一下以前计算机桥牌出牌阶段所建议的方法。

  通过适用自动化数学定理的技术证明桥牌出牌阶段的声明。弗兰克开发了一个叫做飞牌的系统。在他的系统中,制定计划的基本元素是步骤而不是手中所持的牌张。每个步骤对应一个普通的人类牌手的战术(举例来说飞牌,忍让,拔掉赢墩)并且用一个结构表达,结构中的参数带有对应战术的先决条件和后条件的明确说明。为了构思一个计划,飞牌软件通过他们的说明结合各种方法。在单套牌的陈述式规划领域,他们宣称飞牌软件能在桥牌书中大量的牌例中找出合适的行牌路线,并由概率上的和性质上的信息给出他的决定。【1,2】

  甘贝克建议使用人工智能通过对每个单独的花色采取暴力穷举得到子计划,再对这些子计划合并得到一个完整的计划。【3】

  金斯伯格【4】和利维【5】对出牌给出了相似的建议。假设我们有一个快速的桥牌双明手求解器。那么,现实中的桥牌(只有一个明手-北家),理想的出牌路线的建立可能是对一组牌平均起来的最佳方案,那组牌的生成是根据叫牌历史和首攻做出的。

  虽然双明手桥牌不是真正的桥牌,而且通过对一组双明手牌平均起来的计划建立起来的能胜任的出牌计划是含糊的且有问题的。我们认为设计一个快速的双明手求解器对于计算机桥牌的研究是重要的,基于以下原因:

  一个快速的双明手求解器不仅在出牌阶段在叫牌阶段也对我们有所帮助——当估算我们能达到的不同定约时,一个快速的双明手求解器能告诉我们任意一个猜测的牌张分布所能达到的定约

  因为搜索空间是巨大的,它是一个挑战值得我们通过努力以尝试减少搜索空间到一个对现在的计算机能力而言合理的水平。

  一个快速的双明手求解器本身是一个有价值的工具,他能通过模拟统计证明对桥牌手来说的一些常识性的问题。

  双明手桥牌是真正桥牌的一个简化版。如果我们不能在一个合理的时间内解决它,那么我们怎么能期待编写一个专家级的出牌程序呢?

  在我们展示双明手求解器中引用的技术之前,先让我们看一下它的顶层结构的原始实现,它基本上是一种搜索【7】。我们的算法用C++描述。

  给出sp参数指向保存当前状态信息的结构体的指针以及参数goal表示的墩数,如果当前牌手所在的队能够取得至少goal所代表的墩数,双明手搜索函数返回1,否则返回0。总的来说,它按如下方式工作:当goal是某种不重要的值,比如0或者一个比剩下的所有赢墩都要大的数它返回1或0。如果上面的条件都不满足,我们调用GenerateMoves为当前的游戏状态生成一个合理的出牌列表M。每次NextMove被调用,它都从列表M中检索下一个可能的出牌。我们调用PlayCard以使选择的移动生效并更新当前游戏状态。当出完一张牌之后,当前状态中的域switch_team被置为1,如果下一个出牌人与当前出牌人不是一个队的线。然后我们以下一个游戏状态和更新了的目标作为参数递归调用ddsearch。变量result表示打出选中的牌是否能至少赢得目标的墩数。如果结果的值为1,那么我们跳过剩下所有的步骤并返回1,否则,我们收回打出的牌,并尝试下一种出牌。

  2中的代码,条件low≤MaximalTricks总是满足的。而最小值和最大值之间的间隔在每循环之后减少一半。在13墩的桥牌游戏中,当MaximalTricks是0或7时,需要调用ddsearch3次求解游戏,否则需要调用ddsearch4次求解游戏。

  ——在ddsearch函数中检查存在的快速赢墩数。我们主要的思想是:如果出牌的一方能赢得至少一墩并且goal是1的话,我们就跳过进一步的搜索索并返回1;或者相似地,如果goal等于tricks_left并且对手至少能赢得一墩,那么我们就要返回0。在我们对10墩桥牌的游戏实验中,使用快速赢墩检查平均减少了超过50%的展开结点(或者说调用ddsearch函数的次数)。

  ddsearch的调用)是常见的。因此,用一个哈希表存储经常访问的结点或搜索树中更深的结点(或者剩余的赢墩)的最多赢墩的上限与下限对减少搜索树的尺寸是有帮助的。1

  哈希表检查在每次ddsearch被调用时执行,但是对当前一墩牌某些额外的信息(也就是说,引牌的花色和当前的赢张)也应该被储存并核对。

  我们在实验中采用第一种方法,因为就展开结点数和所花的计算机时间而言,它稍好一些。在第二种方法中,我们为了核对赢墩上限和下限所存储的额外哈希表条目经常会提供给我们和它的父节点相似的信息,其父节点在当前一墩开始时已经被存储了。但是这些额外的信息很难被使用(如果它们可能引起剪枝,他们对应的父节点可能已经被存储并为我们提供同样的帮助)并可能把更有用的节点的空间占用。

  220个条目;每个条目有8个字节。对每一副牌,我们把52张牌分成两个不相交的集合:集合A包含每一花色中5张最大的牌;集合B包含剩余的8张。我们还分出一个集合C,包含每一花色B集合中所剩的5张最大的牌。让我们用Bits表示一个函数,把一组牌映射成一个位序列。每一个位相当于每张牌,表示这张牌在当前状态下,在其所在的集合是否出过。对每一个位,数值1表示牌出过了,数值0表示牌没出过。我们计算Bits(A)异或Bits(C)的值作为哈希键字,它是哈希表的索引。这里,我们借用计算机国际象棋的思想,用异或运算生成哈希关键字,让它更平均地分配在哈希表上。为了识别游戏状态,我们在每个哈希表条目中储存Bits(B)和当前的牌手。注意哈希关键字和Bits(B)的组合,能唯一识别出到目前为止出过的牌。

  Bits(C)的第5位到左边以获得哈希关键字。对位的循环能使我们在实验中生成的哈希关键字更均匀地分布在哈希表上。

  /冲突的比率,我们还尝试2,4,8以及16路重散列。为了说明,我们用4路重散列作为例子。在我们的220个哈希表条目中,每4个连续的条目分成一组。为了检查哈希表,我们选择20位哈希关键字中最重要的18位来获得对应的四条组,并连续地检查那四条哈希表条目。类似地,当插入当前状态的搜索结果时,我们在条目组中找最浅深度的(或者哈希冲突最大的)条目,如果4个条目的空间都被占据的话。在我们的实验中,8路重散列的性能比其它的要好,它所花费的CPU时间是最少的。虽然16路重散列有稍好一些的哈希命中/哈希冲突比率而且有更少的展开结点数与8路重散列相比,但是它的哈希表检查和插入的关联开销降低了其效率。

  3,2】声称他们开始用这个想法编写桥牌出牌程序,但是到目前为止,还没有结果发表出来。此外,在双明手搜索中使用单套分析的结果仿佛以前没有被提起过。在这一节,我们先展示一手例子,然后我们描述如何在我们的双明手求解器中使用分析结果,并实现单套分析。

  4,2,10和A已经出过了,而现在轮到南出牌,那么南北将在方片套得到两个当然赢墩和两个长套赢墩,而在兑现当然赢墩和长套赢墩之后,控制权将会转移到北手中。

  2中使用的原始下限值是0,我们能取而代之的是用一个更大的值作为下限从而减少执行ddsearch函数的次数,从4次(对绝大多数13墩桥牌游戏而言)减少到一个更小的值。

  ddsearch做进一步搜索之前,我们能执行下限评做以观察我们的评估值是否已经不小于目标了,当开始一墩牌时或者正好在当前一墩牌首引之后。因为,强牌通常会落入特定的一方,我们选择执行下限评估的时机能让较强的一方在早期有一个大的下限评估(这能影响早期剪枝的结果),这是在他们没有开始当前一墩的情况下。

  ddsearch函数相似,只是在判断和评估叶子结点的方式上有微小的不同。为了节省单套分析执行所需的时间,我们预先计算并把分析结果存储在一个表格中,计算的内容包括所有可能的相对阶数的分布和首引的牌手,对于所有长度不超过9的花色套而言。对于长度为9的花色套,我们需要218个不同的值来索引所有可能的相对阶数分布,每个相对阶数由两位表示,指出持有它的牌手。如果我们用两字节存储分析结果,那么为了存储所有可能的阶数分布(218种)和首引牌手(4种)的内存空间就有221或者两兆字节。为所有长度不大于9的花色套存储分析结果的内存空间少于3兆字节。

  对花色套X中一组相对于剩下的牌阶数连续的一组牌,只有其中一张被拿出来考虑,因为它们都有相同的效果。

  所有点数牌(也就是说,低阶数的牌)可以被近似地认为是同一种行牌,并且只有其中的一张被选择进入出牌序列,因为小牌很少在出牌的过程中可以得到一墩牌。

  如果牌手P的最大级的合法牌张仍然比别一个牌手最低级的牌张要低,那么我们只尝试牌手P中最小张的牌。

  Q之后,北有两种出牌选择:黑桃A(赢张)和黑桃7(输张)。因为南北方的大部分当然赢墩在南手里,所以北可能更愿意先打出输张而保留他唯一的进手张。注意这么出牌对这手牌来说碰巧是正确的。我们现在对排序的实现仍然是原始的,而生成一个表格以总结这些高度领域依赖的排序启发的工作才刚开始。

  当把所有的花色套排序之后,我们要决定为每个花色套所选之牌的总排序。不用按一个花色一个花色地尝试每张牌,我们在最初的几步只尝试每个花色中最佳的出牌,并把它们按花色套的顺序排序,然后我们尝试剩下所有的牌,花色套的顺序对牌张的排序有着重要的作用。这能使我们避免在最后一步才选对正确的花色套,假如对花色套的排序不是很好的线.

  搜索中经常要用到的信息,并且占用空间不是太大的,应该被存放在一张表中。这些信息可能是静态的(也就是说与我们解决的牌例不相关联)或者是动态的。如果是静态的,信息可以被预先计算并储存在文件里。动态信息可以在第一次计算的时候存储起来,然后当再次需要时将其取回。虽然数据表查找技巧对展开结点数的减少没有帮助,但是它们能让程序不断地加速。这里有一些信息适于数据表查找。最后两个是动态的,其他的是静态的。

  位表示一个特定花色套当前的状态并用4位表示一个绝对的(或相对的)阶数,它返回对应的相对(或绝对)阶数。单套分析结果。单套分析的结果对估算下限和生成出牌序列有帮助。如同已经提到的那样,我们预先计算并存储所有长度不超过9

  的花色套的全部可能的相对阶数分布组合的分析结果。生成哈希关键字所用的位掩码。一旦我们决定用牌张来设置哈希关键字和它们在哈希关键字中对应的位的位置,我们能计算位掩码,一旦打出的牌张的花色套和绝对阶数知道的话就可以计算哈希关键字。

  的当前状态(用13位表现),我们能够把当前牌手在应用过行牌剪枝启发之后在花色套X可能的行牌存储在一个表中,以便然来的查找之用。我们的实验在10副随机产生的13墩游戏上进行,表明超过98%的这些行牌信息可以通过数据表查找获得。7.实验

  Sparc-10计算机上)。除了使用单套分析结果的提议,在我们的实现中引用的技术现在都是现成可用的。下面我们总结一些未来针对真实桥牌中自动出牌方面的研究。为花色套定约实现一个下限估算器。

构造一个快速双明手求解器的相关资料:
  本文标题:构造一个快速双明手求解器
  本文地址:http://www.kemtu.com/shijieqiaopaimingjiajingcaipaili/10271523.html
  简介描述:与其它游戏相比,特别是国际象棋,对计算机桥牌的研究是不成熟的,而最好的桥牌程序也不过是质量中等偏下的。在这篇论文中我们解决的问题是设计一个快速地双明手桥牌游戏求解...
  文章标签:桥牌双明手
  您可能还想阅读以下相关文章:
----------------------------------