换一个表述的威力——虚拟对弈的新生

      目前,游戏 AI 领域方兴未艾,出现了大量的新方法新构思。棋牌游戏中的牌类游戏 AI,比如德州、扑克和斗地主等,也在博弈论方法的基础上,发展出了新的思想和方法。今天就介绍其中古老的虚拟对弈 (Fictitious Play, FP) 算法在机器学习大行时代的新变化。

1. 基本概念和符号定义

      正则式表述 (normal-form game) 和扩展式表述 (extensive-form game) 是博弈的两种表达。正则式表述将博弈表述为:每个玩家同时出一个动作,然后进行根据玩家的动作结算收益。扩展式表述则将博弈表述为:让玩家交替出动作,直到博弈结束之后结算玩家收益。一个博弈,既可以用正则式表述进行表述,也可以用扩展式表述进行表述。

1.1 扩展式表述

      扩展式表述侧重描述多位玩家交替出动作的过程,整个扩展式表述基于游戏树,由下面几个部分组成:

1.1.1 玩家

      在扩展式表述中的玩家包括普通玩家 \(N = {1,..,n}\) 和上帝玩家 c,其中上帝玩家决定博弈中的随机事件。比如斗地主中,每个普通玩家手中的牌就由上帝玩家决定。

1.1.2 状态和动作

      \(S\) 表示游戏树节点对应的状态集。对于每个状态 \(s \in S\),连到后续状态的连线则是这个状态下的可选动作,用 \(A(s)\) 表示。玩家函数 \(P: S \rightarrow N \cup c\) 则是根据状态决定由哪位玩家采取动作的函数。对于每位玩家,扩展式表述存在一个有效信息状态 (Information State) 的集合 \(U^{i}\), 和一个有效信息函数 \(I^{i}:S \rightarrow U^{i}\)。为什么会存在有效信息状态 \(u\) 呢。这是在非完美信息博弈中,玩家不是了解所有的信息,比如斗地主中对手的牌。这样游戏树中的不同节点对某个玩家可能是一样的。引入有效信息状态之后,我们用有效信息状态将这些不同状态归并在一起。

1.1.3 奖励

      游戏树中的叶子节点表示博弈结束。该结算每位玩家收益的时候了。我们定义 \(R:S \rightarrow R^{n}\) 表示效用函数,其中 \(R^{n}\) 表示 n 个普通的玩家的收益。

1.1.4 策略

      一个玩家的行为策略 (behavioural strategy) \(\pi^{i}(u) \in \Delta(A(u))\) 给有效信息状态 u 下候选动作 A(u) 赋予概率值。\(\Delta_{b}^{i} \) 表示玩家 i 的行为策略的集合。一个策略配置 \(\pi = (\pi^{i},…,\pi^{n})\) 表示所有玩家一组策略, \(\pi ^{-i}\) 表示除了玩家 i 其他玩家的行为策略。基于游戏的效用函数 \(R\), \(R^{i}(\pi)\) 表示所有玩家遵循策略配置 \(\pi\) 的情况下,玩家收益的期望。
      在其他玩家策略 \(\pi^{-i}\) 固定,玩家 i 的最佳策略为

\begin{eqnarray}
b^{i}(\pi^{-i}) = argmax_{\pi^{i} \in \Delta_{b}{i}} R^{i}(\pi^{i},\pi^{-i}) \nonumber
\end{eqnarray}

玩家 i 的 \(\epsilon\)-最佳策略为

\begin{eqnarray}
b_{\epsilon}^{i}(\pi^{-i}) = \{ \pi^{i} \in \Delta_{b}^{i}: R^{i}(\pi^{i},\pi^{-i}) \ge R^{i}(b^{i}(\pi^{-i}) ,\pi^{-i}) – \epsilon \} \nonumber
\end{eqnarray}

如果一个策略配置中所有玩家相互都是最佳策略,那么称这个策略配置达到了纳什均衡 (Nash Equilibrium)。如果一个配置中所有玩家相互都是 \(\epsilon\)-最佳策略,那么称这个配置达到了 \(\epsilon\)-纳什均衡 (\(\epsilon\)-Nash Equilibrium)。

1.2 正则式表述

      正则式表述和扩展式表述本质上是等价的。我们容易知道,任何一个正则式表述都看成扩展式表述。那么是不是任何一个扩展式表述都可以看成正则式表述呢?答案是可以的。对于每个玩家 \(i \in N\) 他们的确定性策略,\(\Delta_{p}^{i} \subset \Delta_{b}^{i}\) 变成正则式表述里的纯策略 (pure strategy)。这时候纯策略可以解释为玩家从 \(\Delta_{p}^{i}\) 中选择一个确定性行为策略,用这个策略参加博弈。

      对于非确定性行为策略, 在正则式表述中对应的概念是混合策略 (mixed strategy)。玩家 i 的混合策略 \(\prod^{i}\) 是他的纯策略的概率分布。一个混合策略配置 \(\prod \in \times_{i\in N} \Delta^{i}\) 是给每个玩家配置一个混合策略,相应的正则式表述也存在效用函数 \(R^{i}: \times_{i\in N} \Delta^{i} \rightarrow R\) 。

2. 虚拟对弈的源头

      虚拟对弈 (Fictitious Play, FP) 是解决完全非完美静态两人零和博弈的一般性算法。在 1951 年,也就中朝军队攻入汉城那年,Brown, George W 提出了 (Fictitious Play, FP) 算法。虚拟对弈(Fictitious Play, FP) 诞生于如此遥远的年代,以至于我们没有办法在 Google 学术上找到原始的论文[1]。2007 年, Berger, ULrich 写了一篇短文 “Brown’s original fictitious play.” [2]。从这篇短文,我们可以窥得虚拟对弈的基本原理。

      我们拿两玩家博弈做例子。让 (A, B) 表示 \( n \times m \) 有两位玩家的博弈的收益矩阵。玩家1 (行玩家),有 n 个纯策略 i = {1,….,n}; 玩家2 (列玩家) 有 m 个纯策略,j = {1,…m}。当玩家 1 选择 i, 玩家 2 选择 j 时,玩家 1 的收益是 A(i,j) 而玩家 2 的收益是 B(i,j)。基于此,我们可以给出虚拟对弈算法的如下定义。

其中定义 5 是交替更新的虚拟对弈,定义 6 是同时更新的虚拟对弈。其中 \(x(t)\) 和 \(y(t)\) 是 t 时刻的两个玩家的平均策略, 而 \(i_{t+1}\) 和 \(j_{t+1}\) 分别是应对 \(y(t)\) 和 \(x(t)\) 的最佳纯策略。了解这些概念之后,虚拟对弈算法就很简单了:随机初始化玩家们的平均策略,每个玩家找到应对其他玩家平均策略的最佳纯策略,将这个最佳纯策略加到平均策略中去。原始论文证明了,在特定条件下,虚拟对弈能够达到纳什均衡。

      虚拟对弈算法有两个关键操作,一个是在对方平均策略基础上求出我方最佳纯策略,另一个是将这次的最佳纯策略加入我方平均策略。后续改进都是围绕这两个操作进行的。

3. 换一个表述的威力

      虚拟对弈从 1951 年提出到现在,都停留在博弈论研究中,并没有用到解决真实世界的博弈游戏中。原因是虚拟对弈 (Fictitious Play, FP) 算法用基于正则式表述的。不知道对于博弈论研究来说,正则式表述和扩展式表述的区别大不大?但对于企图用计算机求解真实世界的博弈来说,正则式表述和扩展式表述的区别就太大了。对于斗地主、德州和桥牌等现实世界博弈游戏,确定性行为策略的数量级是指数级的。正则式表述下,计算机需要从一个确定性行为策略的概率分布。复杂度太高了。

      如果我们能将用扩展式表述重新描述虚拟对弈,我们就能将虚拟对弈的应用范围扩宽到很多现实博弈中。因为在扩展式表述,计算机只需要输入一个有效信息状态,输出一个候选动作的概率分布。在形式上,复杂度减少很多,从而让计算机求解成为可能。DeepMind 的 Heinrich 等人的论文 [3] 便是照着这个思路,尝试用扩展式表述重新表述虚拟对弈 (Fictitious Play, FP) ,其思路将虚拟对弈应用在扩展式表述的博弈上。

      虚拟对弈应用在扩展式表述的博弈上,我们需要将1)计算最佳纯策略和 2)将最佳纯策略加到平均策略这两个操作改写。计算最佳策略需要遍历整颗游戏树,计算每个叶子节点的效用了,汇总得到最佳纯策略。将最佳纯策略加到平均策略比较困难,需要一些理论支持。下面的推论给出来怎么将两个行为策略相加等价于两个混合策略。

根据两个关键操作的改写,我们得到了下面的定理,从而将虚拟对弈算法运用在扩展式表述的博弈上。

      从上面一顿猛操作,我们最终得到了基于扩展式表述的虚拟对弈算法。从正则式表述换到扩展式表述,我们让计算机运行虚拟对弈算法成为可能。

4. 机器学习的渗入

      换一个表述,只是让计算机运行虚拟对弈算法成为可能,要想让其成为现实,我们还有工作要做。上面算法中的求解最佳纯策略操作 (COMPUTEBR) 需要遍历所有的游戏状态,而将最佳纯策略加到平均策略操作(UPDATEAVERAGESTATEGY)需要记住所有的策略(每个策略需要存储所有信息集上的对应动作的概率)。复杂度依然指数级的,限制了这个算法的运用。为了解决这个问题,论文 [3] 进一步提出了用强化学习解决 求解最佳纯策略操作 (COMPUTEBR), 用有监督学习解决将最佳纯策略加到平均策略操作(UPDATEAVERAGESTATEGY)的方法,从而提出了下面的算法。

      

      在这个深度学习火热的时代,自然有人想到将深度学习用到虚拟自我对弈 (Fictitious Self Play, FSP) 中。论文 [4] 用 DNN 替代了传统的机器学习, 取得了一定的效果。

5. 总结

      虚拟对弈是一个古老的博弈论算法,但其一直停留在博弈论研究中,没有被运用于广阔的现实世界博弈。但在现在的机器学习时代,只要将虚拟对弈从正则式表述换到扩展式表述,我们就能用机器学习的手段解决其两个关键操作:1) 对方平均策略基础上求出我方最佳纯策略和 2) 将这次的最佳纯策略加入我方平均策略,从而实现将虚拟对弈应用在更广阔的现实世界博弈。真是精妙的操作。但后来,冷扑大师横空出世,在两人非完美信息博弈上取得了新的高度。相比之下,这几年虚拟对弈的进展的光芒就被掩盖了。

      目前我们正在利用非完美信息博弈工具集 RoomAI 开发不同棋牌游戏的 AI 算法,希望多 Agent 强化学习能够带来一些思考和方法。 RoomAI 是非完美信息博弈工具集。在 RoomAI 中,选手获得游戏环境给出的信息,当前选手选择合适的动作,游戏环境根据该动作推进游戏逻辑;重复上述过程,直到分出胜负;整个过程如下所示。

      欢迎大家 star RoomAI

参考文献

  1. Brown, George W. Iterative solution of games by fictitious play. Activity analysis of production and allocation , 13(1):374–376, 1951.
  2. Berger, Ulrich. “Brown’s original fictitious play.” Journal of Economic Theory 135.1 (2007): 572-578.
  3. Heinrich, Johannes, Marc Lanctot, and David Silver. “Fictitious self-play in extensive-form games.” International Conference on Machine Learning. 2015.
  4. Heinrich J, Silver D. Deep reinforcement learning from self-play in imperfect-information games[J]. arXiv preprint arXiv:1603.01121, 2016.
此条目发表在游戏人工智能, 算法荟萃分类目录,贴了, , 标签。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。