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种)

img1

井字棋状态空间计算

围棋中,考虑到盘面上一共有 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

img2

麻将状态空间估算

德州扑克的计算方式会更复杂一些。在两人有限注德扑中,游戏有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。这里还没有考虑进野怪、防御塔、兵线等信息。

img3

OpenAI Five对单个英雄的观测内容

对于星际,(在简化后)假设把地图划分为128*128个区块,假设当前时刻同时存在200个单位、每个单位有20个属性、每个属性有10个取值,则对应

的状态空间为 (128*128*10^20)^200 ≈ 10^5000

img4

AlphaStar与人类高手MaNa对战时的可视化界面

需要说明的是,对于麻将、德扑、星际、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]

img5

部分游戏的状态空间和操作序列空间大小

总结

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

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


参考文献:

[1]《Measuring the Size of Large No-Limit Poker Games》
https://poker.cs.ualberta.ca/publications/2013-techreport-nl-size.pdf
[2] OpenAI Five Blog
https://openai.com/blog/openai-five
[3] DeepMind StarCraft II Demonstration
https://www.youtube.com/watch?v=cUTMhmVh1qs&t=1636s
[4] Wikipedia: Game complexity
https://en.wikipedia.org/wiki/Game_complexity

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

2019-10-14
0