1
| 本文作者：田渊栋 | 2017-02-07 09:58 |
雷锋网按：本文作者田渊栋，卡耐基梅隆大学机器人系博士学位、上海交通大学硕士学位和学士学位，前谷歌无人车项目组成员，现任Facebook人工智能组研究员，主要负责Facebook的智能围棋项目Dark Forest。文章转载自知乎专栏，雷锋网已获授权。
最近听说我的母校卡耐基梅隆大学德州扑克的AI Libratus以很大的优势赢得了与职业玩家的比赛，非常兴奋。在同时期，还有一篇来自加拿大阿尔伯塔大学（Univ of Alberta）的文章介绍了DeepStack，同样在3000局的比赛中击败了几位职业玩家。这样在非对称信息游戏上人类再一次输给了AI。
当然有AlphaGo的先例，这个对广大吃瓜群众的冲击可能没有那么大。但我个人觉得非对称信息博弈的实用价值更大些。因为非对称信息博弈的应用范围非常广泛，涵括我们每天遇到的所有决策，上至国家战略，下至日常琐事，全都可以以同样的方法建模。
非对称信息博弈难在哪里？
一方面是因为对于同样的客观状态，各个玩家看到的信息不同，因此增加了每个玩家状态空间的数目和决策的难度；
另一方面即使在同样的状态数下，解非对称信息游戏所需要的内存也要比解对称信息要多得多，这个主要是对于对称信息博弈来说，只要记得当前局面并且向下推演找到比较好的策略就可以了；但对非对称信息博弈，只记得当前（不完整的）局面是不够的，即使盘面上的情况相同，但对手之前的各种招法会导致事实上局面不同，只有把它们全都罗列出来进行分析，才能保证想出的应对策略不被别人利用。
比如说玩石头剪刀布，在看不到别人出招的时候轮到自己出招，如果别人一直用石头剪刀布各1/3的混合策略，那自己就会发现好像怎么出招收益都是0，于是每次都出石头，但是这样的话，对手就可以利用这个策略的弱点提高自己的收益。所以一个好的算法就要求，基于别人已有策略得到的新策略尽可能地少被别人利用(low exploitability)。
这次的游戏是Head-up unlimited Texas Hold'em，直译过来是两人无限注德州扑克。所谓两人就是一对一的零和游戏，不是多人游戏。所谓无限注，就是在加筹码的时候可以任意加（比如著名的把全部筹码都押上的All in），而限注（limited），是指在加筹码的时候只能加一个固定的数字（通常是前两轮和大盲注一样，后两轮是大盲注两倍）。
两人有限注德州扑克（HULHE）因为玩家的选择比较少可以暴力计算，已经在2015年被Univ of Alberta解决，得到的策略离纳什均衡点非常近了（见这篇文章，发上了Science，AI叫Cepheus，用的方法是CFR+）。
这次CMU和Alberta用的方法，也和之前的类似，都是Counterfactual regret minimization (CFR)的变种。这次的主要贡献在于：
DeepStack用上了Continuous Resolving，即动态地解子游戏以避开存储海量策略时内存不足的问题，还有值网络；
CMU用了endgame solving以细化状态空间和策略空间，当然他们的文章似乎还没有公布，细节还不明朗（比如说剪枝应该是用上的）。
CFR的思路非常简单，从随机策略开始，每次优化一个玩家的策略以提高其收益并反复迭代，最后取平均策略作为最终策略。每次优化用的是悔恨值最小化（Regret minimization）的办法，所谓悔恨值就是事后最优选择的收益，减去当时选择的收益，悔恨值最小化就是把到目前为止的累计悔恨值拿过来，看哪一步累计悔恨值高，以后就多走这一步，至于多走的概率，有各种算法（比如说Regret Matching和Hedge）。
对于两人零和游戏，可以证明CFR会收敛到纳什均衡点，也就是“反正我就这么一招，你怎么也破不了”这样的终极招数。所以计算机现在使用的算法，最终目的并不是要利用对方弱点获得胜利，而是找出神功以达到无人可敌的境界。当然要达到这个境界，训练过程中仍然是不断找对方弱点让自己变强。
CFR是个带有理论界的通用算法，说它可以解决一切的非对称信息博弈问题也不为过。但是世界上自然没有免费午餐，在跑CFR的时候，每次都要遍历一次游戏所有可能的状态，而任何一个稍微复杂点的游戏都有指数级的状态，所以运行时间上肯定是不能接受的。
这就有很多折中办法，比如说状态量化（认为2到9都是小牌用同一个策略处理），剪枝（对方不太可能走这一步，那就不用再搜索下去了），随机采样（采样一些路径以代替全部的游戏分支），函数拟合（比如说用值网络来代替深层搜索），等等。
总的来说，CFR和几年前的RL很像，都是传统AI的带理论界的老方法，都是在现实问题中有指数复杂度，都是现在渐渐开始深度学习化，所以我相信以后会有更广阔的发展。
雷峰网特约稿件，未经授权禁止转载。详情见转载须知。
