用数学方法分析哪类游戏中的AI难度最大

作者：可厉儿 超参数科技 2019-10-12

2019年是AI在游戏领域全面开花的一年。

1月，DeepMind开发的AlphaStar在《星际争霸II》比赛中以5:0战胜了职业选手MaNa；4月，OpenAI开发的OpenAI Five在《Dota 2》比赛中2:0战胜去年的TI 8冠军OG；7月，Facebook和CMU联合开发的Pluribus在6人不限注德州扑克比赛中战胜人类世界冠军；8月，微软开发的Suphx在专业麻将平台“天凤”上荣升十段，跻身仅10余位的现役十段选手之列。

自2016年AlphaGo横空出世、掀起游戏AI浪潮以来，围棋、星际争霸、Dota、德扑、麻将，一座座号称“人类智慧高地”的游戏被AI逐一攻克。

一个常见的疑问是，AI挑战过的这些游戏，它们的复杂度能否有一个直观的衡量和对比呢？接下来，我们会从状态空间和操作序列空间这两个维度，来尝试衡量一款游戏的复杂度。对AI来说，前者反映了输入信息的复杂度，后者反映了输出行为的复杂度。

状态空间

状态空间（State Space）反映了游戏过程中所有符合规则的状态的总数量。通常情况下，为了便于计算，估算时会包含进一些不会在现实游戏中出现的情况。比如在估计井字棋的状态空间时，会考虑所有位置均为X或均为O的极端情况，得到3^9这个结果。（盘面上共有9个位置，每个位置可能的取值有X、O或空缺这3种）



在围棋中，考虑到盘面上一共有19*19=361个位置，每个位置可能的取值有黑子、白子或空缺这3种（包含进了棋盘全为黑子或全为白子的极端情况）。因此围棋的状态空间为3^361≈10^172。


麻将的状态空间会复杂一些，但还是可以做个近似的估算。在不考虑吃碰杠等情况的前提下，在一局麻将中的任一时刻，我们把136张麻将牌分为三类：第一类是游戏最后剩下的14张牌，由于这些牌不会被用到，所以不用考虑先后顺序，这里的可能情况是C(136,14)种；第二类是四个玩家各自手里的13张牌，这些牌也没有顺序，所以对应的可能情况有C(122,13)*C(109,13)*C(96,13)*C(83,13)种；第三类是剩余的70张牌，这些牌要么还未被翻开，要么已经被某位玩家打出，这两种情况都是有先后顺序的（因为顺序变化会影响到对胜率的预估），对应的情况是先对70张牌取排列数=P(70,70)，然后每个排列可以从70个位置中的任一位置形成断点（断点前为玩家打出牌的序列、断点后为未翻出牌的序列），总可能情况是P(70,70)*70。将三类牌的可能情况数做连乘，结果约等于10^184。

麻将状态空间估算

德州扑克的计算方式会更复杂一些。在两人有限注德扑中，游戏有4个回合，每回合双方共有至多4次下注机会，状态空间为10^17[1]。在两人不限注德扑中，由于下注额没有限制，变化会多很多，状态空间为10^165[1]。（详细计算过程可参见附录链接）

而对于Dota2和星际这样的游戏来说，由于游戏本身的状态是连续的，无法拆分成离散的节点，不能像之前那样计算。这种连续体现在两个方面：一是时间层面的连续，游戏中的行动是即时的（而非回合制的），这导致无法在时间上分别计算不同的状态空间再做累加。不过鉴于任一时刻的决策其实只依赖于当前状态（在完全相同的当前状态下，玩家之前是先造的兵营再造的补给站、还是先造的补给站再造的兵营，并没有差别），我们可以不考虑历史状态、仅计算截面状态的数量；二是空间层面的连续，坐标、移动方向、技能方向等都是任意的（玩家可以左转30度，也可以左转30.01度），这导致我们必须对状态做简化，否则状态空间会无穷大。

具体来说，对于Dota 2，（在简化后）假设把地图划分为100*100个区块，当前时刻存在10个英雄，假设每个英雄有50个属性（包含装备情况、技能CD等）、每个属性有100个取值，则对应的状态空间为(100*100*100^50)^10≈10^1000。这里还没有考虑进野怪、防御塔、兵线等信息。


对于星际，（在简化后）假设把地图划分为128*128个区块，假设当前时刻同时存在200个单位、每个单位有20个属性、每个属性有10个取值，则对应的状态空间为(128*128*10^20)^200≈10^5000。


需要说明的是，对于麻将、德扑、星际、Dota2这类不完美信息游戏（Imperfect-Information Games）来说，参与者无法随时访问全部游戏信息（比如其他玩家的手牌、战争迷雾中的情况等），这给AI带来了更大的挑战，很难使用传统的蒙特卡洛树搜索方法。

操作序列空间

操作序列空间反映了游戏中所有不同操作序列的数量。也很难精确计算，一般的估计方式是利用平均动作空间（Action Space）和游戏长度（Game Length）这两个参数。前者表示每次操作的平均可执行动作数，后者表示整局游戏中的总操作次数。操作序列空间=平均动作空间^游戏长度。

围棋中，平均一局游戏进行150手、每一手平均有250个解，因此操作序列空间为250^150≈10^360。

麻将中，每局游戏至多会进行17.5轮（(136张牌-14张底牌-13张手牌*4家)/每轮出4张牌），考虑吃碰杠带来的增加和提前胡牌带来的减少，假设平均进行15轮，每轮从14张手牌中选一张打出，因此操作序列空间为14^15≈10^17。

德州扑克中，两人有限注德扑的操作序列空间≈10^15[1]，两人不限注德扑的操作序列空间≈10^162[1]。（详细计算过程可参见附录链接）

Dota 2游戏中，根据OpenAI在OpenAI Five博客[2]中披露的数据：游戏时长45分钟、每秒钟30帧，共计80,000帧，AI每4帧进行一次操作，共计20,000次操作，这是游戏长度。任一时刻每个英雄可能的操作数是170,000，但考虑到其中大部分是不可执行的（比如使用一个尚处于冷却状态的技能），平均的可执行动作数约等于1,000，也即动作空间。因此，操作序列空间约等于1000^20000=10^60000。

星际游戏中，根据DeepMind在AlphaStar现场访谈[3]中披露的数据：平均动作空间约等于10^26，游戏长度在1,000级别，我们假设为2,000，则操作序列空间为(10^26)^2000≈10^52000。

下表整理了上述5款游戏在状态空间和操作序列空间这两个维度的复杂程度，我们也加入了一些更简单的棋牌游戏作为对照[4]。


总结

从上表不难发现，更大的状态空间和操作序列空间意味着更复杂的游戏，往往也意味着更高难度的AI训练。向未来看，伴随着更大的游戏地图、更多的同局玩家数、更复杂的属性维度，状态空间会进一步增加；而伴随着更多的操作选项、更快的操作手速、更长的游戏时间，操作序列空间也会进一步增加。

百尺竿头，更进一步。我们期待AI能逐一攻克更难更复杂的游戏。

作者：可厉儿  
来源：超参数科技
原地址：https://mp.weixin.qq.com/s/g_NKLYp_gQ23YzGNEUeGOg

参与评论