论文研究-基于蒙特卡洛树搜索的计算机德州扑克 .pdf

发布时间：2022-05-30 发布人：admin 分类：说明书资料大小：0.28M 资料格式：pdf 举报版权申诉

weixin_39840387-11577444-4744300845233414724.pdf-第1页.png

第1页 / 共6页

weixin_39840387-11577444-4744300845233414724.pdf-第2页.png

第2页 / 共6页

weixin_39840387-11577444-4744300845233414724.pdf-第3页.png

第3页 / 共6页

weixin_39840387-11577444-4744300845233414724.pdf-第4页.png

第4页 / 共6页

weixin_39840387-11577444-4744300845233414724.pdf-第5页.png

第5页 / 共6页

weixin_39840387-11577444-4744300845233414724.pdf-第6页.png

第6页 / 共6页

文本预览

5 10 15 20 25 30 35 40 中国科技论文在线 http://www.paper.edu.cn 基于蒙特卡洛树搜索的计算机德州扑克曹一鸣，刘知青 ** 北京邮电大学软件学院，北京 100876 摘要：计算机博弈是人工智能领域中的一个重要研究方向。相当长的时间内，相关研究主要集中于确定性完全信息博弈中的棋类游戏。另外一方面，由于更加贴近现实，关于于非确定性不完全信息博弈逐渐引起人们的重视，蒙特卡洛树搜索算法是一种经典的博弈树搜索算法，在计算机围棋领域取得了很大的成功。本文根据扑克的博弈特点，将蒙特卡洛树搜索算法应用于其中，同时结合基于贝叶斯方法的对手模型，设计开发一个具有一定人工智能水平的计算机多人有限注德州扑克引擎。关键词：人工智能；计算机博弈；德州扑克；蒙特卡洛树搜索；对手模型中图分类号：TP181 Computer Texas Hold'em based on Monte-Carlo Tree Search CAO Yiming, LIU Zhiqing 100876) (School of Software Engineering, Beijing University of Posts and Telecommunications, Beijing Abstract: Computer game is an significant research field of artifical intelligence. During an extended period, the correlational research focuses on the deterministic perfect information games, such as chess, go. On the other hand, as the more close integration with reality, the research about the stochastic imperfect information games trigger people's attention gradually. Monte-Carlo Tree Search is a classical algorithm in Game Tree Search, this method has got a big success in Computer Go. This paper combines MCTS with computer poker according to the characteristic of poker. At the same time, using the opponet model based on the Bayesian approach, finally, designs and implements a multi-player engine of Limited Texas Hold'em Poker with artifical intelligence. Key words: Artifical Intelligence; Computer Game; Texas Hold'em; Monte-Carlo Tree Search; Opponent Models 0 引言计算机博弈是测试人工智能所达到水平的一个重要平台。在传统的棋类博弈中，例如国际象棋、西洋跳棋，计算机都取得了优异的成绩，其中 1997 年 IBM 公司的“深蓝”超级计算机击败了国际象棋的世界大师 Kasparov；Schaeffer J[1]则是在数学上证明了西洋跳棋的可解性。现在对于棋类这种确定性完全信息博弈的研究主要集中于围棋这种古老的中国游戏上，虽然计算机围棋尚未取得国际象棋般的成功，但是借助蒙特卡洛树搜索算法[2]，计算机围棋在棋力上取得了巨大的提高。与这些传统的棋类博弈相比，德州扑克、桥牌这些广受欢迎的牌类博弈则是代表这计算机博弈之中的另外一个方向，也就是不确定性非完全信息博弈。相比较于确定性完全信息博弈，这类博弈与现实世界的契合度更高，更能够全面的模拟现实之中的问题，因此对于德州扑克这类博弈问题的研究逐渐成为了人工智能领域的又一个热点，同样我们有理由相信这样的研究更有助于将人工智能利用于现实之中。作者简介：曹一鸣（1988），男，硕士研究生，人工智能通信联系人：刘知青（1966-），男，教授，人工智能，. E-mail: zhiqing.liu@gmail.com - 1 -

中国科技论文在线 1 德克萨斯扑克 1.1 德州扑克 http://www.paper.edu.cn 45 50 55 德克萨斯扑克（英语：Texas Hold'em Poker，有时也写作 Texas Hold'em，通常简称为德州扑克）是世界上最流行的公牌扑克游戏，具有广泛的玩家群体，是国际扑克比赛的正式竞技项目之一。德州扑克规则简单，游戏使用没有大小王的 52 张扑克牌，允许 2 到 10 位玩家同时进行游戏，游戏的进行主要可以被划分为四个阶段，：翻牌前（Pre-flop）、翻牌阶段（Flop）、转牌阶段（Turn）以及河牌阶段（River）。为了保证在游戏结束时彩池内有一定数量的筹码可供分配，游戏规定庄家顺时针方向的第一位以及第二位下家被成为小盲注（Small bland）与大盲注（Big bland），他们将被分别强制向彩池内投注最小下注额一半以及等值的筹码。在四个阶段之中玩家可以根据自己手中的底牌以及牌桌上的公共牌为来决定自己的下注行为，选择跟注（Call）来匹配前一位玩家的下注额，或者加注（Raise）来增加投注额，抑或是放弃（Fold）放弃继续参见本次游戏的机会以及所有已经投注的筹码。游戏分为有限加注模式以及无限加注模式，本文主要的研究对象是有限加注模式的德州扑克。与棋类游戏相比，德州扑克主要存在四点不同[3]：非完全信息性：由于对手的底牌是不可见的，因此程序看到的游戏状态与对手看到的状态是不同的，这种非完全信息的特性极大的增加了决策的复杂性。非确定性：在游戏的过程之中存在发牌的事情，因此我们在决策的过程之中需要考虑到 60 这种随机事件的发生。部分可观测性：由于游戏规则的限制，在游戏中途放弃退出的玩家，我们无法获知其底牌的状况。多人游戏：与国际象棋、围棋这些双人博弈相比，德州扑克可以允许 2 到 10 个玩家一同进行，并且通常情况下玩家的数量超过两个人。 1.2 相关工作 65 早期对于德州扑克的研究主要分为两个方向：基于规则的专家系统：Billings et al[4]提出了一系列的公式用于对游戏的状态进行评估，其中包含了手牌强度（Hand strength）、手牌潜力（Hand potential）、有效手牌强度（Effective hand strength），Andersson[5]提出了彩池赔率的概念（Pot odds），然而这些方法在对游戏状态进行评估的时候采取的是静态评估，由于无法自适应的调整策略，其对于博弈中的决策提出了很大的限制。我们在文章第三部分介绍一种在线学习的博弈树搜索算法-蒙特卡罗树搜索算法用来弥补专家系统所带来的限制。基于博弈论的策略：在德州扑克之中应用最为成功的便是纳什均衡策略。纳什均衡是一种鲁棒性的静态策略，一般来说，如果一组策略被认为是均衡的，也就是说参与博弈的任何一方试图改变自己的策略时，都会降低自己的收益的预期[6]。Billings[7]通过对游戏状态进行抽取，提出了一个近似的纳什均衡策略。然而那是均衡策略前提假定我们面对的是一个最优化的对手，同时在博弈的过程之中最小化自己的损失，但是通常的情况是我们面对的并非是一个最优化的对手，这样使用纳什均衡策略仅仅使我们的损失最小化，却无法利用对手的缺点使我们的收益最大化[8]。在第四章，我们会给出一种对手模型的设计方式，用于利用对手的弱点，进而最大化收益。 70 75 80 - 2 -

中国科技论文在线 2 适应于德州扑克的蒙特卡洛树搜索算法 2.1 传统蒙特卡洛树搜索 http://www.paper.edu.cn 蒙特卡洛树搜索算法是将博弈树搜索算法以及随机算法之中的蒙特卡洛模拟相结合在一起的一种最优优先的搜索策略，这种算法最成功的应用在于求解计算机围棋问题，相关的研究成果 MoGo[9]，MANGO[10]，代表了计算机围棋领域的最高水准。蒙特卡洛树搜索算法选择性地扩展博弈树，树中的每一个节点对应着博弈之中的一个状态，节点不但需要表示博弈状态的相关信息，同时还包括节点的访问次数以及对于节点的评估值，这里的节点评估值并非是通过评估函数获得的，而是使用蒙特卡洛模拟评估出来的。蒙特卡洛树搜索算法的一个核心的思想就是逐步适应并改善的策略，随着算法迭代次数的增加，博弈树的尺寸逐步展开，而博弈树中结点的蒙特卡罗评估值也更加精确，这些精确的信息为我门提供大量丰富且 85 90 有用的信息，我们可以根据这些有用的信息来调整我们的选择策略。最终所选择的行为也会为结点带来一个较高的评估值[2]。为了更好地说明蒙特卡洛树搜索算法，如图 1 所示，我们将整个算法划分为四个部分： 95 图 1 蒙特卡洛树搜索算法选择阶段：算法从初始状态按照一定的选择策略递归地选择子节点，直到下降到树的边际节点。常用的选择策略主要有最大评估值策略、最优选择策略[11]。我们使用的是基于 UCT 的选择策略。这个策略将多臂匪徒问题的求解方法应用于博弈树之中，其最大的特点是能够 100 利用已有的经验，同时会结合对未知因素的一定的探索，这样可以通过对当前最优解的利用以及次优解的探索来向全局最优解进行逼近。UCT 的策略的选择过程是首先计算所有子节点的 UCB1 值，然后选择 UCB1 值最大的子节点，而节点的 UCB1 值的计算公式为： Z s a ( , ) = B s a ( , ) = B s a ( , ), + W s a ( , ) N s a ( , ) N s log ( ) N s a ( , ) C 其中 ( , B s a 表示一个调节值，是一个调节常数， ( , ) W s a 是这些次模拟之后到达终止状态的回报值的总和， N s a 是在状态 S 下行为 a 被选择进 ) 行模拟的次数， ( , N s ( ) N s a ( , ) = ∑ ) a 105 是状态 S 被模拟访问的次数的总和。扩展阶段：将边界节点的子节点加入至博弈树的结构之中，扩展的策略主要是逐次扩展 - 3 -

中国科技论文在线 http://www.paper.edu.cn 的策略[12]，该策略并非一次性将全部的子节点添加到树结构之中,而是设置一个窗口值，随着遍历次数的增加，逐渐添加子节点。模拟阶段：使用蒙特卡洛模拟，随机进行游戏直到游戏终点，仅集成了很少的规则，最 110 后返回一次模拟的评估值。更新阶段：沿着选择阶段的路径，逆向地将模拟阶段的评估值，以及访问次数更新到路径上所有的节点上。 2.2 德州扑克的蒙特卡洛树 115 120 125 130 135 由于德州扑克是一种非确定性非完全信息博弈，而传统博弈树是对应于确定性完全信息博弈的，因此我们要根据德州的博弈特点对博弈树进行改造。由于德州扑克在游戏的进行之中会有发牌的事件发生，因此对于游戏之中的发牌状态我们应该将之与其他节点独立出来，我们设定一个随机节点用于对应游戏之中的发牌状态；由于德州扑克中对手有他人不可见的底牌，因此我们要区别出决策节点用于表示程序进行决策的节点，同时要定义一个对手节点表示对手进行决策的节点；另外由于德州扑克的游戏进程比较短，因此在博弈树的扩展过程之中很容易到达游戏的终止状态，因此我们定义叶子节点为博弈树中游戏终止状态的节点。所以我们可以使用决策节点、对手节点、随机节点、叶子节点构造一个德州扑克的蒙特卡洛博弈树。在更新策略上，我们为这两种节点设置了一个向量用来记录参与游戏的所有玩家到达游戏终止状态的期望收益值，而更新的策略则是对于父节点，他的玩家期望收益向量是由其所有的子节点的玩家期望收益向量求取均值获得。而在选择策略上，决策节点使用 UCT 算法选取子节点，其 UCB1 值的计算则是选取玩家期望收益向量之中己方的期望收益值作为利用值部分；对于对手节点来说，由于我们不知清楚他的底牌，那么我们采用一种简化的策略，就是暂时不为这些节点分配底牌，其选择过程也是随机从子节点中进行选择。随机节点，这种节点是指由随机事件发生的节点，在扑克程序中也就是发牌的节点，由于上面我们设定的对手节点的策略，在这里我们同样需要一个简化的策略来对应，只考虑已知发出的牌，即除了决策节点的底牌以及当前状态下发出的牌以外，其他的牌都可以作为随机节点的候选可发牌。其节点的更新策略同决策节点/对手节点相似，都是为节点设置一个玩家期望收益向量，其更新的方式与决策节点/对手节点相同，父节点的评估值由子节点计算均值获得。而由于发牌是一种随机行为，对应的选择策略则是随机去选择子节点。叶子结点，这个节点是游戏进行到了终止状态也就是摊牌阶段形成的节点，由于需要与对手进行比较，在我们不知道对手底牌情况之下，我们可以跟据对手模型为对手分配底牌，当迭代一定次数之后，我们同样可以获得一个玩家期望收益值向量作为上更新的一个基础。而在这种节点上由于以及到达游戏的终止状态，因而不涉及选择的过程。 3 对手模型 140 145 在 1.2 中所涉及的纳什均衡的策略，可以保证在长时间的比赛之中可以不被任何对手击败，然而这种不能充分利用对手的策略同样不能取得一个更好的收益。例如在“石头-剪子- 布”的游戏中，最优的策略便是完全随机的进行决策，这样可以保证任何对手在与这个策略进行游戏时，都无法击败这个策略，同样这个策略也无法击败对手。但是假设对手选择“剪子”作为决策的频率要远远高于其他，如果我们的策略能够充分利用对手的特点，那么以更高的频率做出“石头”的决策将为我们带来更高的收益，这便是对手模型的基本思想。 - 4 -

中国科技论文在线 http://www.paper.edu.cn 150 本文采用一种实时的基于贝叶斯方法的统计对手建模来为程序构造对手模型，在该方案中我们设定一个样本采集窗口，其中保存有前期牌局的游戏信息。结合 Bucketing 的手牌抽取策略[13]，我们可以获得一组概率分布 (A | H,Ph) ，其中表示对手在拥有底牌 H，以及在游戏进行到 Ph 阶段时其决策的分布情况，那么根据贝叶斯定理，我们可以计算出在游戏的某个阶段当对手进行决策时，其底牌的分布情况。同时随着比赛的进行，程序会实时的更新 P 窗口内保存的游戏信息，以达到一个实时更新的目的。这样我们便可以在使用蒙特卡洛树搜索算法的时候将从对手模型之中获取到的对手的信息结合到其中，以便更好的利用对手的特点获取最大化的收益。 4 实验 155 为了测试扑克程序的性能[14]，我们采用 ACPC 协议（也就是年度计算机扑克大赛所使用的比赛用协议）作为程序的对外接口，服务器程序相当于牌桌与发牌者，其自动实现了洗牌、发牌、摊牌判断、筹码分配的功能，连接到服务器上扑克程序相当于玩家，通过协议与服务器交互信息，实现自动化的比赛对局。在测试中，我们选择了如下的程序作为对手：固定策略程序：该程序在比赛过程之中，以 0.1 的概率选择放弃不跟，以 0.9 的概率选择加注与跟注。本程序第一版本：不带有对手模型的版本。测试以 SB/H 作为评估指标，其含义为：每局（Hand）赢得对手多少个小盲注（Small Bland）单位量筹码数。程序以 3000 局游戏作为一个测试单元，分别于上述三个测试程序进行对局，测试的结果如表 1 所示： 160 165 表 1：测试结果固定策略程序无对手模型版本有对手模型版本 - +2.4SB/H +4.6SB/H -2.4SB/H - +0.67SB/H -4.6SB/H -0.67SB/H - 固定策略程序无对手模型版本有对手模型版本 5 结论本文给出了一种结合蒙特卡洛树搜索以及对手模型的算法用以求解非确定性非完全信 170 息博弈问题。通过测试的结果，我们可以发现，基于蒙特卡洛树搜索的程序，在性能上要优与固定策略的程序；而同时基于该方法的程序，结合了对手模型的程序的性能也要高于没有结合对手模型的程序。因此，我们可以确认，结合了对手模型的蒙特卡洛树搜索方法是解决计算机德克萨斯扑克这类非确定性非完全信息博弈问题的一种高效方法。 175 [参考文献] (References) [1] Schaeffer J, Burch N, Björnsson Y, et al. Checkers is solved[J]. science, 2007, 317(5844): 1518-1522. [2] Gelly S, Kocsis L, Schoenauer M, et al. The grand challenge of computer Go: Monte Carlo tree search and extensions[J]. Communications of the ACM, 2012, 55(3): 106-113. [3] Gerritsen G E H. Combining Monte-Carlo Tree Search and Opponent Modelling in Poker[D]. Maastricht: Maastricht University 2010. [4] Billings D, Davidson A, Schaeffer J, et al. The challenge of poker[J]. Artificial Intelligence, 2002, 134(1): 201-240. 180 - 5 -

中国科技论文在线 http://www.paper.edu.cn 185 190 195 200 [5] Morris S, Shin H S. Global games: theory and applications[J]. ECONOMETRIC SOCIETY MONOGRAPHS, 2003, 35: 56-114. [6] Andersson R. Pseudo-Optimal Strategies in No-Limit Poker[J]. ICGA Journal, 2006, 29(3): 143-149. [7] Billings D, Burch N, Davidson A, et al. Approximating game-theoretic optimal strategies for full-scale poker[A].Billings D. IJCAI-03[C]. Acapulco:Morgan Kaufmann 2003: 661-668. [8] Billings D, Davidson A, Schauenberg T, et al. Game-tree search with adaptation in stochastic imperfect-information games[A]. Donkers, H. H. L. M. Computers and Games[C]. Berlin: Springer Berlin Heidelberg, 2006: 21-34. [9] Gelly S, Wang Y. Exploration exploitation in go: UCT for Monte-Carlo go[A]. Twentieth Annual Conference on Neural Information Processing Systems[C]. 2006. [10] Chaslot G M J B, Winands M H M, HERIK H J V A N D E N, et al. Progressive strategies for Monte-Carlo tree search[J]. New Mathematics and Natural Computation, 2008, 4(03): 343-357. [11] Iolis B, Bontempi G. Comparison of selection strategies in monte carlo tree search for computer poker[A]. Proceedings of the Annual Machine Learning Conference of Belgium and The Netherlands[C], BeNeLearn. 2010. [12] 刘知青，李文峰. 现代计算机围棋基础[M]. 北京：北京邮电大学出版社，2011 [13] Sklansky D, Malmuth M. Hold'em Poker: For Advanced Players[M]. Two Plus Two Publishing LLC, 1999. [14] Teófilo L F, Rossetti R, Reis L P, et al. A Simulation System to Support Computer Poker Research[J]. 13th MABS, 2012. - 6 -

分享到：

赞收藏

资料库

论文研究-基于蒙特卡洛树搜索的计算机德州扑克 .pdf

相关推荐

开发技术

热门标签

最新资料