棋牌游戏大全,棋牌游戏app,棋牌游戏平台,棋牌游戏赌博,棋牌娱乐,棋牌娱乐平台,棋牌论坛,棋牌,开元棋牌,棋牌游戏有哪些,斗地主,扑克游戏,麻将,德州扑克,牛牛,麻将糊了,掼蛋,炸金花,掼蛋技巧,掼蛋口诀,抢庄牛牛,十点半,龙虎斗,21点,贵阳捉鸡麻将,牌九

　　本发明属于人工智能领域中的机器博弈方向，具体涉及一种德州扑克牌型对照表的构建方法。首先生成德州扑克五张扑克牌的所有可能的组合牌型，划分为九种类型，然后构建基于哈希技术的牌型对照表，并且解决了哈希表中普遍存在的冲突问题，最后通过实验验证了对照表的最佳内存空间分配方案；本发明的基于哈希技术的德州扑克牌型表构建方法，利用哈希表查询效率高的特点，用查表代替频繁的在线牌型判断，提高了博弈系统中估值函数的执行效率。

　　(19)中华人民共和国国家知识产权局 (12)发明专利申请 (10)申请公布号 CN 112774177 A (43)申请公布日 2021.05.11 (21)申请号 4.1 (22)申请日 2021.03.08 (71)申请人 沈阳大学 地址 110000 辽宁省沈阳市大东区望花南 街21号 (72)发明人 高强孙世能吴宝举常颖 韩晓微 (51)Int.Cl. A63F 1/00 (2006.01) G06Q 50/34 (2012.01) 权利要求书1页 说明书5页 附图2页 (54)发明名称 一种基于哈希技术的德州扑克牌型对照表 构建方法 (57)摘要 本发明属于人工智能领域中的机器博弈方 向，具体涉及一种德州扑克牌型对照表的构建方 法。首先生成德州扑克五张扑克牌的所有可能的 组合牌型，划分为九种类型，然后构建基于哈希 技术的牌型对照表，并且解决了哈希表中普遍存 在的冲突问题，最后通过实验验证了对照表的最 佳内存空间分配方案；本发明的基于哈希技术的 德州扑克牌型表构建方法，利用哈希表查询效率 高的特点，用查表代替频繁的在线牌型判断，提 高了博弈系统中估值函数的执行效率。 A 7 7 1 4 7 7 2 1 1 N C CN 112774177 A 权利要求书 1/1 页 1.一种基于哈希技术的德州扑克牌型对照表构建方法，利用哈希技术在内存中构建了 德州扑克牌型对照表，并且解决了建表过程中存在的哈希冲突问题； 其特征在于按照如下步骤进行：首先分别生成九种类型的五张扑克牌的组合牌型，其 次表的每一行占16个字节，表的尺寸为2.6M*16B≈42MB（ 2598960），采用哈希技术，随 机生成52张扑克牌的32位整数和64位整数（即两个4 ×13的二维数组），通过各个扑克牌对 应的数组元素进行异或运算，其中运算得到的64位整数代表5张扑克牌牌型；32位整数 0x3FFFFFF得到26位地址作为该牌型在表的主键，对照表构建的具体流程如下： （1）随机生成扑克牌的32位随机整数和64位随机整数； 牌型种类中的所有牌型，并存放到哈希表中； （2）分别存放同花、四条、葫芦、顺子等 以同花顺为例，根据四种花色和每个花色从“A”到“5”的牌型作为循环嵌套： a.分别取五张连续的扑克牌，取出相应扑克牌32位、64位随机整数，做异或运算； b.根据异或得到的32位整数，计算26位地址； c.计算并写入排名字段，标志位flag置1； d.写入类型字段； e.写入64位哈希值，作为牌型识别码； 对照表在构建过程中，采取建立公共溢出区与开放定址法相结合的方式来解决哈希表 存在的冲突，具体处理流程如下： （1）将哈希表的尺寸扩大到64M，提高表的散列度； （2）将数据存放到基本哈希表； （3）若哈希值冲突，则存放到公共溢出表中； （4）若公共溢出表中也存在相同哈希值的数据，则采用开放定址法解决此冲突，即采用 线性探测再散列的方法，将哈希值做加1运算、加2运算等处理，找到接近冲突地址且空的位 置，存放数据； 最后通过实验验证了对照表的最佳内存空间分配方案：基本表占用128MB、溢出表占用 128MB。 2.根据权利要求1所述的一种德州扑克牌型对照表构建方法，其特征在于所述的利用 对照表实现牌型大小的判断。 3.根据权利要求1所述的一种德州扑克牌型对照表构建方法，其特征在于所述的对照 表的表结构（包括：主键、牌型识别码、标志位flag）。 4.根据权利要求1所述的一种德州扑克牌型对照表构建方法，其特征在于所述的德州 扑克牌型对照表的构成流程。 5.根据权利要求1所述的一种德州扑克牌型对照表构建方法，其特征在于所述的解决 对照表构建过程中解决哈希冲突的处理流程。 6.根据权利要求1所述的一种德州扑克牌型对照表构建方法，其特征在于所述的通过 实验得到对照表的最佳内存空间分配方案：基本表占用128MB、溢出表占用128MB。 2 2 CN 112774177 A 说明书 1/5 页 一种基于哈希技术的德州扑克牌型对照表构建方法 技术领域 [0001] 本发明属于人工智能领域的机器博弈方向，具体涉及一种基于哈希技术的德州扑 克牌型对照表构建方法。 背景技术 [0002] 德州扑克是一种玩家对玩家的扑克游戏。一共有52张牌，没有大、小王。每个玩家 分两张扑克牌作为底牌(只有本方可见，其他玩家不可见)，另有五张是所有玩家可见的公 共扑克牌被陆续发出。一个完整的德州扑克牌局共分为四个发牌阶段，即：preflop、flop、 turn、river；玩家可以选择的下注行为包括：看牌(check)、跟注(call)、下注(bet)、加注 (raise)、盖牌放弃(fold)。其具体规则如下： 首先，每个玩家分别得到两张底牌，随着第一轮下注后，开始陆续发公共牌： 1)第一次将同时发三张公共牌，然后由小盲注开始表态，玩家可以选择下注、加 注、或者盖牌放弃，若有一个玩家弃牌，则此次牌局结束； 2)第二次只发一张公共牌(即第四张公共牌)，由大盲注开始轮流表态； 3)第三次发第五张公共牌，由大盲注开始轮流表态。 [0003] 最后，亮底牌并开始比牌，由手中的两个底牌、五张公共牌，组成五张最大的牌型 进行互相比较，牌型最大的玩家赢得奖池中的筹码。牌型大小依次为：同花顺、四条(如四张 2)、葫芦(三带二)、同花、顺子、三条、两对、一对、高牌。若五张公共牌为最大牌型或双方最 大的五张扑克牌牌型完全相同，奖池中的筹码两个玩家平分。在亮底牌并开始比牌阶段，需 要博弈系统的评估函数做出判断。 [0004] 德州扑克是一种典型的不完全信息动态博弈问题，博弈树是描述二人对弈问题的 有效工具。图1显示了德州扑克一轮下注过程的博弈树，博弈树包括： 1)玩家节点(如图1中的圆形节点)。对于二人的德州扑克问题，该节点表示本方玩 家或对方玩家，这两种节点在博弈树中交替出现； 2)机会节点(如图1中的六边形节点)。该节点表示当前牌局进入下一轮发牌阶段； 3)每个玩家节点包含三种下注行为(如图1中的分支)。根据规则，每个玩家只有三 种下注行为，即弃牌、下注/加注、看牌/跟注。 [0005] 当博弈树展开到叶子节点，需要调用估值函数，判定胜负关系并计算输赢筹码量。 但是目前多采用在线判断德州扑克牌型大小的方法，每次需要判定牌型大小的时，都要调 用该方法，在线进行繁复的计算，影响估值函数的执行效率。若博弈树展开时，采用该方法 则影响博弈树的展开效率。 发明内容 [0006] 本发明的目的是针对德州扑克牌型大小在线判断比较复杂且影响估值函数执行 效率，进而影响博弈树展开的效率的问题，而构建的一种基于哈希技术的德州扑克牌型对 照表构建方法，利用哈希表查询效率高的特点，用查表代替频繁的在线 页 弈系统中估值函数的执行效率。 [0007] 本发明的方法主要利用哈希技术在内存中构建了德州扑克牌型对照表，并且解决 了建表过程中存在的哈希冲突问题。其特征在于按照如下步骤进行：首先分别生成九种类 型的五张扑克牌的组合牌型，其次表的每一行占16个字节，表的尺寸为2.6M*16B≈42MB 采用哈希技术，随机生成52张扑克牌的32位整数和64位整数(即两个4 × 13的二维数组)，通过各个扑克牌对应的数组元素进行异或运算，其中运算得到的64位整数 代表5张扑克牌牌型； 32位整数0x3FFFFFF得到26位地址作为该牌型在表的主键，对照表 的表结构如表1所示： 表1牌型对照表的表结构 列名 占用空间(Bit) 数值类型 checksum 64 unsigned__int64 type 16 short ranking 32 int flag 16 short ·Checksum:它是一个64位整数值，是每个牌型的唯一标识； ·Type:它表示五张扑克牌的类型,比如：同花顺、葫芦等等。其值的范围为1到8； ·Ranking:它表示该牌型在同一类型中的大小排名； ·Flag:它是表示数据是否已存储的标识位，用于解决哈希冲突问题。 [0008] 对照表构建的具体流程如下： 1)随机生成扑克牌的32位随机整数和64位随机整数； 2)分别存放同花、四条、葫芦、顺子等牌型种类中的所有牌型，并存放到哈希表中。 以同花顺为例，根据四种花色和每个花色从’A’到’5’的牌型作为循环嵌套： a)分别取五张连续的扑克牌，取出相应扑克牌32位、64位随机整数，做异或运算； b)根据异或得到的32位整数，计算26位地址； c)计算并写入排名字段，标志位flag置1； d)写入类型字段； e)写入64位哈希值，作为牌型识别码。 [0009] 对照表在构建过程中，采取建立公共溢出区与开放定址法相结合的方式来解决哈 希表存在的冲突，具体处理流程如下： 1)将哈希表的尺寸扩大到64M，提高表的散列度； 2)将数据存放到基本哈希表； 3)若哈希值冲突，则存放到公共溢出表中； 4)若公共溢出表中也存在相同哈希值的数据，则采用开放定址法解决此冲突，即 采用线性探测再散列的方法，将哈希值做加1运算、加2 运算等处理，找到接近冲突地址且 空的位置，存放数据。 [0010] 最后通过实验验证了对照表的最佳内存空间分配方案：基本表占用128MB、溢出表 占用128MB。实验以一种当前的局面状态为例，通过分配给基本哈希对照表和溢出表不同的 存储空间，比较搜索时间上的差别；这里设定了一个flop 阶段的牌局状态，通过完成一次 搜索来比较表占用内存的大小、发生的冲突数对搜索效率的影响，进而得到一个最佳的内 4 4 CN 112774177 A 说明书 3/5 页 存空间分配方案。测试例子：AI手牌分别为“AsKh”，flop阶段的公共牌：“9d8s7d”，其中s表 示黑桃，h表示红桃， d表示方块。 [0011] 表2占用内存空间、发生的冲突数及查询时间对照表  (溢出表大小为：8M地址空 间*16B＝128MB) 表3占用内存空间、发生的冲突数及查询时间对照表  (溢出表大小为：16M地址空 间*16B＝256MB)  对照表申请的内存空间 冲突数 查询消耗的时间(毫秒) 16MB 555067 61436 32MB 332746 59356 64MB 172883 60459 128MB 90545 61088 1GB 13517 61494 2GB 4537 61112 表4占用内存空间、发生的冲突数及查询时间对照表  (溢出表大小为：64M地址空 间*16B＝1024MB)  对照表申请的内存空间 冲突数 查询消耗的时间(毫秒) 16MB 555067 60438 32MB 332746 60320 64MB 172883 61461 128MB 90545 59528 1GB 13517 60548 2GB 4537 59212 实验结果见表2、表3和表4，通过实验结果，可看出基本对照表占用的内存越大，散 列度越高，发生的哈希冲突数越少。但是，从实验结果中发现，基本表和溢出表分别被分配 2GB和1GB时，搜索所消耗的时间却不是最少的。这是由于在溢出表中，采用了线性探测再散 列的方法来存放数据；在查询时，有一些数据同样是通过线性探测的方式(即地址加1、加2 等等)读取到的，如果溢出表过于散列，那么这种线性探测的读取效率就会很低。 [0012] 本发明的发明方法首次实现了通过构建德州扑克牌型对照表实现胜负关系的判 定；本发明的方法为那些胜负关系判定比较复杂的博弈问题提供了一种有效的解决办法； 本发明的方法利用哈希表查询效率高的特点，用查表代替频繁的在线牌型判断，提高了博 弈系统中估值函数的执行效率，与传统的在线频繁计算相比，具有较好的应用前景。 5 5 CN 112774177 A 说明书 4/5 页 附图说明： [0013] 图1为德州扑克博弈树展开过程示意图。 [0014] 图2为本发明实例1中的获奖证书。 [0015] 图3为本发明实例2中的获奖证书。 具体实施方式 [0016] 以下将参考所讨论的细节来描述本公开的各种实施方案和方面，附图将示出各种 实施方式。下列描述和附图是对本公开的说明，而不应当解释为限制本公开。描述了许多特 定细节以便提供对本公开各种实施方案的全面理解。然而，在某些情况下，并未描述众所周 知的或常规的细节以便提供对本公开实施方式的简洁讨论。 [0017] 实施例1 本发明的方法应用在二人无限注德州扑克对弈系统中，系统的博弈树展开过程 中，终局状态调用本发明的方法所构建的牌型对照表判定对弈双方的胜负关系。该系统在 2018年中国计算机博弈锦标赛中获得季军(如图2所示)。具体实施步骤具体如下： 步骤1：分别生成九种类型的五张扑克牌的组合牌型，表的每一行占16个字节，表 的尺寸为2.6M*16B≈42MB 采用哈希技术，随机生成 52张扑克牌的32位整 数和64位整数(即两个4×13的二维数组)，通过各个扑克牌对应的数组元素进行异或运算， 其中运算得到的64位整数代表5张扑克牌牌型；32位整数0x3FFFFFF得到26位地址作为该 牌型在表的主键。 [0018] 步骤2：开始构建牌型对照表，具体流程如下： (1)随机生成扑克牌的32位随机整数和64位随机整数； (2)分别存放同花、四条、葫芦、顺子等牌型种类中的所有牌型，并存放到哈希表 中。以同花顺为例，根据四种花色和每个花色从’A’到’5’的牌型作为循环嵌套： a.分别取五张连续的扑克牌，取出相应扑克牌32位、64位随机整数，做异或运算； b.根据异或得到的32位整数，计算26位地址； c.计算并写入排名字段，标志位flag置1； d.写入类型字段； e.写入64位哈希值，作为牌型识别码。 [0019] 步骤3：采取建立公共溢出区与开放定址法相结合的方式来解决哈希表存在的冲 突，具体处理流程如下： (1)将哈希表的尺寸扩大到64M，提高表的散列度； (2)将数据存放到基本哈希表； (3)若哈希值冲突，则存放到公共溢出表中； (4)若公共溢出表中也存在相同哈希值的数据，则采用开放定址法解决此冲突，即 采用线性探测再散列的方法，将哈希值做加1运算、加2运算等处理，找到接近冲突地址且空 的位置，存放数据。 [0020] 步骤4：在博弈树展开的过程中，每次到达叶子节点都需要通过查询对照表来计算 胜负关系，查表的具体流程如下： (1)分别从双方的7张扑克牌中，找到牌型最大的五张扑克牌牌型： 6 6 CN 112774177 A 说明书 5/5 页 a.首先从7张扑克牌中，生成所有的五张扑克牌组合； b.遍历这个集合，排除高牌的牌型； c.查询牌型对照表，得到具体牌型类型和在该类型中的排名； d.相互比较，得到最大的牌型； e.若所有牌型都为高牌，则对这些牌型按照数值降序排列，再相互比较得到最大 的牌型； (2)与对方的最大牌型进行比较，判定胜负关系。 [0021] 实施例2 本发明的方法应用在中国计算机博弈锦标赛所使用的德州扑克自对弈平台中，该 平台利用socket通信方式与参加比赛的博弈系统进行信息交互，平台主要负责展现德州扑 克牌局的比赛过程并最终判定胜负。比赛双方每完成一个德州扑克牌局，都使用本发明的 方法所构建的对照表实现胜负关系的判定，并且胜负结果将以牌谱文件的形式保存。该平 台已被组委会连续两年选为德州扑克项目比赛用平台。具体实施步骤描述如下： (1)由平台发牌并将手牌牌型信息发送给比赛方； (2)比赛方将决策行为及筹码数量发送给对弈平台； (3)对弈平台将决策行为及筹码量信息转发给对方参赛系统； (4)对弈平台发公共牌，并将牌型信息及牌局所处阶段信息发送给比赛双方； (5)到达终局阶段，平台调用牌型对照表来判定比赛双方的胜负关系； (6)若达到比赛规定的局数，则将比赛结果保存为牌谱文件；否则，转到步骤  1。 7 7 CN 112774177 A 说明书附图 1/2 页 图1 图2 8 8 CN 112774177 A 说明书附图 2/2 页 图3 9 9