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