（应用数学专业论文）多人非零和不完全信息游戏的研究与实现.pdf

多人非零和不完全信息游戏的研究与实现 专业；成用数学 硕士生：陆一埏 指器教师：冯国灿教授 摘要 游戏阀题蠢着重要的现实意义与科磺意义。一方露，经典漩行的游戏，如象 棋、围棋和挢牌，窍蕾为数众多的爱好者，围绕饕这个游戏有一个嚣家群体靼一 种游戏文化。实现一个足以和人类对抗的智能游戏程廖，对于挑战人类磐力、丰 富游戏文化都蠢极大意义。另一方惑，游戏具有定义良好载趣则帮嚣拣，是现实 生活愤境的抽壤，人类在游戏中魄行为熊l 弋表其炱实抒为模式。因姥，久工铿能、 经济攀、决策理论麓谗多学科考| l 采鼹游戏阙题l 乍为研究对象或任务环蠛。雯终， 游戏庞大的状态空间和些代数属一| 堡也锼它成为计算科学与数学磷突敦实例。 本文主要讨论人工翅能鸳景中的游戏闯题。传统上，人工铿能学科使鼹搜索 算法实现餐能游戏程序，这一方法在嚣人零秘竞全售息游戏上取褥了艇大豹戏 功，一个蓑名的例子是游戏程序“漯蓝”鹫战胜国际象模糕赛怒军。然褥对于多 人、j # 零却或毒不宠全售息游戏的硪突，开展的缀少，霪内更是鲜鸯磺究与余绍。 本文蛇工作主要分为薅瘿分。一磐分综述游戏辩的搜索算法，狳了鼹人零窝宠全 傣息游戏鲍搜索方法之外，也贪缨了多人游戏、极会游戏差瑟不宠全信息游戏救攫 索方法，黪在麓国内读卷分缨人王智能游戏的现鸯方法窝遴震情况。另一部分搽 讨多人菲零弱不完全售患游戏黪特点与实现懿霹题，并将终论鬻予指导一个多入 嚣零秘不宪全傣患豹纸牌游戏撰猪游戏懿实凝中。撰猪驻耱于著名镌“缎心” 游戏，是一摹孛辫蠹非常漉器黪纸薄游戏，其分花色酶抒法商典裂静代表意义。摸 猪翡多入非零粒特点也决定了游戏霸家之溺不秀跫蕈缝竞争酶关系。我销逶进实 现一个久工謦戆撰猪游戏程序，讨论了鲡褥将搜索算法运掰到复杂润题，浚及始 梅在篾有竞争又有合绍置信惠不完全静笺杂环境中进幸亍决策。 本文豹贡献在予：1 ) 介绍诗算搬游簸蠲藤，综述了游戏树援索箨法；2 ) 实 娃 现了一个人工餐能拱猪游戏程序；3 ) 建立了掰涉游戏程序靛一般模型；4 ) 撼 出了实现多人非零和不完仝信息游戏程序的一般方法，包括一个颇有新意的算法 改迸。实验结采显示我们的拱猪游戏程序已经达蓟了一般人类玩家的水平，出辟 灵活蹩、合理性方嚣远远越过了现存的巍业软l 孛。这涯实了文中撼出故模型稠方 法的有效性。另外，实验结果与实际游戏中的某些现象十分吻合，我们从中总结 出一些有趣的结论。 关键词：游戏，游戏槲搜索，多人，非零和，不完垒信息，拱猪 t l i r e s e a r c ha n dr e a iiz a t i o no n m u i t i p i a y e r n o n z e r o s u mg a m e swit him p e r f e c tin f o r m a tlo n m a j o r ：a p p ii e dm a t h e m a t i o s n a m e ：l uy i t i n g s u p e r v i $ o r ：f e n gg u o o a n a b s t r a c t g a m ei sa ni m p o r t a n ts u b j e c tb o t hl nr e c r e a t i o na n dr e s e a r c h o n eh a n d ，ac l a s s i c g a m e ，l i k ec h e s s ，b r i d g eo rg oh a v es om a n yf a n st h a ti th a sa c t u a l l yf o s t e r e dak i n d o fg a m ec u l t u r e t or e a l i z ea ni n t e l l i g e n tc o m p u t e rg a m ep r o g r a mw h i c hc a nb ea m a t c ho fh u m a nh a ss i g n i f i c a n c ei nc o l o r i n gt h a tc u l t u r e t h eo t h e rh a n d ，g a m e sw i t h w e l l d e f i n e dr u l e sa n dg o a l si sa ng o o da b s t r a c t i o no fr e a ll i f es i t u a t i o n s ；h u m a ng a m e p l a ys o m ew h a tr e v e a l e dt h er e a lb e h a v i o rp a t t e r n so fh u m a n t h a t sw h ym a n y d i s c i p l i n e s ，e s p e c i a l l ya i ，e c o n o m i c sa n do p e r a t i o n a lr e s e a r c h ，c h o o s eg a m e sa ss t u d y c a s eo rt a s ke n v i r o n m e n t a n da l s oc o m p u t a t i o n a ls c i e n c ea n dm a t h e m a t i c ss t u d y g a m ep r o b l e m sb e c a u s eo ft h ec o m p u t a t i o n a lc o m p l e x i t ya n da l g e b r a i cp r o p e r t i e so f g a m e s t h i sp a p e rh a n d l e sg a m ep r o b l e m si na i sa p p r o a c h t r a d i t i o n a l l y ，a iu s eb r u t e f o r c e s e a r c ha n dh e a u r i s t i ct of o r mi n t e l l i g e n tg a m ep r o g r a mw h i c hh a sa l r e a d ya c h i e v e d g r e a ts u c c e s si nt w o p l a y e rz e r o s u mg a m e sw i t hp e r f e c ti n f o r m a t i o n am o s tn o t e d c i t a t i o ni st h a t ”d e e pb l u e ”b e a th u m a nw e r l dc h e s sc h a m p i o ni n1 9 9 8 i nd o m a i no f g a m e so fm u l t i p l a y e r n o n z e r o s u mo ri m p e r f e c ti n f o r m a t i o nt h e r ea r em u c hi e s s r e s e a r c h e sh a v i n gb e e nd o n e e v e ni e s s e ri nc 。h i n e s e t h i sp a p e rh a v ed o n ew e r k m a i n l yo nt w op a r t s ：1 as u r v e yo ng a m et r e es e a r c ha l g o r i t h m sb e a r i n gi nm i n d i n t r o d u c i n ga ig a m em e t h o d sa n dp r o g r e s st od o m e s t i cr e a d e r s b e s i d e ss e a r c h m e t h o d so nt w o p l a y e rz e r o s u mg a m e sw i t hp e r f e c ti n f o r m a t i o n w ea l s oi n t r o d u c e t h ec o u n t e r o a r t so nm u l t i p l a y e r c h a n c eo ri m p e r f e c ti n f o r m a t i o ng a m e s 2 a d i s c u s s i o no nm u l t i p l a y e rn o n z e r o s u mg a m e sw i t hi m p e r f e c ti n f o r m a t i o ni n c l u d i n g i t sa t t r i b u t e sa n dp a r t i c u l a r i t i e sa n dc o n s i d e r a t i o n so nr e a l i z a t i o n w et h e nu s et h e s e c o n c l u s i o n st og u i d eo u rr e a l i z a t i o no fap o p u l a rc a r dg a m e ，g o n g z h u g o n g z h ui s d e r i v e df r o mh e a r t sa n dv e r yp o p u l a rt h r o u g h o u tt h ec o u n t r y i ti sp l a y e db yc o l o r w h i c hi sat y p i c a lr e p r e s e n t a t i v eo fo d ec l a s so fc a r dg a m e i ng a m et h ep l a y e r s c o m p e t ee a c ho t h e rn o tb yd u t yb u tb yb e n e f i t 、ea n a l y s ea n dd e m o s t r a t eh o wt o a p p l ys e a r c hm e t h o d si nc o m p l e xp r o b l e m sa n dh o wc o m p u t e rm a k e sd e c i s i o n si na c o m p l e xe n v i r o n m e n ts u c ha sw i t hc o m p e t i t i o n ，c o o p e r a t i o na n dh i d d e ni n f o r m a t i o n a 1 1t h r o u g ht h ei m p l e m e n t a t i o no ft h eg a m e o u rc o n t r i b u t i o n si n t h i sp a p e ri n c l u d i n g ：1 ) a ni n t r o d u c t i o no fc o m p u t e rg a m e p r o b l e ma n da ns u r v e yo fg a m et r e es e a r c ha l g o r i t h m s ；2 ) a nc o m p l e t ea ig o n g z h u g a m ea p p l i c a t i o n ；3 ) ag e n e r a lp r o g r a mm o d e lf o rr e l a t i v eg a m e ；4 ) g e n e r a li d e a so n r e a l i z a t i o no f m u l t i p l a y e rn o n z e r o s u mg a m e sw i t hi m p e r f e c ti n f o r m a t i o n i n c l u d i n g an o v e li d e nt oi m p r o v ea l g o r i t h mp e r f o r m a n c e e x p e r i m e n tr e s u l ts h o w st h a to u r g o n g z h up r a g r a mp l a y saj u n i o rh u m a np l a y e rl e v e la n dc a no u t p e r f o r ma v a i l a b l e c o m m e r c i a lp r o g r a m si nf l e x i b i l i t ya n dm t i o n a l i t y 。w h i c hv a l i d a t e st h ei d e a si nt h i s p a p e r a d d i t i o n a l l y ，e x p e r i m e n td a t am a t c hs o m ef a m i l i a rp h e n o m e n ai nh u m a ng a m e p l a y ，f r o mw h i c hw ed e r i v e ds o m ei n t e r e s t i n gc o n c l u s i o n s k e yw o r d s ：( 1 a m e ，g a m et r e es e a r c h ，m i t i - p t a y e r ，i m p e r f e c ti n f o r m a t i o n ，a o n g z h u 中山大学硕士学位论文 第一章引言帚一早j i 五 1 1计算机游戏问题介绍 本文所讨论的计算机游戏指的是参与棋类、牌类等博弈游戏的计算机程序， 不包括当前各种以视频为表现形式的广义计算机游戏。关于计算机游戏的研究已 有很长的历史 4 6 】，早在1 9 5 0 年，c l a u d es h a n n o n 就已发表了他关于计算机国际 象棋的一篇颇具开创意义的论文，此时距世界上第一台电子计算机e n i a c 问世 ( 1 9 4 6 ) 不过四、五年的时间，有远见的人们已经预见到了计算机在游戏中的广 阔应用前景。s h a n n o n 、s a m u e l 、t u r i n g 、n e w e l l 、s i m o n 等人都在这个领域进行 了一些早期的工作。他们的工作吸引了众多研究者加入这一领域，从而使计算机 游戏研究成为人工智能的重要研究领域之一。 虽然计算机游戏研究的最初目标是编写一个高水平的计算机国际象棋程序， 但研究范围很快就扩展到了几乎所有流行的游戏上，如c h e c k e r s ( 西洋跳棋) 、 o t h e l l o 、g o ( 围棋) 、b r i d g e ( 桥牌) 、c h i n e s e c h e s s ( 中国象棋) 、s h o g i ( 日 本象棋) 、b a c k g a m m o n ( 西洋双陆棋) 、p o k e r 等。这些游戏可以从不同方面 进行分类。按玩家数可以分为单人游戏、2 人游戏和多人游戏。按游戏信息是否 完全可见可分为完全信息的( p e r f e c ti n f o r m a t i o n ) 和不完全信息的( i m p e r f e c t i n f o r m a t i o n ) ，例如象棋是完全信息的，而桥牌是非完全信息的。按游戏的计分 规则可分为零和的( z e r o s u m ) 和非零和的，零和指的是如果将游戏结果中的奖 励视为正、惩罚视为负，那么对参与游戏各玩家的奖惩之和为零。以国际象棋为 例，游戏结果只有三种：胜、负、和，令l 代表胜、一1 代表负、0 代表和，则双 方结果总是零和的。另外，有的游戏还包括机会( c h a n c e ) ，例如借助色子决定 下一轮行动值的游戏。被讨论最多的一类游戏是两人零和完全信息游戏 ( t w o p l a y e rz e r o s u mg a m e sw i t hp e r f e c ti n f o r m a t i o n ) ，国际象棋、围棋都属于这 一类游戏。 另外还有些性质用于衡量游戏的特性。收敛性：如果随着游戏的进行，游戏 状态空间趋近于零，则称游戏具有收敛性。例如国际象棋和桥牌是收敛的，因为 随着棋盘上棋子的减少或玩家手中牌的减少，游戏的状态空间是趋近于零的。状 中山大学硕士学位论文 态空间复杂度和游戏树复杂度：状态空间是从游戏初始状态可以达到的所有状态 的集合，游戏树是记录从初始状态通过合法行动到达最终状态的所有路径的树状 结构。可以根据游戏的状态空间复杂度和游戏树复杂度特性对游戏进行分类。 2 3 1 详细讨论了游戏的收敛性、状态空间复杂度和游戏树复杂度对解决游戏问题的影 响。 实际的游戏问题往往有着庞大的状态空间和游戏树复杂度，这使它们往往成 为新搜索算法的温床和试验平台。现在大多数标准的搜索方法都是在游戏背景中 开发出来的。此外游戏通常具有定义良好的规则和目标，作为真实世界情景的某 种简化和抽象，游戏问题也常常成为人工智能、运筹学等学科的研究对象。简化 的游戏问题还被用于数学、经济学等学科的理论研究。 1 2计算机游戏研究的现状 9 0 年代起，计算机游戏程序取得了一系列显著的成功。1 9 9 4 年c h i n o o k 程序在c h e c k e r s 游戏上取得了计算机程序的第一个世界冠军称号。紧接着1 9 9 7 年，d e e pb l u e 战胜世界头号国际象棋大师盖里卡斯帕罗夫，实现了计算机 游戏研究的最初目标一一一个世界冠军水平的国际象棋程序。同年 l o g i s t e l l o 也以绝对性优势战胜了o t h e l l o 世界冠军。表1 1 是1 9 9 0 年对2 0 0 0 年计算机奥林匹克项目的游戏程序的一个水平预测。在这张表中，除了a w a r i 游戏的解决尚待时日之外其他预测都是相当准确的。 表1 11 9 9 0 年对2 0 0 0 年游戏奥林匹克项目的水平预测( 见【2 3 】参考文献) 已解决 高于世界冠军水平 世界冠军水平 大师水平 业余水平 c o n n e c t - f o u rc h e c k e n ( 8 x 8 )c h e s ； g 0 ( 9 x 9 】 g o ( 1 9 x 1 9 ) q u b i cr e n j ud r a u g h b ( 1 0 x 1 0 )c h i n e s ec h e s n i n em e n sm o r r i ； 0 t h e ob r i d g e 6 0 m o k us c r a b b l e a w a r i b a c k g a m m o n 2 】给出了游戏解决的三种定义：1 ) u l t r a - w e a k l ys o l v e d ，从游戏初始位置得 到游戏理论值：2 ) w e a k l ys o l v e d ，确定了从初始位置获取游戏理论值的行动策 略：3 ) s t r o n g l ys o l v e d ，确定了从任意合法位置获取游戏理论值的行动策略。对 中山大学硕士学位论文 于状态空间过于复杂的游戏，得到游戏理论值几乎不可能。但通过一个评估函数 对末到达最终状态的游戏进行局面评估，可以得到与游戏结果近似一致的评估 值，利用这个评估值就可以制定出理性的策略。很多高水平游戏都使用了局面评 估。在所有游戏中，围棋由于其庞大的搜索空间和困难的局面评估，成为继国际 象棋之后计算机游戏研究的下一个挑战。表1 2 是当前对2 0 1 0 年的一个预测， 反映了这些游戏当前的研究进展和前景。 表1 22 0 0 0 年对2 0 1 0 年游戏奥林匹克项目的水平预测( 【2 3 1 ) 已解决高于世界冠军水平世界冠军水平大师水平业余水平 a w a f ic h e s sg o ( 9 x 9 ) br i d g e g o ( 1 9 x 1 9 ) o t h e i | od r a u g h t s ( 1 0 x1 0 )c h i n e s ec h e s ；$ h o g i c h e c k e r s ( 8 8 )$ c r a b b i e h e b a c k g a m m o n a m a z o i l l i n e so f a c t i o n 1 3计算机游戏程序的实现 游戏程序的核心是一个高效的树搜索算法。如图l 所示。理想情况下，该搜 索算法搜索从游戏当前位置( 初始状态) 到游戏结局的每一种可能的合法行动序 列( 即图中的一条路径) ，并根据游戏结果判定行动序列的优劣程度，选取最优 的行动序列( 图中粗线表示的路径) ，得到当前位置的行动策略。但在实际情况 中，搜索算法不会搜索每一个完整的可能的行动序列。一个原因是，通常搜索算 法只需搜索部分可能路径便能得到正确的最优结果和策略。另一个原因是，由于 复杂性问题和资源( 时间、空间等) 限制，搜索算法常常只能搜索到一定深度便 停止搜索。此时，通过一个评估函数为搜索中止处的节点赋上评估值，这个评估 值应该与游戏结果近似一致，从而通过该评估值可以判断路径的优劣。有研究表 明，在许多游戏中，搜索深度与游戏程序的水平有非常紧密的关系。因此，如何 设计一种高效的搜索算法，它搜索尽量少的路径、获取尽量大的搜索深度和尽量 准确的评估函数，是开发一个高水平的游戏程序的关键。游戏相关的知识在高水 平的游戏程序中也起着致关重要的作用。使用知识可以减少搜索所需的资源( 转 移表) 、消除搜索的机械性( 选择算法) ，但它最重要的用途就是用来建立一个准 确恰当的评估函数。评估函数反映了计算机程序对游戏局面的判断，极大程度决 4 中山大学硕士学位论文 定着程序所作决策的质爨。除了搜索和知识的方法之外，分解和仿真也是很肖潜 力蘸逶嗣穷法，螽瑟会麓擎务绍这瓣秘方法兹惑想。 一种可 中问状 此处评估 搜索深度 ，。，、，_ ， 磊黎娶慧的：。曼 ! z j9 i | 粤 _ - 2i 紫装篓寨 图1 i ：游戏攫索示意圈。树形结擒代表当前玩家眼中豹游戏。方框伐袭游戏状态节点。为 了简单起抛，没有区分不间玩家的节点类型。方框中的德为节点的值，叶子节点的假为游 戏结果贼予当前玩家的值，内部节点的值由其孩子节点的值决定。图中，如果可以到达的 话，值为9 的时子节点是擞翁嚣家最优的游戏结果。如粜橱始状态为游戏的开始位置，则9 帮是游戏瓣璞论毽。覆绒衮示豹是通往溅缆结莱懿路径，这条爨径土麴节点其毒稳嗣瓣篷， 它给 j 了嬲前玩家应采取的策略。 1 3 搜索的方法 在两人完全信息游戏中使用最多的也是最成熟的搜索算法是a l p h a - b e t a 算 法，即m i n i m a x 算法加上a l p h a - b e t a 剪枝( p r u n i n g ) 。m i n i m a x 算法决定了一个 节点扶窀愆孩子节点懿壤褥到叁身戆蓬数方法。褒m i n i m a x 辫法匏搜索过程中， 许多分枝对于搜索结粜没有任何影响，因而可以被安全的忽略掉，这种未被访问 到的节点和路径叫做被剪枝了。a l p h a - b e t a 剪枝摄一种简单高效的剪枝算法，它 藐寿效薅将m i n i m a x 冀法靛复杂旋( 蠲谤润繁点数寒蘩羹 麸o ( b 4 洚低到 o ( b “2 ) ，其中b 代表平均分枝因予，d 代表树的深度。人们使用和研究a l p h a b e t a 算法已爨4 0 多年的掰史，对该算法提窭了许多肖效的改进，现在它的表现已经 接近它的理论最佳值。a l p h a b e t a 簿法静剪技效率很大程凄取决于节点的瓣序， 串出夫学壤士学位论文 因此一般游戏程序都会在嫩行a l p h a b e t a 搜索前对树节点进行排序，一种常见的 情况是先使用转移表( t r a n s p l a n tt a b l e ) 的信息，再使照杀手癌发( k i l l e rh e u r i s t i c ) ， 簸后使用压虫启发( h i s t o r yh e u r i s t i c ) 【t 1 。 a l p h a b e t a 算法是- 3 * 深度优先的算法，当树深度过大时，通常使用迭代加 潆( i t e r a t i v e l yd e e p e n i n g ) 来保证搜索程媲定时闻内究成。迭代加深以逐渐增大 的搜索深度薰簸进行a l p h a b e t a 搜索过强，直至完成缓索或雳完鲶定静时闻，遨 同最大深度的完整搜索的绥果。相邻两次搜索的深度箍通常为一个常数，它取决 予游戏的分技因子，国际裂棋中通常取l 。迭代鸯瑶深豹优点在于熊够在时闯有限 的条件下给溅适当的结暴，并且中阍一艨的搜索过程可以利蠲上一朕援索褥蓟的 信息，提高搜索效率。由于树的节点数目随深度呈指数增长，相对于最深一层的 搜索瑟言，静麟进毒亍麓浅鼷次搜索所需麴开销是缀小豹。 a l p h a b e t a 算法以固寇顺序( 深度优先、觚左到右) 访闻节赢，这使它具督 很好的完备性，即不会锚潋任何通向最优结果的节点。但在资源有限的条件下， 窍对我翻零黧瞧终更多的计算资源花在爨有幕望通谯绶优结果豹路径上，这就嚣 袋一种有选择的搜索顺序。有许多与a l p h a b e t a 想法不同的援索舞法，如嚣+ 、 s s s 。、m t d ( f ) 、b e s t f i r s t 、c o n s p i r a c y n u m b e r 、p r o o f - n u m b e r 等。其中一些是搬 蠢希望兹掰算法，著虽已经在菜些游戏中取褥了不错熬结果，但对这些摆对较赣 的算法，要取得与对a l p h a b e t a 算法襁似的深亥理解，还需要时间酌积累与沉淀， 与两人零和完全信息游戏相比，多人游戏、包含机会的游戏和信息不完全的 游戏开展褥较少。这三耱炎墼懿游戏郝黉要对游戏撼的结擒箨一然敬变，搜索算 法大多是m i n i m a x 算法的岚接扩展，像多入游戏中的m a x “算法、机会游戏中的 e x p e c t i m i n i m a x 算法和不宠全信息游戏中的i m p m i n i m a x 算法，而搜索算法对 应豹蒡棱雾漩基本土篷蹩嶷蔫了a l p h a ，b e t a 剪较中浚鬟援索浸兹悉戆。纛要攒趱 的是，这些搜索算法在实际游戏问题中由于受到问鼷本质的局限。现阶段还没柯 敬得类似于a l p h a b e t a 算法在两人零和完全信息游戏中取得的成功，值得进一步 磺究豹连方裙穰多。 1 3 2 知谀的方法 考虑露餐获缮一个节点瓣篷懿阕题，正常祷嚣下这需要递整援索该节点豹躜 6 中出大学磺士学垃论文 有嚣继，几耪利用游戏戋鞋识匏方法可戬游滁或减少这耪嚣簧。 游溅的状态集实际是一个图的结构，然而却是按照树来搜索，因此树中会脊 许多不同的节点代寝相同的状态。举例来说，同样一盘中尚，可以以很多不同蠢 法缮到。重复熬状态节点在搜索深度槎阉对其套捃羁瓣僮，因照菇繁一次搜索瓣 将搜索结果保留下来等到下一次遇到相同状态的节点时岚接取前一次搜索的 值，而无需重复搜索。起这样一个作用的结构叫转移裘( t r a n s p o s i t i o n t a b l e ，1 t ) ， 逶豢瘸啥番表寒实瑗。转移表繇孬节点状态、搜索深度、搜素结栗篷窝该状态下 的最佳策略。当要获得一个节点的值时，先查看该节点是否位于转移表中，如果 是，且保存节点的搜索深魔大于簿于本次搜索的深度，直接取用保存节点的节点 妻擞兔该节点躲篷；懿粟保存节患懿援索深度小于本次援索深度，也霹黻剩露保 存节点的最俄策略排列本次搜索的节点顺序。如果该节点不在转移表中，对其进 行搜索，并将搜索结果添加到转移表中。转移袭消除搜索重复状态的需簧，所起 懿终髯稳当予将楗援索转纯为爨疆素。游戏送行过程串，转移表| | 芟集游戏壤惑并 重复利用，甚至可以将转移表收集的信息存储于硬盘上，以供多次游戏使用。男 一种类似的方法使辩j 残局数据库( e n d g a m ed a t a b a s e s ) ，将有限的残局游戏状态 存德予一令数据痒中，嗣辩存敦在该残蜀清 冤下瓣游戏结巢秘聚德行纛策略。囊 游戏进行到( 或搜索到) 浆个状态与库中保存的残局相同时，无需进一步的搜索 就能躐接得别结果。残局数据库的好处是一次构建永远都能使用。另外也可以利 蠲入稻怠结瓣经验疑谖，妇模谱、开爨手瑟、统计数据等，在特定场合取代袋萼| 导搜索过程。 当没有以上知识可用时，需要搜索该节点至一定深度( 迭代加深) ，并在搜索 箨壹静篷方馒霜译健丞数e v a l ( s ) 给塞终漆节点静评傣值，冀中s 弋衰游戏狡态。 评估函数用于对游戏局面进行评价，给如能准确预示游戏结果的谨估值。建立一 个好的评估函数需要用到游戏自身的知识。通常，可以从不同特征( f e a t u r e ) 评 价游戏局面，分剐记为z ，2 ，五，然磊使用线性加权静方法获褥整体谱侨，酃 e v a l ( s ) = 毪点o ) ，其中嗨为孝擎经五瓣浮伶傻在整体评价中瑟占浆毙蘩。恻鳃 i 褒象擞中，一个特缎可取梵剩余的子力，一个特征霹取鸯予瓣分枣。特，鹱蕊投覆 通常由经验和手工调整得列，这是一项很耗时耗力的工作。可以使用强化学习的 方法囱动化这一过程，现在畿常用的一种学习方法是辩变羲分( t e m p o r a l 中山大学硕士学位论文 d i f f e r e n c el e a r n i n g ，t d l ) 的学习方法。 1 3 3 其他方法 如累以上方法已将搜索性能发攘到极致，那么再想显著地提高搜索速度，可 戳采曩l 耱行计算静方法 h l 。当援索空闻过于旋大，懿霞摸审豹请况，鼙缝静全 局搜索难以奏效，可以采用局部搜索的方法 3 6 】。局部搜索的方法将原游戏分解 为几个独立的子游戏，井分别对各予游戏进行局部搜索，由备予游戏的搜索结果 综合褥劐漾游戏的绪祭。不完全绩怒麓游戏中毯含鸯未翔绩怠，如果穆这穆来翔 信息体现在游戏搜索树中，即游戏树中包含每一种可能的情形，则将很快膨胀游 戏树的大小，导致搜索无法有效进行。这时可采用仿真的方滋。假定一种寒知信 怠静可麓情形( 这i q 锻原秘蘧静一个采棒，或不完全信患游戏斡实铡纯) ，将不 完全信息搜索转化为究全信息搜索，对这种情形进行搜索得到该样本下的结果。 重复该j 违程，直到得剿绘定数量的样本下的结果，将这些样本的结果进行练舍得 虱不完全信息条件下蠲望韵最佳结聚。嚣蔚最好的挢薅程序g i b 2 0 就楚莱溺这 种方法她理不完全信息问题。它根据叫牌信息和出牌过程模拟一定数量的牌的完 整分布，瞧知道牌的究攘分布的条件下搜索游戏褥剽该分布下驰结果，再以该分 布情形的出现概率帮缡暴豹好坏为粳重，综合器释分布魏清凝褥弱出簿策旗。如 果样本选取得，仿真的方法可以使用少数样本模拟整个可能状态空间，增加单个 样本的搜索深度，提离游戏程序的表现。 1 4本文选题 本文萎贯究多入零帮不竞全信惠游戏戆理论与实现。雀计算瓿游戏豹疆宠瑟 史上，两人零和完全信息的游戏被研究得很多，而多人、非零和、不完全情息的 情况受到的关注相比之下非常少，特别，如何实现一个实际的同时具备多人非零 帮不完全信惑特瞧鹃复杂游戏跫一个蓬搔探讨瓣阀题。本文觚这个怒法入手，希 望通过实现一个纸牌游戏程序，向人们介绍计算机进行游戏的一般方法，并对此 问题的硪究做一个当前的总结，探讨在两人零和究全信息游戏中十分有效的搜索 戆方法农多久菲零帮不完全信意游戏中应鬻翡麓能往帮弱戳瞧。善宠，实现一拿 流行的游戏本身即具商其现实意义；其次，通过解决实现过程中面l 临的实际问题， 8 中山大学硕士学位论文 找到适合予某一类问题的方法，也具有相当价值。 迭霉揆猪游戏佟为我翻静骚炎辩象主要塞予叛下琢函：1 ) 揆猪是一种典鍪 的多人非零和不完全信息游戏，十分符合我们的要求；2 ) 拱猪是一种国内非常 流行的纸牌游戏，其打法有典型的代表意义；3 ) 拱猪的多人非零和特点决怒了 游戏玩家之闯莛蘸竞争又台 辛的关系，如褥在篾巍争又合律瓣繇境中透行决策， 也是一个比较新颖的问题。 本文欲实现的目标如下：1 ) 综述计算枫游戏搜索算法；2 ) 建立所涉游戏程 亭静一觳模鼙；3 ) 实魏一个天工管能揆猪游戏稷j 葶：4 ) 提磁实现多大箨零稻 不完全信息游戏程序的一般方法。 5本文缓织 本章简要介绍了游戏问题的背镣和现状，以及实现一个人工智能游戏程序的 大薅愚露，第二章霸第三章疆援索兔主线综述了黻经懿穗关工露。萁中，第二章 介绍两入零和完全信息游戏的搜索方法，重点讲述m i n i m a x 搜索算法和 a l p h a b e t a 剪枝算法，以及一些提高搜索效率的增强方法，除此之外也介绍了其 建有代表羧豹攫索冀法。第三章将游戏耱懿援索方法扩震弱多人、菲零窝、不完 全信息的情况下，分别介绍了这三种情况下的研究工作，每一种情况都给出了问 题的定义和代表算法。第四章分析实现多人非零和不完全信息游戏需要面临的问 题，并将游戏橇赘援索冀法应曩到一个实镶羧猿游戏孛，突瑷了一个竞整豹 拱猪游戏稷序。第五章鼹我们的实验结果、结论和对未来工作的一些设想。另外， 附录a 列出了程序的源文件清单，附录b 展示了程序的主界颥和程序运行时的 舞麓。 中山大学硕士学位论文 第二章游戏树搜索 一个智能游戏程序应该和它的人类对手一样，能够正确地判断，理性地决策， 使其在游戏这样一个竞争的环境中获得有利的地位。当然，由于计算机的构造和 运行方式，其决策过程也与人类大不相同。关于计算机在游戏中的表现， 2 0 1 有 如下论述，“只有当蛮力搜索能够掩盖其天生的愚钝，计算机才能成为像样的游 戏玩家”。这一点在已实现的游戏程序中表现得十分明显。大凡状态空间少，游 戏树深度浅、分支因子小的游戏，计算机都能表现很好，有些游戏计算机能够完 全解决，有些计算机能表现出与人类相当甚至超过人类的水平。但是对于状态空 间过大，搜索复杂度过高，大大超出现有硬件计算条件的游戏，计算机就表现得 无能为力，例如分支因子十分巨大的围棋，现有最好的程序只相当于缺乏正规训 练的人类的水平。多数游戏程序的核心是一个搜索算法，程序水平很大程度取决 于搜索算法的搜索效率一次决策( 固定时间长度) 搜索的状态节点数和深度， 因此游戏研究很大的努力花在开发新的高效算法和提高现有算法效率上。在所有 有影响力的游戏搜索算法中，m i n i m a x 算法和a l p h a b e t a 剪枝( 后面称两者的结 合为a l p h a b e t a 剪枝算法或直接称为a l p h a b e t a ) 的研究历史最长，因此是最成熟 最完善，也是最广为使用的算法，它们分别在2 1 节、2 2 节中介绍。2 3 节讨论 将a l p h a - b e t a 算法应用到游戏中的实际问题。有许多a l p h a - b e t a 的增强方法，能 大大提高a l p h a b e t a 剪枝的效率和相同搜索资源条件下( 时间、空间) 算法的搜 索能力，2 4 节介绍了这些增强方法。对a l p h a b e t a 算法的深入研究和对新算法 的探索得到了其他一些算法，这些算法与a l p h a b e t a 在某些方面思想不同，在特 定场合的表现有时优于a l p h a b e t a ，有些是很有希望的新算法，值得进一步的研 究，2 5 节介绍了其中一些具有代表性的算法的思想。最后，2 6 节是一个小结。 2 1游戏树的m i n i m a x 搜索算法 如图2 1 所示的简化桥牌游戏。两个玩家( m a x 和m i n ) 各持2 张牌，初 始状态下由m a x 首先出牌，图下方的向量标明了游戏结果中两家分别所得的墩 数，注意到只需将游戏结果向量做一个平移，两家的结果之和就等于0 ，因此这 0 中山大学硕士学位论文 是一个零和的游戏。考虑初始状态下m a x 的出牌。如果m a x 按右侧的出牌线 路出方块j ，他有机会得到全部两墩牌( 第三种结局) ，但更有可能的是遭到m i n 的反击( 先用方块a 吃掉方块j ，继而再打一张方块，全取两墩) ，一墩也得不 到( 第四种结局) 。但是如果m a x 首先出黑桃1 0 ，他至少能得到一墩。当然， 如果m 矾是一个理陛的玩家，他会选择垫掉方块5 ，并借助方块a 取得最后一 墩( 第一种结局) 。为了有效防御m i n 的反击，m a x 应该选择先出黑桃1 0 。 m i n i m a x 算法就是基于这样一个思路，它假设对于玩家的每一种行动，对手 总能找到相应的最优行动进行回击，那么玩家选择的行动就应该是使对手的最优 回应行动造成的结果对己方最有利的一种，这样一种选择行动的策略被称为最佳 防御策略，它总假设对手是不犯错误的最优选手。当然这个假设不一定完全成立， 如果对手不是总能找到最优策略，对于人类玩家，这是很有可能的，则可以利用 对手的失误取得对自己更为有利的结果。但是，“蠢笨”的计算机在面临“聪明” 的人类的竞争时，这样一种小心谨慎的态度是十分明智的。下面规范化地提出游 戏树的m i n i m a x 搜索算法。 定义2 1 一个整数赋值游戏是一个四元组( g ，p ，5 ，e v ) ，其中g 是游戏合法 状态的有限集，p ，g 为游戏初始状态，s ：g _ 2 6 是后继函数，它给出一个给 定状态的所有直接后继，e v ：g - f m a x ，m i n u z 是评价函数，它将游戏状态映射 到一种类型的节点或一个标量值。 p j ( p ) 表示状态p 可由状态p 经过一次合法行动到达。通常游戏需要满足 以下两个要求：( 1 ) 没有一个n 0 的状态序列p o ，p 。，其中对每个f 0 有 p f s ( p f - 1 ) ，且p o = p 。a 即不存在循环的状态。( 2 ) e v ( p ) z 当且仅当s ( p ) = 审。 即仅当游戏结束时( 叶子节点) ，e v 为游戏结局赋予一个整数值。将目的是使游 戏结局值最大的玩家称为m a x i m i z e r ，而使游戏结局值最小的玩家称为 m i n i m i z e r 。而当游戏进行中( 内部节点) ，e v ( p ) = m a x 代表轮到m a x i m i z e r 行动， 这样的节点p 称为m a x 节点，而e v ( p ) = m i n 代表是m i n i m i z e r 的行动轮次，p 称 为m i n 节点。 中山大学硕士学位论文 a 出牌 ( 1 1 )( 2 ，0 ) ( 2 ，0 )( 0 2 ) 图2 1 一个游戏的例子 定义2 2 给定整数赋值游戏( g ，p , j ，e v ) ，递归地定义函数e v 。：g z 如下： e v 。( p ) = e v ( p ) m a x p e ，( p ) e v 。( p ) m i n p e ，( p ) e v 。( p ) e v ( p 1 z e v ( p ) = m a x e v ( p ) = m i n 则( g ，p ，j ，e v ) 的值即游戏值定义为e v 。( p ，) ，任意节点p 的值定义为e v 。( p ) 。 由定义2 2 可知，m a x 节点的值等于所有后继节点值的最大值，而m i n 节点 的值等于所有后继节点值的最小值，这反映了m a x 尽量使游戏结局值最大，而 m i n 尽量使游戏结局值最小的企图。这样m a x 节点的值实际上就是所有最小值 ( m i n ) 中的最大值( m a x ) ，这样一个过程得到m i n i m a x 算法如下： 算法2 3 ( m i n i m a x ) 给定整数赋值游戏( g ，p ，j ，e v ) 和状态p g ，计算 中山大学硕士学位论文 i fe v ( p ) zr e t u r ne v ( p 、 e l s ei fe v ( p ) 2