【新智元导读】攻克围棋后,什么是AI的下一个征程?打扑克!相比信息完全可见的围棋,能够猜疑、虚张声势的德扑要困难得多。冷扑大师Libratus是首个在无限手一对一德扑中战胜人类职业玩家的AI,相关论文也在NIPS 2017获得了最佳论文奖。不过,这篇论文不是一般的难!本文中,邓侃博士将从纳什均衡策略、反事实最佳策略等4个方面,生动举例,带你读懂人工智能如何打德扑。
真实的生活,(不会像围棋那样)可以毫无遮拦地洞察整个棋局。真实生活中充斥着虚张声势、欺诈、揣度对方心理。这才是我所研究的博弈。 ——冯·诺依曼
冷扑大师 Libratus 与“冷门” NIPS 2017 最佳论文
CMU 教授 Tuomas Sandholm 及其学生 Noam Brown 所开发的人工智能德扑系统 Libratus,被国内同行翻译成 “冷扑大师”。冷扑大师在 2017年1月,与四位德扑职业高手对阵,大获全胜,赢得了接近总数的筹码 [1]。
2017年11月,Noam Brown 与 Tuomas Sandholm 合著的论文,“Safe and Nested Endgame Solving for Imperfect-Information Games”,获得 NIPS 2017 最佳论文奖 [2]。
但是这篇最佳论文,在国内业界引起的讨论,似乎不算特别热烈。原因可能有三条,
1. 这篇论文非常不好懂。光数学符号的定义,就整整占了一节内容。数学符号定义结束后,是很大篇幅的定理证明。初读一遍,云里雾里。
2. 非热门的理论根基。当下热门的机器学习领域,是深度学习和强化学习。而这篇论文的理论根基,是博弈论和运筹学。
3. 方法论的通用性。若干读者认为,冷扑大师的算法,可能仅仅适用于德扑,或者充其量能够扩展到其它棋牌类游戏。应用前景有限。
11月8日,Tuomas Sandholm 来北京参加新智元举办的世界人工智能大会AI World 2017,并做主题演讲。餐叙时,Sandholm 教授对笔者说,从应用前景来说,冷扑大师的算法,不仅可以用于赌博,也可以用于谈判,拍卖定价,投资决策等等。
11月8日,Tuomas Sandholm(中)来北京参加新智元举办的世界人工智能大会,餐叙时与新智元创始人兼CEO杨静(左)和本文作者邓侃博士交流
从方法论来说,冷扑算法的理论根基是博弈论和运筹学。而强化学习学习的理论根基是马尔科夫决策过程和动态规划。虽然来源不同,但是终将殊途同归。
冷扑算法与强化学习和深度学习殊途同归之日,必将大放异彩。
冯·诺依曼曾经这样说,“真实的生活,(不会像围棋那样)可以毫无遮拦地洞察整个棋局。真实生活中充斥着虚张声势、欺诈、揣度对方心理。这才是我所研究的博弈。”
读懂冷扑大师这篇最佳论文,关键是理解四个概念,
1. 纳什均衡策略,
2. 反事实最佳策略,
3. 抽象,
4. 终局。
冷扑大师的算法与纳什均衡策略:不让对方占便宜
目前冷扑大师只会打双人德扑。当然,把算法改进一下,多用几核 GPU,也可以打多人德扑。
打德州扑克时,先发给每个牌手两张暗牌,然后陆续发 5 张明牌,期间 4 轮下注,最后比大小 [3]。
德扑难在揣摩对手的两张暗牌。公开的信息,是 5 张明牌和双方下注的历史。但是,对方不会严格按照自己手中的暗牌来下注,而是有意夹杂着各种误导战术,譬如虚张声势等等。
冷扑大师是如何识别对手的下注策略呢?
其实,冷扑大师不推测对手的下注策略。
稍微具体一点,冷扑大师追求的目标,是能够达到纳什均衡(Nash Equilibrium)的策略。纳什,就是著名的数学家,电影《美丽心灵》的男主角。纳什均衡策略,是不让对方占便宜的策略。
纳什均衡策略是被动的防御策略,而不是主动的进攻策略。也就是说,纳什均衡策略不揣度对手的下注策略。
举个例子,假如对方的策略,是不论自己手上的暗牌是什么,不动脑子地一味跟着我方下注。打了几手以后,即便我方发现了对方的策略,根据纳什均衡,我方也不会趁自己牌好时,冒进地抬高赌注,赚对方便宜。
纳什均衡策略,不揣度对方的策略。但是,对方会不会寻找纳什均衡策略的漏洞?
理论上说,纳什均衡策略能够保证,在经过了多次牌局摈除了运气的成分后,是不存在被对方利用的漏洞的。
问题是,冷扑大师的算法,是不是严格意义上的纳什均衡策略?这篇论文,之所以大段大段证明数学定理,目的就是为了证明,至少在一对一的情况下,冷扑大师的算法,是逼近纳什均衡策略的。
如何寻求最佳下注策略?先做一个下注对应表
既然纳什均衡策略不揣度对手的下注策略,那么就可以用机器自我博弈的办法,尽可能枚举各种可能的牌局,寻求最佳的下注策略。
我们不妨做一张下注对应表(Action Mapping),七列,若干行。
其实,可以通过第三列(双方下注的历史)来推算第四列(我方手上剩下的筹码)。设置第四列的目的,是为了方便。
前四列是输入,论文中被称为局面(Information Set,InfoSet)。后三列是输出,分别是推测、决策和收益。
假如我们有足够的计算能力,我们枚举各种可能的局面(InfoSet)。
第一列,我方手上两张暗牌(pre-flop),总共有 (52 * 51) / (2 * 1) = 1,326 种组合。
第二列,先发三张明牌(flop),总共有 (50 * 49 * 48) / (3 * 2 * 1) = 19600 种组合。然后,再两次发单牌(turn、river)。加起来,总共有 19600 + 19600 * 47 + 19600 * 47 * 46 = 43,316,000 种组合。
如果把第一列和第二列的所有组合加在一起,那么总数是 1,326 * 43,316,000 = 57,437,016,000。
第三列下注及其历史,组合数量就更多了。所以,这张表的行数巨大,论文上说是 10^165 行。这个数量级太大了,即便用当今世界最强大的云计算系统,估计也得算上几十年。
不过,假如我们有足够的计算能力,能够遍历出这张表,那么我们就可以计算出面对特定的牌局,各种下注决策对应的平均收益。
譬如,发完全部 5 张明牌之后(river),对方手里的两张暗牌,总共有 (45 * 44) / (2 * 1) = 990 种组合。又假如,前三轮下注(pre-flop, flop, turn),总共有 N 种下注历史。这时候如果轮到我方下注,每一种下注策略,譬如下注手头剩下的全部筹码(all in),将面临 990 * N 种可能的收益。这 990 * N 种收益的平均值,就是这种下注策略的平均收益。
面对特定的牌局,我们计算出了各种下注决策对应的平均收益以后,就可以找出平均收益最高的那种下注决策。
平均收益最高的那种下注决策,是否就是纳什均衡策略?不是。
原因是,当对方手里的暗牌的牌力很低时,譬如对方手里的两张暗牌是一张红桃三一张梅花六(3h6c),对方大金额下注的概率很低。
那么,如何估算对方下注策略的概率?
这个问题比较复杂,因为对方下注,不仅仅依据对方手里的暗牌和桌面的明牌,而且,对方会根据我方下注的历史,来估算我方手里的暗牌。
反事实最佳策略:寻找纳什均衡策略的流行算法
反事实最佳策略(Counterfactual Best Response, CBR ),是一种近年来比较流行的,寻找纳什均衡策略的算法 [4]。
反事实最佳策略有三大要素:1. 模拟,2. 悔牌(regret),3. 迭代(iteration)。
面对各种局面(InfoSet),也就是前述的局面下注对应表的前四列,先假设我方以随机均等概率选择下注策略。这样经过一系列发牌和下注,牌局结束,然后清点我方的收益或损失。
这样模拟几亿次牌局,大致覆盖各种可能的局面。
然后悔牌。面对某种特定局面,也就是固定住对应表的前四列,换句话说,也就是我方有特定的两张暗牌,桌面上有最多五张特定的明牌,再加上特定的下注历史。悔牌的意思是,面对某种特定局面,我方不随机选择下注策略,而是只认定一种下注方式,譬如跟注(call)。
悔牌以后,后续亮出的明牌,不会改变。但是我方和对方,后续下注的历史会发生改变。
把刚才几亿次牌局,重新模拟一遍。重新模拟时,双方暗牌和桌面上的明牌不变,发牌顺序不变,悔牌以前的下注历史不变,但是悔牌以后的下注历史改变。每次下注时,除了悔牌那个特定策略,其余的下注策略不变。
这样重新模拟了一次以后,就可以计算出悔牌的策略,平均收益是多少。
然后换一种悔牌策略,也就是面对同样局面,只认定另一种下注方式。譬如前一次悔牌的策略是跟注(call),这一次模拟的悔牌策略,改为加码(raise),然后把刚才几亿次牌局,重新模拟第二遍。这样就可以计算出第二种悔牌策略的平均收益。
模拟了若干次以后,就可以估算出,面对同样的局面,各种可能的悔牌策略,及其平均收益。
重复以上模拟过程,确定各种局面的各种策略,及其平均收益。
然后,更新下注对应表(Action Mapping)。先清空表中第五列,也就是不枚举对方手上的两张暗牌。然后在第七列,填入每一种下注策略的平均收益。
以上是第一轮模拟和悔牌,然后进行第二轮模拟。
第二轮模拟时,先假设对方仍然按照随机均等的概率,选择下注策略。而我方根据第一轮更新后的下注对应表,选择下注决策。
面对同样一个局面,也就是表中的前四列,我方按以下方式选择下注策略。
1. 先根据当前的局面,也就是暗牌明牌加下注历史,找到更新后的下注对应表中,所有相应的行。
2. 更新后的下注对应表中,第六列是下注策略,第七列是平均收益。根据平均收益,选择下注策略。收益越高,相应下注策略被选中的概率越高。
这样,确定了第二轮模拟的暗牌明牌,发牌顺序,以及我方和对方最初下注历史。
然后,悔牌。并再做一个下注对应表,记录面对各种局面时,各种下注策略的平均收益。
第三轮模拟时,我方用第二版下注对应表,对方用第一版下注对应表。经过多次模拟过程,得到第三版下注对应表。
如此重复迭代。经过多轮模拟迭代以后,所得到的下注对应表,将是逼近纳什均衡的最佳策略。
简化牌局,降低计算负担
如第三节所述,下注对应表中,单单第一列和第二列的组合,就高达 57,437,016,000 种。如果在加上各种可能的下注历史,那么下注对应表的行数,是 10^165 数量级。
另外,用反事实最佳策略算法,来寻找纳什均衡策略,需要经过几十亿次模拟。
下注对应表的行数太多,反事实最佳策略算法的模拟次数太多,导致计算量太大,难以承受。
一个显而易见的解决办法,是简化牌局(Abstraction),以便精简下注对应表的行数。
譬如,一个对子,红桃八和黑桃八(8h8s),与另一个对子,方片八和梅花八(8d8c),这两个对子的牌力,是相似的。所以,可以把两个八的对子,总共 (4 * 3) / (2 * 1) = 6 种组合,都简化成下注对应表中的一行。
但是牌力的计算,需要很仔细,譬如一对八,与一个八一个九,哪一种组合的牌力大?假如 5 张明牌分别是七、十、勾、外加两张散牌,那么一个八一个九可以与明牌组合成从七到勾的顺子,而一对八与五张明牌的最大组合,仍然是一对八。
所以,牌力的计算,不仅要看牌面本身的大小,而且要枚举两张暗牌,与 5 张明牌的各种可能的组合。[5] 详细讲述了牌力的计算方法。另外,也讲述了如何根据牌力,对牌面进行抽象的做法(Card Abstraction)。
DeepStack对牌面进行抽象,详见[5]
不仅对牌面要进行抽象,而且对下注也要进行抽象,譬如只允许四种下注方式,弃牌(fold)、跟注(call)、加码(raise)、孤注一掷(all in)。
经过抽象后,牌局组合的总数,被大大降低。譬如 [4] 把总数为 10^165 的牌局组合,简化到 10^12。
牌局组合总数降低后,反事实最佳策略模拟迭代,就可行了。
终局,误算与精算
但是,简化牌局,会导致误算。譬如根据牌力,我们把一对七与一对八,归为同一种局面。但是,假如双方一路对赌到底,谁也不中途弃牌(fold),只好最后亮牌(showdown)。
亮牌的时候,我方一对七,对方一对八,虽然牌力区别微小,但是却决定最终胜负。这就是所谓误算(Off-tree Problem)。
解决误算的办法,是用精算(re-solving)来替代抽象(abstraction)。
精算的核心,是通过拟合双方下注历史,来反向推算对方手里的两张暗牌,及其概率。
假设我方的两张暗牌是 h1,对方的两张暗牌是 h2。又假设我方和对方,都按照反事实最佳策略来下注,那么就可以通过查找下注对应表,推算出各种下注策略的概率。
譬如,pre-flop 时,我方的暗牌是一对八,对方的暗牌是一对 A。假如首次下注由我方开始,我方加码(raise)的概率很大,但是 all-in 的概率几乎为 0。但是对方 all-in 的概率,会比 0 大很多。
现在给定一个特定的下注历史,我们可以通过查找下注对应表,计算出每一步下注的概率。所谓下注历史,就是一连串的下注,下注历史的概率,就是一连串概率的乘积。
通过计算下注历史的概率,我们不仅可以估算对方手里的暗牌,而且还可以估算对方背离正常的下注策略的幅度和波动,也就是说,我们能够估算得出对方虚张声势(bluffing)的概率。
估算出了对方的暗牌,以及对方 bluffing 的概率,终局的精算,就比较容易了。无非是把对方的暗牌,与我方的暗牌相比较,推算出我方胜出的概率,以此决定下注的金额。
参考文献: