第15卷第3期 智能系统学报 Vol.15 No.3 2020年5月 CAAI Transactions on Intelligent Systems May 2020 D0:10.11992/tis.201803043 一种基于经验的德州扑克博弈系统架构 高强，徐心和2，王昊3，白国力3，曹瑞珉 (1.沈阳大学辽宁省装备制造综合自动化重点实验室，辽宁沈阳110044,2.东北大学信息科学与工程学院， 过宁沈阳110819：3.东北大学机械工程与自动化学院，辽宁沈阳110819) 摘要：为了利用历史经验知识提高德州扑克博弈水平，提出一种二人赌注无上限的德州扑克博弈系统架构： 对于知识库模块，利用海量历史牌局训练得到基于CN的深度学习网络模型并构建了一个专家经验库：在系 统的搜索模块中，构建了一种分阶段的德州扑克博弈树，利用专家经验和历史经验引导德州扑克博弈树的展 开；对于系统的估值核心模块，构建了一种基于哈希技术的牌型对照表，以提高系统判定胜负的效率。实验结 果表明本文提出的博弈系统架构具有更高的对弈水平。 关键词：二人赌注无上限德州扑克；计算机博弈；非完全信息动态博弈：博弈树：深度学习；专家库：哈希表：博 弈策略 中图分类号：TP301.5文献标志码：A文章编号：1673-4785(2020)03-0468-07 中文引用格式：高强，徐心和，王吴，等.一种基于经验的德州扑克博奔系统架构.智能系统学报，2020,15(3)：468-474. 英文引用格式：GAO Qiang,XU Xinhe,WANG Hao,.et al.System architecture of Texas Hold'em based on experienceJ.CAAl transactions on intelligent systems,2020,15(3):468-474. System architecture of Texas Hold'em based on experience GAO Qiang XU Xinhe',WANG Hao',BAI Guoli,CAO Ruimin' (1.Key Laboratory of Manufacturing Industrial Integrated Automation,Shenyang University,Shenyang 110044,China;2.College of Information Science and Engineering,Northeastern University,Shenyang 110819,China;3.School of Mechanical Engineering and Automation,Northeastern University,Shenyang 110819,China) Abstract:To improve the level of Texas Hold'em through historical experience,this paper proposes a system architec- ture of heads-up no-limit Texas Hold'em for the knowledge base module.Mass historic games are used to train the deep learning network based on convolutional neural network,and an expert database is constructed for the search module of the system.Texas Hold'em structured game tree is developed and extended,and it is applied in terms of the expertise and historical experience to the core module for evaluation.A hand-ranking hash-based table is built to reduce the time required to evaluate hand rankings.The experimental result shows a higher playing level for the proposed system archi- tecture. Keywords:Heads-up no-limit Texas Hold'em;computer games;dynamic game with imperfect information; game tree;deep learning;expert database;Hash table;game strategy 德州扑克属于一种典型且复杂的非完全信息克博奔系统Polaris首次战胜了职业扑克选手。 动态博弈问题)，它是近年来计算机博弈领域的 2015年1月，加拿大阿尔伯特大学在Science期刊 学者们重点研究的热点问题。2006年，加拿大阿 上发表了一篇关于德州扑克博弈问题最新研究成 果的文章)，该研究小组开发了两人参与的有赌 尔伯特大学(University of Alberta)作为主办方举 注上限的德州扑克博弈系统，并得到了该博弈问 办了首届国际计算机扑克大赛)；2007年，德州扑 题的理论解。但是二人赌注无上限的德州扑克问 收稿日期：2018-03-26. 基金项目：辽宁省自然科学基金项目(20180550146.20170520386. 题，由于具有更高的复杂度（文献[6]证明了此类 通信作者：高强.E-mail:tommy_.06@163.com. 问题属于NP-hard问题)，一直没有实现求解
DOI: 10.11992/tis.201803043 一种基于经验的德州扑克博弈系统架构 高强1 ，徐心和2 ，王昊3 ，白国力3 ，曹瑞珉3 （1. 沈阳大学 辽宁省装备制造综合自动化重点实验室，辽宁 沈阳 110044; 2. 东北大学 信息科学与工程学院， 辽宁 沈阳 110819; 3. 东北大学 机械工程与自动化学院，辽宁 沈阳 110819） 摘 要：为了利用历史经验知识提高德州扑克博弈水平，提出一种二人赌注无上限的德州扑克博弈系统架构： 对于知识库模块，利用海量历史牌局训练得到基于 CNN 的深度学习网络模型并构建了一个专家经验库；在系 统的搜索模块中，构建了一种分阶段的德州扑克博弈树，利用专家经验和历史经验引导德州扑克博弈树的展 开；对于系统的估值核心模块，构建了一种基于哈希技术的牌型对照表，以提高系统判定胜负的效率。实验结 果表明本文提出的博弈系统架构具有更高的对弈水平。 关键词：二人赌注无上限德州扑克；计算机博弈；非完全信息动态博弈；博弈树；深度学习；专家库；哈希表；博 弈策略 中图分类号：TP301.5 文献标志码：A 文章编号：1673−4785(2020)03−0468−07 中文引用格式：高强, 徐心和, 王昊, 等. 一种基于经验的德州扑克博弈系统架构 [J]. 智能系统学报, 2020, 15(3): 468–474. 英文引用格式：GAO Qiang, XU Xinhe, WANG Hao, et al. System architecture of Texas Hold’em based on experience[J]. CAAI transactions on intelligent systems, 2020, 15(3): 468–474. System architecture of Texas Hold’em based on experience GAO Qiang1 ，XU Xinhe2 ，WANG Hao3 ，BAI Guoli3 ，CAO Ruimin3 (1. Key Laboratory of Manufacturing Industrial Integrated Automation, Shenyang University, Shenyang 110044, China; 2. College of Information Science and Engineering, Northeastern University, Shenyang 110819, China; 3. School of Mechanical Engineering and Automation, Northeastern University, Shenyang 110819, China) Abstract: To improve the level of Texas Hold’em through historical experience, this paper proposes a system architecture of heads-up no-limit Texas Hold’em for the knowledge base module. Mass historic games are used to train the deep learning network based on convolutional neural network, and an expert database is constructed for the search module of the system. Texas Hold’em structured game tree is developed and extended, and it is applied in terms of the expertise and historical experience to the core module for evaluation. A hand-ranking hash-based table is built to reduce the time required to evaluate hand rankings. The experimental result shows a higher playing level for the proposed system architecture. Keywords: Heads-up no-limit Texas Hold’em; computer games; dynamic game with imperfect information; game tree; deep learning; expert database; Hash table; game strategy 德州扑克属于一种典型且复杂的非完全信息 动态博弈问题[1-2] ，它是近年来计算机博弈领域的 学者们重点研究的热点问题。2006 年，加拿大阿 尔伯特大学 (University of Alberta) 作为主办方举 办了首届国际计算机扑克大赛[3] ；2007 年，德州扑 克博弈系统 Polaris 首次战胜了职业扑克选手[4]。 2015 年 1 月，加拿大阿尔伯特大学在 Science 期刊 上发表了一篇关于德州扑克博弈问题最新研究成 果的文章[5] ，该研究小组开发了两人参与的有赌 注上限的德州扑克博弈系统，并得到了该博弈问 题的理论解。但是二人赌注无上限的德州扑克问 题，由于具有更高的复杂度 (文献 [6] 证明了此类 问题属于 NP-hard 问题)，一直没有实现求解。 收稿日期：2018−03−26. 基金项目：辽宁省自然科学基金项目 (20180550146，20170520386). 通信作者：高强. E-mail：tommy_06@163.com. 第 15 卷第 3 期 智 能 系 统 学 报 Vol.15 No.3 2020 年 5 月 CAAI Transactions on Intelligent Systems May 2020
第3期 高强，等：一种基于经验的德州扑克博弈系统架构 ·469· 2017年1月30日，美国卡耐基梅隆大学开发的德 德州扑克博弈系统 州扑克博弈系统Libratus与4名人类顶尖德州扑 克选手之间的“人机大战”在美国匹兹堡结束，最 终人工智能取得胜利。这是人工智能在各种棋 牌博弈中对人类取得的又一个胜利。本文提出一 种二人赌注无上限的德州扑克博弈系统架构，构 数据表示 走法生成 搜索引擎 估值 知识库 建了一个专家经验库；利用海量历史牌局训练得 心 到基于CNN的深度学习网络模型；在系统的搜索 模块中，构建了一种分阶段的德州扑克博弈树， 图1德州扑克博弈系统架构中的模块组成 利用专家经验和历史经验引导德州扑克博弈树的 Fig.1 Modules of the system architecture of Texas Hold'em 展开；对于系统的估值核心模块，构建了一种基 于哈希技术的牌型对照表，以提高系统判定胜负 德州扑克博弈系统主要由5个模块组成，其 中数据表示，主要指德州扑克博弈问题中的扑克 的效率。 牌和走法（即下注行为）如何在计算机系统中表 1二人赌注无上限德州扑克 示，根据德州扑克的规则，共有52张牌，没有大、 小王。本系统采用二维数组来表示52张扑克牌， 1.1二人赌注无上限德州扑克规则 即poker[4][13],第一维表示扑克牌的花色，下标 二人赌注无上限德州扑克是一种双人的扑克 0、1、2、3分别表示黑桃、红心、方块、梅花：对于 游戏。一共有52张牌，没有大、小王。每个玩家 走法，在德州扑克中就是两个玩家的下注行为， 分两张扑克牌作为底牌（只有本方可见，其他玩 根据规则，玩家的下注行为包括下注、加注、看 家不可见)，另有5张是所有玩家可见的公共扑克 牌、跟注和弃牌，在系统中用5个整型常量(1~5) 牌被陆续发出。其具体规则如下。 来表示。 首先，每个玩家分别得到两张底牌（称为Pre 走法生成模块是指对于某个德州扑克局面， f1op阶段)，随着第一轮两个玩家交替下注后，开 用此模块产生具体的走法，德州扑克的牌局局面 始陆续发公共牌： 分为玩家下注时对应的局面和发公共牌的局面。 1)第1次发牌将同时发3张公共牌（称为 对于下注时对应的局面，其走法就是玩家的下注 op阶段)，然后由小盲注开始表态，玩家可以选 行为，根据规则，每个发牌阶段先表态的玩家允 择下注、加注或者盖牌放弃，若有一个玩家弃牌， 许的下注行为包括下注、看牌和跟注，后表态的 则此次牌局结束； 玩家允许的下注行为包括加注、跟注和弃牌：对 2)第2次发牌只发1张公共牌（即第4张公 于发公共牌的局面，其走法就是生成某个发牌阶 共牌，Turn阶段)，由小盲注开始轮流表态； 段所有可能被发放的公共牌组合。搜索引擎、估 3)第3次发牌是发第5张公共牌(River阶 值核心和知识库这3个模块的设计将在后面的章 段)，由小盲注开始轮流表态。 节详细阐述。 最后，亮底牌并开始比牌(Showdown阶段)， 由手中的2个底牌、5张公共牌中的任意3张，组 2分阶段的德州扑克博弈树 成5张最大的牌型进行互相比较，牌型最大的玩 2.1德州扑克博弈树总体设计 家赢得赌注池中的筹码。牌型大小依次为：同花 对于德州扑克问题，下注阶段包括Preflop、 顺、四条（如4张2）、葫芦(3带2)、同花、顺子、三 Flop、Turn、River共4个阶段。随着手牌及公共 条、两对、一对、高牌。若两个玩家拥有的5张牌 牌的发放，随机性和不确定性的逐渐降低，各个 牌型大小相同，则赌池中的筹码被两个玩家平 阶段的搜索策略并不相同。对于系统的搜索引擎 分。小盲注双方轮换担任，每一局有4轮下注的 模块，本文设计了一种分阶段的二人赌注无上限 机会，每一轮加注次数不限。 德州扑克博弈树（总体流程图见图2），由于对方 1.2德州扑克博弈系统架构中的模块组成 手牌不可见，博弈树搜索模块首先要生成所有可 德州扑克问题是一种典型的非完全信息动态 能的对方手牌牌型，然后根据每两张具体牌型以 博弈问题，其博弈系统架构与完全信息动态博弈 及目前牌局所处的下注阶段展开一轮下注过程 问题（如围棋、中国象棋等）相似，具体的模块组 以此类推，进而描述在该下注阶段之后，牌局的 成如图1所示。 完整对弈过程。当博弈树展开到叶子节点(Show
2017 年 1 月 30 日，美国卡耐基梅隆大学开发的德 州扑克博弈系统 Libratus 与 4 名人类顶尖德州扑 克选手之间的“人机大战”在美国匹兹堡结束，最 终人工智能取得胜利[7]。这是人工智能在各种棋 牌博弈中对人类取得的又一个胜利。本文提出一 种二人赌注无上限的德州扑克博弈系统架构，构 建了一个专家经验库；利用海量历史牌局训练得 到基于 CNN 的深度学习网络模型；在系统的搜索 模块中，构建了一种分阶段的德州扑克博弈树， 利用专家经验和历史经验引导德州扑克博弈树的 展开；对于系统的估值核心模块，构建了一种基 于哈希技术的牌型对照表，以提高系统判定胜负 的效率。 1 二人赌注无上限德州扑克 1.1 二人赌注无上限德州扑克规则 二人赌注无上限德州扑克是一种双人的扑克 游戏。一共有 52 张牌，没有大、小王。每个玩家 分两张扑克牌作为底牌 (只有本方可见，其他玩 家不可见)，另有 5 张是所有玩家可见的公共扑克 牌被陆续发出。其具体规则[8] 如下。 首先，每个玩家分别得到两张底牌 (称为 Preflop 阶段)，随着第一轮两个玩家交替下注后，开 始陆续发公共牌： 1) 第 1 次发牌将同时发 3 张公共牌 (称为 flop 阶段)，然后由小盲注开始表态，玩家可以选 择下注、加注或者盖牌放弃，若有一个玩家弃牌， 则此次牌局结束； 2) 第 2 次发牌只发 1 张公共牌 (即第 4 张公 共牌，Turn 阶段)，由小盲注开始轮流表态； 3) 第 3 次发牌是发第 5 张公共牌 (River 阶 段)，由小盲注开始轮流表态。 最后，亮底牌并开始比牌 (Showdown 阶段)， 由手中的 2 个底牌、5 张公共牌中的任意 3 张，组 成 5 张最大的牌型进行互相比较，牌型最大的玩 家赢得赌注池中的筹码。牌型大小依次为：同花 顺、四条 (如 4 张 2)、葫芦 (3 带 2)、同花、顺子、三 条、两对、一对、高牌。若两个玩家拥有的 5 张牌 牌型大小相同，则赌池中的筹码被两个玩家平 分。小盲注双方轮换担任，每一局有 4 轮下注的 机会，每一轮加注次数不限。 1.2 德州扑克博弈系统架构中的模块组成 德州扑克问题是一种典型的非完全信息动态 博弈问题，其博弈系统架构与完全信息动态博弈 问题 (如围棋、中国象棋等) 相似，具体的模块组 成如图 1 所示。 德州扑克博弈系统 数据表示 走法生成 搜索引擎 估值核心 知识库 图 1 德州扑克博弈系统架构中的模块组成 Fig. 1 Modules of the system architecture of Texas Hold’em 德州扑克博弈系统主要由 5 个模块组成，其 中数据表示，主要指德州扑克博弈问题中的扑克 牌和走法 (即下注行为) 如何在计算机系统中表 示，根据德州扑克的规则，共有 52 张牌，没有大、 小王。本系统采用二维数组来表示 52 张扑克牌， 即 poker[4][13]，第一维表示扑克牌的花色，下标 0、1、2、3 分别表示黑桃、红心、方块、梅花；对于 走法，在德州扑克中就是两个玩家的下注行为， 根据规则，玩家的下注行为包括下注、加注、看 牌、跟注和弃牌，在系统中用 5 个整型常量 (1~5) 来表示。 走法生成模块是指对于某个德州扑克局面， 用此模块产生具体的走法，德州扑克的牌局局面 分为玩家下注时对应的局面和发公共牌的局面。 对于下注时对应的局面，其走法就是玩家的下注 行为，根据规则，每个发牌阶段先表态的玩家允 许的下注行为包括下注、看牌和跟注，后表态的 玩家允许的下注行为包括加注、跟注和弃牌；对 于发公共牌的局面，其走法就是生成某个发牌阶 段所有可能被发放的公共牌组合。搜索引擎、估 值核心和知识库这 3 个模块的设计将在后面的章 节详细阐述。 2 分阶段的德州扑克博弈树 2.1 德州扑克博弈树总体设计 对于德州扑克问题，下注阶段包括 Preflop、 Flop、Turn、River 共 4 个阶段。随着手牌及公共 牌的发放，随机性和不确定性的逐渐降低，各个 阶段的搜索策略并不相同。对于系统的搜索引擎 模块，本文设计了一种分阶段的二人赌注无上限 德州扑克博弈树 (总体流程图见图 2)，由于对方 手牌不可见，博弈树搜索模块首先要生成所有可 能的对方手牌牌型，然后根据每两张具体牌型以 及目前牌局所处的下注阶段展开一轮下注过程， 以此类推，进而描述在该下注阶段之后，牌局的 完整对弈过程。当博弈树展开到叶子节点 (Show- 第 3 期 高强，等：一种基于经验的德州扑克博弈系统架构 ·469·
·470· 智能系统学报 第15卷 down node),调用估值函数，判定胜负关系并计算 调用估值函数来评价每个叶子节点的优劣。根据 输赢筹码量。 德州扑克对弈规则，Showdown阶段需要比较双 开始) 方5张扑克牌的牌型大小，牌型大小依次为：同花 顺、四条、葫芦、同花、顺子、三条、两对、一对、 生成对手手牌牌型 高牌。通过程序进行牌型在线判断的方式，过于 繁琐且影响系统的搜索效率。 P1 preflop 本文提出一种基于哈希技术0的牌型大小对 flop P2 照预置表。哈希技术在棋类博弈问题（比如中国 turn P3 象棋启发式搜索及开局、残局库中经常用到， river 基于哈希技术的置换表是启发式搜索中最为重要 P4 的算法，在计算机博弈系统中起着十分重要的作 得到最佳下注行为 用。作为混合博弈树搜索引擎中的一种启发式搜 索算法，在搜索中如果有和置换表中相同的节 计算筹码量 点，不用再向下搜索，可以直接调用表中的记录， 这样省去了很多时间，从而提高了搜索引擎的效 (结束 率2。本文将哈希技术用于建立德州扑克牌型 图2德州扑克博弈树搜索总体PAD图 大小对照表，在程序启动时，将牌型大小对照表 Fig.2 Overall problem analysis diagram of the game tree 加载到内存中，采用查表的形式代替繁琐的牌型 2.2一轮下注过程的博弈树描述 判断，缩短判断牌型大小所需的时间，以提高引 根据德州扑克的规则，每个发牌阶段发完公 擎的搜索效率。 共牌之后，两个玩家需要交替下注，图3显示了德 3.1牌型对照表的设计 州扑克一轮下注过程的博弈树，博弈树包括： 牌型对照表由牌型种类、同类牌型中的排 1)玩家节点（如图3中的圆形节点）。对于二 名、是否已有数据标志位及牌型识别码4个字段 人的德州扑克问题，该节点表示本方玩家或对方 组成。表的每一行占16个字节，表的尺寸为 玩家，这两种节点在博弈树中交替出现。 2.6M×16B≈42MB(其中2.6M为C2=2598960), 2)机会节点（如图3中的六边形节点）。该节 采用哈希技术，随机生成52张扑克牌的32位整 点表示当前牌局进入下一轮发牌阶段。 数和64位整数（即两个4×13的二维数组），通过 3)每个玩家节点包含3种下注行为（如图3 各个扑克牌对应的数组元素进行异或运算，其中 中的分支)。根据规则，每个玩家只有3种下注行 运算得到的64位整数代表5张扑克牌牌型：32位 为，即弃牌、下注加注、看牌/跟注。 整数&0x3 FFFFFF得到26位地址作为该牌型在表 的主键（即数组下标）。定义表结构的伪代码如下： struct Hashltem 弃牌 加注 看碑 short type;∥牌型类型标示位 B B short1 flag:/∥该位置是否已存放数据的标志位 弃牌 加注 弃牌 加注 int ranking;/同类牌型中的排名 跟注 跟注 unsigned_int64 checksum;,/5张扑克牌的64位 函 A 识别码 加注 加注 3.2牌型对照表的构建 图3德州扑克一轮下注过程的博弈树示意图 在系统启动时，生成基于哈希技术的牌型对 Fig.3 A part of the betting round 照表，利用查表代替繁琐的程序判断，实现快速 3基于哈希技术的德州扑克牌型对 比较双方在Showdown阶段的牌型大小。具体构 照表 建的流程如下： 1)牌型对照表由基本表和溢出表组成（这种 在博弈树展开到叶子节点（亮底牌）时，需要 设计主要用于解决哈希冲突问题，在3.4节有具
down node)，调用估值函数，判定胜负关系并计算 输赢筹码量。 开始 生成对手手牌牌型 得到最佳下注行为 计算筹码量 结束 P1 P2 P3 P4 preflop flop turn river 图 2 德州扑克博弈树搜索总体 PAD 图 Fig. 2 Overall problem analysis diagram of the game tree 2.2 一轮下注过程的博弈树描述 根据德州扑克的规则，每个发牌阶段发完公 共牌之后，两个玩家需要交替下注，图 3 显示了德 州扑克一轮下注过程的博弈树[9] ，博弈树包括： 1) 玩家节点 (如图 3 中的圆形节点)。对于二 人的德州扑克问题，该节点表示本方玩家或对方 玩家，这两种节点在博弈树中交替出现。 2) 机会节点 (如图 3 中的六边形节点)。该节 点表示当前牌局进入下一轮发牌阶段。 3) 每个玩家节点包含 3 种下注行为 (如图 3 中的分支)。根据规则，每个玩家只有 3 种下注行 为，即弃牌、下注/加注、看牌/跟注。 跟注 弃牌 看牌 加注 弃牌 加注 跟注 弃牌 加注 加注 加注 A −1 B B +1 A +1 A 图 3 德州扑克一轮下注过程的博弈树示意图 Fig. 3 A part of the betting round 3 基于哈希技术的德州扑克牌型对 照表 在博弈树展开到叶子节点 (亮底牌) 时，需要 调用估值函数来评价每个叶子节点的优劣。根据 德州扑克对弈规则，Showdown 阶段需要比较双 方 5 张扑克牌的牌型大小，牌型大小依次为：同花 顺、四条、葫芦、同花、顺子、三条、两对、一对、 高牌。通过程序进行牌型在线判断的方式，过于 繁琐且影响系统的搜索效率。 本文提出一种基于哈希技术[10] 的牌型大小对 照预置表。哈希技术在棋类博弈问题 (比如中国 象棋[11] ) 启发式搜索及开局、残局库中经常用到， 基于哈希技术的置换表是启发式搜索中最为重要 的算法，在计算机博弈系统中起着十分重要的作 用。作为混合博弈树搜索引擎中的一种启发式搜 索算法，在搜索中如果有和置换表中相同的节 点，不用再向下搜索，可以直接调用表中的记录， 这样省去了很多时间，从而提高了搜索引擎的效 率 [12-14]。本文将哈希技术用于建立德州扑克牌型 大小对照表，在程序启动时，将牌型大小对照表 加载到内存中，采用查表的形式代替繁琐的牌型 判断，缩短判断牌型大小所需的时间，以提高引 擎的搜索效率。 3.1 牌型对照表的设计 C 5 52 牌型对照表由牌型种类、同类牌型中的排 名、是否已有数据标志位及牌型识别码 4 个字段 组成。表的每一行占 16 个字节，表的尺寸为 2.6M×16B≈42MB(其中 2.6 M 为 =2 598 960)， 采用哈希技术，随机生成 52 张扑克牌的 32 位整 数和 64 位整数 (即两个 4×13 的二维数组)，通过 各个扑克牌对应的数组元素进行异或运算，其中 运算得到的 64 位整数代表 5 张扑克牌牌型；32 位 整数&0x3FFFFFF 得到 26 位地址作为该牌型在表 的主键 (即数组下标)。定义表结构的伪代码如下： struct HashItem { short type;//牌型类型标示位 short flag;//该位置是否已存放数据的标志位 int ranking;//同类牌型中的排名 unsigned _int64 checksum;//5 张扑克牌的 64 位 识别码 } 3.2 牌型对照表的构建 在系统启动时，生成基于哈希技术的牌型对 照表，利用查表代替繁琐的程序判断，实现快速 比较双方在 Showdown 阶段的牌型大小。具体构 建的流程如下： 1) 牌型对照表由基本表和溢出表组成 (这种 设计主要用于解决哈希冲突问题，在 3.4 节有具 ·470· 智 能 系 统 学 报 第 15 卷
第3期 高强，等：一种基于经验的德州扑克博弈系统架构 ·471· 体阐述) 免。对于博弈树搜索中的基于哈希技术的置换 2)随机生成扑克牌的32位随机整数和64位 表来说，即使存在冲突，可以通过搜索代替查表， 随机整数； 影响的只是搜索效率；而本文提出的牌型对照 3)分别生成同花、四条、葫芦、顺子等5张扑 表，用于Showdown阶段比较双方牌型大小，包含 克牌牌型种类中的所有牌型，并存放到哈希表 了所有的5张扑克牌牌型，不允许存在冲突。 中。以同花顺为例，根据4种花色和每个花色将 本文采取建立公共溢出区与开放定址法相 “A”到“5”的牌型作为循环嵌套： 结合的方式来解决哈希表存在的冲突，具体设计 ①分别取5张连续的扑克牌，取出相应扑克 思路如下： 牌32位、64位随机整数，做异或运算； 1)将哈希表尺寸扩大到64MB,提高表的散 ②根据异或得到的32位整数，计算26位地址； 列度； ③计算并写入排名字段，标志位fag置l; 2)将数据存放到基本哈希表； ④写入类型字段： 3)若哈希值冲突，则存放到公共溢出表中； ⑤写入64位哈希值，作为牌型识别码。 4)若公共溢出表中也存在相同哈希值的数 3.3查询牌型对照表 据，则采用开放定址法解决此冲突，即采用线性 德州扑克博弈树在展开到叶子节点(Show- 探测再散列的方法，将哈希值做加1、加2等处 down节点)时，需要查询牌型对照表来确定双方 理，找到接近冲突地址且空的位置，存放数据。 的胜负关系。查询牌型对照表的步骤如下： 3.5得到两个表的最佳内存分配方案 1)分别从双方的7张扑克牌中，找到牌型最 以一种德州扑克牌局局面为例，根据分配给 大的5张扑克牌牌型，即 基本哈希对照表和溢出表不同的存储空间，比较 ①首先从7张扑克牌中，生成所有的5张扑 冲突数和搜索时间的差别；这里设定了一个Flop 克牌组合； 阶段的牌局状态，通过完成一次搜索来比较表占 ②遍历这个集合，排除高牌的牌型； 用内存的大小、发生的冲突数对搜索效率的影 ③查询牌型对照表，得到具体牌型类型和在 响，进而得到一个最佳的内存空间分配方案。 该类型中的排名； 以一个局面状态为例，根据分配给基本哈希 ④相互比较，得到最大的牌型； 对照表和溢出表不同的存储空间，比较冲突数和 ⑤若所有牌型都为高牌，则对这些牌型按照 搜索时间的差别；这里设定了一个lop阶段的牌 数值降序排列，再相互比较得到最大的牌型； 局状态，通过完成一次搜索来比较表占用内存的 2)与对方的最大牌型进行比较，判定胜负 大小、发生的冲突数对搜索效率的影响，进而得 关系。 到一个最佳的内存空间分配方案。测试例子： 3.4哈希冲突的解决方法 AI手牌为“AsKh”,FIop阶段的公共牌为 基于哈希技术的牌型对照表虽然可以提高查 “9d8s7d”,其中，s表示黑桃，h表示红桃，d表示 询效率，但是哈希技术存在一个缺陷，即哈希冲 方块。 突。哈希冲突是指：关键字keyl≠key2,但是 根据表1和表2的测试结果，最终得到基本 H(key1)=H(key2),这里H表示哈希函数。无论哈 表和溢出表的最佳分配方案为：基本表占用128MB、 希函数多么地散列，哈希表存在的冲突都无法避 溢出表占用128MB。 表1占用内存空间、发生的冲突数及查询时间对照表（溢出表大小为128MB) Table 1 Comparison of memory space,hash collisions and time consumed (size of the overflow table:128 MB) 对照表申请的内存空间MB 冲突数 查询消耗的时间/ms 16 555067 60988 32 332746 61312 64 172883 59590 128 90545 58529 1024 13517 59848 2048 4537 62789
体阐述)； 2) 随机生成扑克牌的 32 位随机整数和 64 位 随机整数； 3) 分别生成同花、四条、葫芦、顺子等 5 张扑 克牌牌型种类中的所有牌型，并存放到哈希表 中。以同花顺为例，根据 4 种花色和每个花色将 “A”到“5”的牌型作为循环嵌套： ①分别取 5 张连续的扑克牌，取出相应扑克 牌 32 位、64 位随机整数，做异或运算； ② 根据异或得到的 32 位整数，计算 26 位地址； ③ 计算并写入排名字段，标志位 flag 置 1； ④ 写入类型字段； ⑤ 写入 64 位哈希值，作为牌型识别码。 3.3 查询牌型对照表 德州扑克博弈树在展开到叶子节点 (Showdown 节点) 时，需要查询牌型对照表来确定双方 的胜负关系。查询牌型对照表的步骤如下： 1) 分别从双方的 7 张扑克牌中，找到牌型最 大的 5 张扑克牌牌型，即 ①首先从 7 张扑克牌中，生成所有的 5 张扑 克牌组合； ② 遍历这个集合，排除高牌的牌型； ③ 查询牌型对照表，得到具体牌型类型和在 该类型中的排名； ④ 相互比较，得到最大的牌型； ⑤ 若所有牌型都为高牌，则对这些牌型按照 数值降序排列，再相互比较得到最大的牌型； 2) 与对方的最大牌型进行比较，判定胜负 关系。 3.4 哈希冲突的解决方法 基于哈希技术的牌型对照表虽然可以提高查 询效率，但是哈希技术存在一个缺陷，即哈希冲 突。哈希冲突是指：关键字 key1≠key2，但是 H(key1)=H(key2)，这里 H 表示哈希函数。无论哈 希函数多么地散列，哈希表存在的冲突都无法避 免 [15]。对于博弈树搜索中的基于哈希技术的置换 表来说，即使存在冲突，可以通过搜索代替查表， 影响的只是搜索效率；而本文提出的牌型对照 表，用于 Showdown 阶段比较双方牌型大小，包含 了所有的 5 张扑克牌牌型，不允许存在冲突。 本文采取建立公共溢出区与开放定址法[16] 相 结合的方式来解决哈希表存在的冲突，具体设计 思路如下： 1) 将哈希表尺寸扩大到 64 MB，提高表的散 列度； 2) 将数据存放到基本哈希表； 3) 若哈希值冲突，则存放到公共溢出表中； 4) 若公共溢出表中也存在相同哈希值的数 据，则采用开放定址法解决此冲突，即采用线性 探测再散列的方法[16] ，将哈希值做加 1、加 2 等处 理，找到接近冲突地址且空的位置，存放数据。 3.5 得到两个表的最佳内存分配方案 以一种德州扑克牌局局面为例，根据分配给 基本哈希对照表和溢出表不同的存储空间，比较 冲突数和搜索时间的差别；这里设定了一个 Flop 阶段的牌局状态，通过完成一次搜索来比较表占 用内存的大小、发生的冲突数对搜索效率的影 响，进而得到一个最佳的内存空间分配方案。 以一个局面状态为例，根据分配给基本哈希 对照表和溢出表不同的存储空间，比较冲突数和 搜索时间的差别；这里设定了一个 Flop 阶段的牌 局状态，通过完成一次搜索来比较表占用内存的 大小、发生的冲突数对搜索效率的影响，进而得 到一个最佳的内存空间分配方案。测试例子： A I 手牌为 “AsKh” ， Flo p 阶段的公共牌为 “9d8s7d”，其中，s 表示黑桃，h 表示红桃，d 表示 方块。 根据表 1 和表 2 的测试结果，最终得到基本 表和溢出表的最佳分配方案为：基本表占用 128 MB、 溢出表占用 128 MB。 表 1 占用内存空间、发生的冲突数及查询时间对照表 (溢出表大小为 128 MB) Table 1 Comparison of memory space, hash collisions and time consumed (size of the overflow table: 128 MB) 对照表申请的内存空间/MB 冲突数 查询消耗的时间/ms 16 555 067 60 988 32 332 746 61 312 64 172 883 59 590 128 90 545 58 529 1 024 13 517 59 848 2 048 4 537 62 789 第 3 期 高强，等：一种基于经验的德州扑克博弈系统架构 ·471·
·472· 智能系统学报 第15卷 表2占用内存空间、发生的冲突数及查询时间对照表（溢出表大小为256MB) Table 2 Comparison of memory space,hash collisions and time consumed(size of the overflow table:256 MB) 对照表申请的内存空间MB 冲突数 查询消耗的时间/ms 16 555067 61436 32 332746 59356 64 172883 60459 128 90545 61088 1024 13517 61494 2048 4537 61112 4专家库和深度学习网络 4×13矩阵扩展到20×20矩阵，空位用0填补。牌 局中出现的玩家决策行为及产生的筹码量也放在 德州扑克属于非完全信息动态博弈问题，对 这个矩阵中。 弈过程中对手的底牌不公开，导致博弈树中对手 节点的决策行为难以判断，这就加大了博弈树的 历史牌 txt文件 复杂度。本文在德州扑克博弈系统中构建了知识 局文件 转换程序 库：通过对历史牌局的学习，提高系统的对弈经 csv文件 验，根据经验展开对手神经网络建议的决策行 为：构建了专家经验库，根据当前牌局局面给出 输出 深度学习tensorflow 神经网络 本方玩家节点的决策行为建议。这在一定程度上 降低了博弈树的复杂度，提高了搜索效率。 4.1适用于德州扑克问题的深度学习神经网络 图4深度学习模块功能示意图 本文采用一种深度学习方法18一卷积神 Fig.4 Overall design of the deep learning module 经网络(convolutional neural networks,CNN),以 本文设计的卷积神经网络（图5），需要2个卷 海量历史牌局作为学习样本，利用已有知识预测 积层，即一个最大池化层（尺寸为2×2）和一个 对手的决策习惯0。通过国际计算机扑克博弈大 dropout层；每个卷积层都采用同一尺寸的卷积核 赛网站提供的历届若干位高水平德州扑克博弈系 (尺寸为5×5)。 统的历史牌局（约2千万个牌局）作为学习样本， 将历史牌局视为完全信息动态博弈，对每一场德 州扑克牌局采用卷积神经网络学习这些历史数 卷积 最大 据，从而掌握对手的决策行为建议。 输入 池化 卷积 全连接层 池化 输出 50 4.1.1总体设计 dropout 为了使卷积神经网络可以识别历史对弈数 图5卷积神经网络结构设计示意图 据，需要对牌局文件(txt文件)做处理，就是要一 Fig.5 Design of the convolutional neural network 行一行地读取文件中的牌局数据，并转换成卷积 4.1.3训练及测试深度学习神经网络 神经网络可以识别的csv文件。图4描述了深度 为了得到精度较高的深度学习神经网络，本 学习模块的总体设计。 文做了如下实验： 4.1.2学习历史牌局数据的卷积神经网络结构 1)从2000万个牌局中，随机抽取10万个； 设计 2)设定训练参数，并输出神经网络模型： 依据德州扑克对弈规则)，共有52张扑克 3)从剩余的海量牌局中，随机抽取6万个： 牌，系统可以采用二维数组表示对弈过程中的牌 4)设定测试参数，输出显示测试精度。 型，即poker!,1),每个数组元素用1表示已发放， 通过实验，得到如表3所示的实验结果，当训 0表示未发放。对于卷积神经网络的设计，本文 练次数达到5000次，每次抽取1024个样本，测 采用20×20的张量表示一张扑克牌，就是将 试精度可以达到99.74%
表 2 占用内存空间、发生的冲突数及查询时间对照表 (溢出表大小为 256 MB) Table 2 Comparison of memory space, hash collisions and time consumed (size of the overflow table: 256 MB) 对照表申请的内存空间/MB 冲突数 查询消耗的时间/ms 16 555 067 61 436 32 332 746 59 356 64 172 883 60 459 128 90 545 61 088 1 024 13 517 61 494 2 048 4 537 61 112 4 专家库和深度学习网络 德州扑克属于非完全信息动态博弈问题，对 弈过程中对手的底牌不公开，导致博弈树中对手 节点的决策行为难以判断，这就加大了博弈树的 复杂度。本文在德州扑克博弈系统中构建了知识 库：通过对历史牌局的学习，提高系统的对弈经 验，根据经验展开对手神经网络建议的决策行 为；构建了专家经验库，根据当前牌局局面给出 本方玩家节点的决策行为建议。这在一定程度上 降低了博弈树的复杂度，提高了搜索效率。 4.1 适用于德州扑克问题的深度学习神经网络 本文采用一种深度学习方法[17-18] −卷积神 经网络[19] (convolutional neural networks，CNN)，以 海量历史牌局作为学习样本，利用已有知识预测 对手的决策习惯[20]。通过国际计算机扑克博弈大 赛网站提供的历届若干位高水平德州扑克博弈系 统的历史牌局 (约 2 千万个牌局) 作为学习样本， 将历史牌局视为完全信息动态博弈，对每一场德 州扑克牌局采用卷积神经网络学习这些历史数 据，从而掌握对手的决策行为建议。 4.1.1 总体设计 为了使卷积神经网络可以识别历史对弈数 据，需要对牌局文件 (txt 文件) 做处理，就是要一 行一行地读取文件中的牌局数据，并转换成卷积 神经网络可以识别的 csv 文件。图 4 描述了深度 学习模块的总体设计。 4.1.2 学习历史牌局数据的卷积神经网络结构 设计 依据德州扑克对弈规则[ 5 ] ，共有 52 张扑克 牌，系统可以采用二维数组表示对弈过程中的牌 型，即 poker[4,13] ，每个数组元素用 1 表示已发放， 0 表示未发放。对于卷积神经网络的设计，本文 采 用 20×2 0 的张量表示一张扑克牌，就是 将 4×13 矩阵扩展到 20×20 矩阵，空位用 0 填补。牌 局中出现的玩家决策行为及产生的筹码量也放在 这个矩阵中。 深度学习tensorflow 转换程序 历史牌 局文件 csv文件 神经网络 输出 txt文件 图 4 深度学习模块功能示意图 Fig. 4 Overall design of the deep learning module 本文设计的卷积神经网络 (图 5)，需要 2 个卷 积层，即一个最大池化层 (尺寸为 2×2) 和一个 dropout 层；每个卷积层都采用同一尺寸的卷积核 (尺寸为 5×5)。 输入 卷积 最大 池化 卷积 最大 池化 全连接层 50% dropout 输出 图 5 卷积神经网络结构设计示意图 Fig. 5 Design of the convolutional neural network 4.1.3 训练及测试深度学习神经网络 为了得到精度较高的深度学习神经网络，本 文做了如下实验： 1) 从 2 000 万个牌局中，随机抽取 10 万个； 2) 设定训练参数，并输出神经网络模型； 3) 从剩余的海量牌局中，随机抽取 6 万个； 4) 设定测试参数，输出显示测试精度。 通过实验，得到如表 3 所示的实验结果，当训 练次数达到 5 000 次，每次抽取 1 024 个样本，测 试精度可以达到 99.74%。 ·472· 智 能 系 统 学 报 第 15 卷
第3期 高强，等：一种基于经验的德州扑克博弈系统架构 ·473· 表3训练参数设置及测试精度对照表 Table 3 Comparison of the training parameters'setting and test accuracy 训练次数 训练量 测试次数 测试量 精度% 500 32 10 32 88.12 1000 128 10 128 94 1000 1024 10 1024 99.12 2000 1024 10 1024 99.3 5000 1024 10 1024 99.74 4.2适用于德州扑克问题的专家经验库 1000局（对弈规则：每局双方分别拥有20000个 博弈树展开过程中，对于玩家节点，一般有 筹码，筹码量一局一复位；大小盲注身份一局一 3种下注行为（即着法，博弈树中玩家节点的分 交换；以最终赢得筹码量的多少判定胜负关系)， 支)。为了提高德州扑克博弈树展开的效率，本文 根据胜负关系来比较两个系统的优劣。 依据专家经验，为本方玩家节点选择最佳决策行为。 根据表4显示的对弈结果可知，EXP+CNN 德州扑克在Preflop阶段，没有发放公共牌， 版本的系统对弈EXP+EXP版本时，赢得了比较 不确定性过大，如果展开博弈树，由于博弈树中 多的筹码，说明利用深度学习模型预测对手行为 包含太多随机因素，搜索效率很低且不够准确。 更加准确：实验中的人类玩家就是专家库的开发 因此，本文在Preflop阶段，不展开博弈树，而是根 者，从表4可看到，人类玩家与EXP+EXP版本的 据本方手牌牌型和对方的下注行为，来查询专家 系统对弈水平十分接近。另外，EXP+CNN版本 库，直接决定本方下注行为。本文分别建立了 的德州扑克博弈系统在2018中国大学生计算机 Preflop阶段手牌分析专家库及Flop、Turn、River 博弈大赛上获得季军。没有取得更好成绩的主要 阶段专家库。 原因：作为深度学习神经网络的输入数据，历史 4.3实验 牌局没有经过仔细的筛选，如果选择那些更高水 将专家库+深度学习（以下简称为EXP+ 平德州扑克博弈系统比赛的历史牌局作为输入数 CNN)德州扑克博弈系统与专家库+专家库（以下 据，训练得到的深度学习网络模型一定能够给出 简称为EXP+EXP)版本的博弈系统进行对弈 更优的决策行为。 表4两个版本博弈系统对弈1000局的胜负关系 Table 4 Results of two versions of the game system playing 1 000 games 系统版本 EXP +CNN EXP+EXP Human Expert EXP+CNN 32620筹码 92561筹码 EXP+EXP -32620筹码 631筹码 Human Expert -92561筹码 -631筹码 5结束语 平。对于未来的研究工作，应该参考冷扑大师的 算法架构，在博弈系统中加入虚拟遗憾最小化算 本文提出一种二人赌注无上限的德州扑克博 法(counterfactual regret minimization,CFR),进一步 弈系统架构，在系统的搜索模块中，构建了一种 提高德州扑克博弈系统的对弈水平。 分阶段的德州扑克博弈树；在知识库模块中，构 建了专家经验库，引导博弈树中本方玩家节点的 参考文献： 决策分支展开；并通过学习海量历史牌局数据得 [1]OSBORNE M J,RUBINSTEIN A.A course in game the- 到一个深度学习神经网络，利用历史经验引导德 ory[M].Cambridge:MIT Press,1994. 州扑克博弈树中对方玩家节点的决策分支展开： [2]胡裕靖，高阳.扑克游戏中的不完美信息博弈凹.中国计 对于系统的估值核心模块，构建了一种基于哈希 算机学会通讯，2014,10(9)：37-42. 技术的牌型对照表，以提高系统判定胜负的效 HU Yujing,GAO Yang.Games with incomplete informa- 率。实验表明，该博弈系统具有较高的博弈水 tion in Pokers[J].China computer society newsletter,2014
表 3 训练参数设置及测试精度对照表 Table 3 Comparison of the training parameters’ setting and test accuracy 训练次数 训练量 测试次数 测试量 精度/% 500 32 10 32 88.12 1 000 128 10 128 94 1 000 1 024 10 1 024 99.12 2 000 1 024 10 1 024 99.3 5 000 1 024 10 1 024 99.74 4.2 适用于德州扑克问题的专家经验库 博弈树展开过程中，对于玩家节点，一般有 3 种下注行为 (即着法，博弈树中玩家节点的分 支)。为了提高德州扑克博弈树展开的效率，本文 依据专家经验，为本方玩家节点选择最佳决策行为。 德州扑克在 Preflop 阶段，没有发放公共牌， 不确定性过大，如果展开博弈树，由于博弈树中 包含太多随机因素，搜索效率很低且不够准确。 因此，本文在 Preflop 阶段，不展开博弈树，而是根 据本方手牌牌型和对方的下注行为，来查询专家 库，直接决定本方下注行为。本文分别建立了 Preflop 阶段手牌分析专家库及 Flop、Turn、River 阶段专家库。 4.3 实验 将专家库 +深度学 习 (以下简称 为 EXP + CNN) 德州扑克博弈系统与专家库+专家库 (以下 简称为 EXP+EXP) 版本的博弈系统进行对弈 1 000 局 (对弈规则：每局双方分别拥有 20 000 个 筹码，筹码量一局一复位；大小盲注身份一局一 交换；以最终赢得筹码量的多少判定胜负关系)， 根据胜负关系来比较两个系统的优劣。 根据表 4 显示的对弈结果可知，EXP + CNN 版本的系统对弈 EXP+EXP 版本时，赢得了比较 多的筹码，说明利用深度学习模型预测对手行为 更加准确；实验中的人类玩家就是专家库的开发 者，从表 4 可看到，人类玩家与 EXP+EXP 版本的 系统对弈水平十分接近。另外，EXP + CNN 版本 的德州扑克博弈系统在 2018 中国大学生计算机 博弈大赛上获得季军。没有取得更好成绩的主要 原因：作为深度学习神经网络的输入数据，历史 牌局没有经过仔细的筛选，如果选择那些更高水 平德州扑克博弈系统比赛的历史牌局作为输入数 据，训练得到的深度学习网络模型一定能够给出 更优的决策行为。 表 4 两个版本博弈系统对弈 1 000 局的胜负关系 Table 4 Results of two versions of the game system playing 1 000 games 系统版本 EXP + CNN EXP+EXP Human Expert EXP+CNN — 32 620筹码 92 561筹码 EXP+EXP −32 620筹码 — 631筹码 Human Expert −92 561筹码 −631筹码 — 5 结束语 本文提出一种二人赌注无上限的德州扑克博 弈系统架构，在系统的搜索模块中，构建了一种 分阶段的德州扑克博弈树；在知识库模块中，构 建了专家经验库，引导博弈树中本方玩家节点的 决策分支展开；并通过学习海量历史牌局数据得 到一个深度学习神经网络，利用历史经验引导德 州扑克博弈树中对方玩家节点的决策分支展开； 对于系统的估值核心模块，构建了一种基于哈希 技术的牌型对照表，以提高系统判定胜负的效 率。实验表明，该博弈系统具有较高的博弈水 平。对于未来的研究工作，应该参考冷扑大师的 算法架构，在博弈系统中加入虚拟遗憾最小化算 法 (counterfactual regret minimization，CFR)，进一步 提高德州扑克博弈系统的对弈水平。 参考文献： OSBORNE M J, RUBINSTEIN A. A course in game theory[M]. Cambridge: MIT Press, 1994. [1] 胡裕靖, 高阳. 扑克游戏中的不完美信息博弈 [J]. 中国计 算机学会通讯, 2014, 10(9): 37–42. HU Yujing, GAO Yang. Games with incomplete information in Pokers[J]. China computer society newsletter, 2014, [2] 第 3 期 高强，等：一种基于经验的德州扑克博弈系统架构 ·473·
·474· 智能系统学报 第15卷 10(9):37-42 tice Hall,1990:456-461,472 [3]LITTMAN M,ZINKEVICH M.The 2006 AAAI com- [17]DENG Li,YU Dong.Deep learning:methods and applic- puter-poker competition[J].ICGA journal,2006,29(3): ations[J].Foundations and trends in signal processing, 166-167. 2014.7(3):197-387. [4]HARRIS M.The first "Man-Machine Poker Champion- [18]BENGIO Y.Learning deep architectures for AI[Ml.Han- ship"begins tomorrow[N].Poker News,2007-07-22. over:Now Publishers Inc..2009. [5]BOWLING M.BURCH N.JOHANSON M.et al.Heads- [19]FUKUSHIMA K.Neocognitron:a self-organizing neural up limit hold'em poker is solved[J].Science,2015, network model for a mechanism of pattern recognition 3476218):145-149. unaffected by shift in position[J].Biological cybernetics, [6]BLAIR JR S,MUTCHLER D,LIU C.Games with imper- 1980.36(4)193-202 fect information[R].AAAI Technical Report FS-93-02. [20]YAKOVENKO N,CAO Liangliang,RAFFEL C,et al. American:AAAI.1993. Poker-CNN:a pattern learning strategy for making draws [7]HINTZE H.Libratus scores convincing sweep in man v. and bets in poker games[C].Proceedings of the Thirtieth machine poker match[N].Misc,News,2017-01-31. [8]BILLINGS D,DAVIDSON A,SCHAEFFER J,et al.The AAAI Conference on Artificial Intelligence.Phoenix, challenge of poker[J].Artificial intelligence,2002, USA,2016:360-367 134(1/2):201-240 作者简介： [9]BILLINGS D.Algorithms and assessment in computer 高强，讲师博士，主要研究方向 poker[D].Alberta:University of Alberta,2006. 为机器博弈、计算复杂性理论。 [10]ZOBRIST A L.A new hashing method with application for game playing[R].Madison,USA:University of Wis- consin,1970 [11]WANG Jiao,LI Sizhong,XU Xinhe.A minors hash table in Chinese-chess programs2[J].ICGA journal,2010, 33(1):18-33. 徐心和，教授，博士生导师，中国 [12]BREUKER D M,UITERWIJK J WH M,VAN DEN 人工智能学会常务理事，主要研究方 HERIK H J.Replacement schemes for transposition 向为控制理论与应用、系统仿真、智能 机器人、机器博弈。主持完成国家自 tables[J].ICGA journal,1994,17(4):183-193. 然科学基金、863基金、国家“八五” [13]BREUKER D M.UITERWIJK J W H M.HERIK H J.In- “九五”攻关课题13项，其中8项通过 formation in transposition tables[J].Advances in com- 省、部级鉴定，获科技进步奖国家三 puter chess,1997,27:199-211. 等1项，省部级科技进步奖多项。发表学术论文300余篇。 [14]NELSON B L.Hash tables in Cray blitz[J].ICGA journ- al1985,8(1):3-13 王吴，博士研究生，主要研究方向 [15]HYATT R M,COZZIE A.The effect of hash signature 为机器博弈。 collisions in a chess program[J].ICGA journal,2005, 28(3):131-139. [16]TENENBAUM A M.LANGSAM Y.AUGENSTEIN M J.Data structures using C[M].Englewood Cliffs:Pren-
10(9): 37–42. LITTMAN M, ZINKEVICH M. The 2006 AAAI computer-poker competition[J]. ICGA journal, 2006, 29(3): 166–167. [3] HARRIS M. The first “Man-Machine Poker Championship” begins tomorrow[N]. Poker News, 2007-07-22. [4] BOWLING M, BURCH N, JOHANSON M, et al. Headsup limit hold’em poker is solved[J]. Science, 2015, 347(6218): 145–149. [5] BLAIR J R S, MUTCHLER D, LIU C. Games with imperfect information[R]. AAAI Technical Report FS-93-02. American: AAAI, 1993. [6] HINTZE H. Libratus scores convincing sweep in man v. machine poker match[N]. Misc, News, 2017-01-31. [7] BILLINGS D, DAVIDSON A, SCHAEFFER J, et al. The challenge of poker[J]. Artificial intelligence, 2002, 134(1/2): 201–240. [8] BILLINGS D. Algorithms and assessment in computer poker[D]. Alberta: University of Alberta, 2006. [9] ZOBRIST A L. A new hashing method with application for game playing[R]. Madison, USA: University of Wisconsin, 1970. [10] WANG Jiao, LI Sizhong, XU Xinhe. A minors hash table in Chinese-chess programs2[J]. ICGA journal, 2010, 33(1): 18–33. [11] BREUKER D M, UITERWIJK J W H M, VAN DEN HERIK H J. Replacement schemes for transposition tables[J]. ICGA journal, 1994, 17(4): 183–193. [12] BREUKER D M, UITERWIJK J W H M, HERIK H J. Information in transposition tables[J]. Advances in computer chess, 1997, 27: 199–211. [13] NELSON B L. Hash tables in Cray blitz[J]. ICGA journal, 1985, 8(1): 3–13. [14] HYATT R M, COZZIE A. The effect of hash signature collisions in a chess program[J]. ICGA journal, 2005, 28(3): 131–139. [15] TENENBAUM A M, LANGSAM Y, AUGENSTEIN M J. Data structures using C[M]. Englewood Cliffs: Pren- [16] tice Hall, 1990: 456–461, 472. DENG Li, YU Dong. Deep learning: methods and applications[J]. Foundations and trends in signal processing, 2014, 7(3): 197–387. [17] BENGIO Y. Learning deep architectures for AI[M]. Hanover: Now Publishers Inc., 2009. [18] FUKUSHIMA K. Neocognitron: a self-organizing neural network model for a mechanism of pattern recognition unaffected by shift in position[J]. Biological cybernetics, 1980, 36(4): 193–202. [19] YAKOVENKO N, CAO Liangliang, RAFFEL C, et al. Poker-CNN: a pattern learning strategy for making draws and bets in poker games[C]. Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence. Phoenix, USA, 2016: 360–367. [20] 作者简介： 高强，讲师，博士，主要研究方向 为机器博弈、计算复杂性理论。 徐心和，教授，博士生导师，中国 人工智能学会常务理事，主要研究方 向为控制理论与应用、系统仿真、智能 机器人、机器博弈。主持完成国家自 然科学基金、863 基金、国家“八五”、 “九五”攻关课题 13 项，其中 8 项通过 省、部级鉴定，获科技进步奖国家三 等 1 项，省部级科技进步奖多项。发表学术论文 300 余篇。 王昊，博士研究生，主要研究方向 为机器博弈。 ·474· 智 能 系 统 学 报 第 15 卷