Hanabi游戏的RL探索

前几天突发奇想能否用强化学习算法探索“花火”游戏,一查,发现DeepMind[1]和FAIR[2]都在2019年发表了成果。


花火(Hanabi)是一个非常经典的桌游,规则极其简单,却衍生出千变万化的技巧,获2013德国年度桌游大奖。它是一个2-5人的合作游戏,简单说来就是大家齐心协力完成纸牌接龙。一共50张牌,每张牌有颜色(红黄蓝绿白)和数字(1-5),每人保持4-5张手牌,看不到自己的牌,但能看到所有其他玩家的牌。玩家依次执行:选择给另一个玩家一条线索(clue),或打一张牌,或弃一张牌(并换取线索名额),并补充手牌。打出的牌必须能在公共区域接上某条颜色的龙(从1到5),如果出错三次直接输掉。当新牌被抓完时,游戏结束,此时看公共区域共有多少张牌,最好就是每个颜色接满了1-5,总共25分。通常来说新人能玩到20以上就很好了,高级玩家追求的是满分。clue是这个游戏的关键,因为每条线索只能告诉某个玩家手里的所有某种颜色、或所有某个数字的牌,比如:A对B说,“你的第2、5张是红色”,或者“第1、2张是4”。起始有8个clue名额,之后要靠弃牌换取。在游戏过程中,玩家之间严禁提供clue以外的任何场外信息。


第一次玩这个游戏,纯靠逻辑推理很快能摸到clue的门道。玩了几次后,大家会摸索出一套“约定”,即如何最大程度地提高clue的信息量。最差情况下,玩家通过2个clue(颜色加数字)来确定一张牌,也就是说每个clue的信息量是0.5,但考虑到clue名额稀缺,这样做是极其浪费的。一个clue可以用来指示多张牌,这样多个clue组合就可以增加平均信息量。此外,clue还作为打牌或保护牌的指示,并且在可能的矛盾指示下规定优先级。一个clue除了字面上传递的信息,还有大量隐藏的信息:比如,在玩家B看来,A没有给出效果最好的clue,却选择了明显次一点的,那么这个行为或许暗示了某些自己不知道的信息,比如自己的手牌。注意这是一个不完全信息游戏,每个人能看到除了自己以外的所有手牌,这就意味着游戏中充满了“他不知道我知道他有这张牌”的高阶知识。比如有一个叫finesse的技巧:玩家A跳过B给了C一个打牌clue,但B看到C的牌知道这张牌是接不上的,那么B就能判断,自己必须按约定盲打手里最新的那张牌,这样C的牌才能接上(但C看不到自己的牌,所以他不知道B经历的这些推理)。这样,仅靠一个clue就连续打出了两张牌。还有一种bluff的技巧,就是在B打出后发现这张牌无法被C接上,他被A“骗”了,那这又进入了另一层约定。在[3]这个令人叹为观止的满分游戏复盘里,充斥了各种finesse的变种和嵌套,最终实现了平均每个clue打出了1.5张牌的超高信息量。[4]这个文档罗列了游戏社区总结出来的约定体系,其中基础约定就有23个level之多,而finesse仅仅是第二级。
约定系统是这个游戏最迷人的地方。它必须在清晰、自洽的前提下尽可能地穷尽所有手牌场景,精巧地设计各约定之间的动态结构与优先级,来最大化每一个行为背后传递的信息。它很像桥牌叫牌,是一个可以被人理解的、符合逻辑的编码系统。另一方面,这个游戏又比较年轻,人们通过逻辑和实战总结出约定体系,而无法完全从规则出发严格证明某个约定好于另一个。


这就让人们非常好奇,人工智能能否进化出一个“完美”的约定,秒杀人类玩家?就像AlphaGo横扫人类后成了人类的老师一样,AI能否通过算法而非逻辑推演构造出约定,供人类学习?和围棋不同之处在于:这涉及到多玩家合作(multi-agent)、agent之间信息不对称、随机抽牌导致信息不完全等等问题。另外,这个问题不是Markovian,即玩家不能仅依靠当前牌局决定行动,而要记住所有过往信息(好在游戏回合数量不太多,可以把所有历史记录下来,让问题变成Markovian)。就像围棋一样,人类的决策依靠严格精确的逻辑,而AI依靠大量模式中习得的概率分布。人类棋手师从AI的方式,不是模仿它的概率分布,而是是将它的棋局诠释为某种新的定式。但是,对这个游戏来说,假使它在几乎所有牌局中都达到了满分,人类仔细观察agent在每个牌局中的配合方式,能够诠释出一套人类可以理解的约定系统吗?完全存在这种可能:这套最优约定是纯粹无法解读的编码系统,它只为计算机服务。这就太令人失望了!


在已经发表的两项成果里,Google用了model-free里较为传统的Q-Network,在多人游戏里达到了20分左右的成绩,还算不错;Facebook用了model-based里的蒙特卡洛搜索,但为了不让搜索树爆炸,限定在双人游戏里,达到了24分以上。虽说没有达到秒杀人类的水准,但已经相当不错了。两家都开源了,有兴趣的朋友可以自己训练。

[1]DeepMind发表的成果:https://deepmind.com/research/publications/hanabi-challenge-new-frontier-ai-research
[2]FAIR发表的成果:https://ai.facebook.com/blog/building-ai-that-can-master-complex-cooperative-games-with-hidden-information/
[3]https://www.youtube.com/watch?v=yyrtUm9i6uM
[4]https://hanabi.github.io/docs/learning-path

«
»

    Leave a Reply

    Your email address will not be published. Required fields are marked *