欢迎光临
中国顶尖人工智能与机器人行业新媒体平台

Facebook田渊栋:德州扑克上战胜人类的AI究竟用的是什么算法?| 解析

雷锋网(公众号:雷锋网)按:本文作者田渊栋,卡耐基梅隆大学机器人系博士学位、上海交通大学硕士学位和学士学位,前谷歌无人车项目组成员,现任Facebook人工智能组研究员,主要负责Facebook的智能围棋项目Dark Forest。文章转载自知乎专栏,雷锋网已获授权。

Facebook田渊栋:德州扑克上战胜人类的AI究竟用的是什么算法?| 解析

最近听说我的母校卡耐基梅隆大学德州扑克的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的带理论界的老方法,都是在现实问题中有指数复杂度,都是现在渐渐开始深度学习化,所以我相信以后会有更广阔的发展。

      雷锋网特约稿件,未经授权禁止转载。详情见

赞(0) 关注公众号

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

公众号也精彩

微信扫一扫打赏