500万场对局!谷歌工程师利用AI探索最优套牌
2022年9月6日
点火73 回复45
万智牌
万智牌:竞技场

我非常了解,看到标题点进来阅读正文的你非常急切地想了解到底哪套牌是AI算法得出的最优解。但实际上这篇文章将要讨论的其实是解题思路,以及一点点对于未来的展望。我会在文章某处穿插地告诉大家牌表是什么(以方便大家借鉴),而且我不会以图片的形式呈现,以免你们一上来就去看牌表图,然后在不阅读文章的情况下对这个牌表进行错误的评价。

 

这是Dr. Ruckus,一位谷歌工程师。Ruckus想要找出最好的套牌配置,为玩家们剩下珍贵的金钱(或MTGA上的野卡)。他在完成实验后,将自己的成果制作成了视频发表在了油管上(地址在这里)。下面我们直奔主题,一起来看看他是如何通过AI技术实现这个目标的。

 

 

第一步、搭建MTGA

实验的目的是将游戏过程简化为一次次快速的计算,所以不可能依靠现有的MTGA程序来实现。Ruckus把整个MTGA拔下来重写了一遍,这样便可以在复制品上快速模拟对局。他说,这个过程就像是教给一个完全没有玩过万智牌的人有关万智牌对局的一切知识,而且在所有系统规则外还要教会他们每一张单卡的效果。这听上去工作量非常大,但我们相信谷歌工程师可以在较短的时间里用各种办法解决这些相对重复性的问题。

 

 

第二步、人工智能

之后Ruckus“教会”了AI如何进行万智牌对局,其实很类似于AI下围棋,不过演算支会更加复杂。他认为他训练出来的AI80%的表现都非常理想,缺点在于有些时候不够远虑,这来源于算力不足。他还提到AI玩牌有一个优势,在于永远不会遗漏触发,光做到这点应该就能击败不少人类牌手了。(括弧笑)

最终他训练出的AI达到了现有条件下(指计算机硬件)的最佳平衡状态——玩得足够快的同时尽量玩得好,这就为模拟大量对局奠定了基础。

 

 

第三部、模拟环境

我个人认为这部分开始体现Ruckus的聪明才智了,毕竟他使用的设备只有自己的计算机,算力有限,在上一步一定程度上简化了人工智能之后,他进一步进行了简化操作。我们知道一个正常的T2环境至少会有若干套T1套牌(比如ELD的T2就不正常),上个版本末期的环境大概如下:

我们可以将它简化为:

基本都是快攻以及少量控制。而快攻套牌中一家独大的是小白快,所以...

这便是Ruckus第一次实验使用的Meta!全部都是小白内战!当然,读到这里你会说,那这样得到的实验结果是毫无意义的。这是完全正确的结论,不过这个初次实验的目的并不是为了得到答案(所以我也没有着急把牌表分享给大家,因为这个牌表本身不具有任何参考意义),而是为了测试流程,检验思路是否正确。这就好比我们平时做物理题的时候都会假设存在一个“小滑块”,但它并不具有现实意义,而只是一个数学模型而已。

不过Ruckus在承认这个缺陷的同时,还进行了一些补充:如果一个环境里大部分套牌都是快攻,那么是不是其实忽略小部分控制,针对快攻调整主牌(因为这里测试的是BO1),得到的结果会非常接近全环境最好的套牌?而且他还指出,MTGA会倾向为你匹配使用类似套牌对的对手(我相信你们也都有体会),因此测试100%的小白快内战也不是完全没有意义(唯一美中不足的是现在套牌退环境了)。

 

 

第四步、样本容量和结果可靠性

经过累积分布函数(cumulative binominal distribution function,我把维基链接放在这里了)计算,Ruckus认为10000局对局可以得到99.95%准确的胜率。这个量对于我们肉身打牌来说还是有一些困难,但是AI不会在这个过程中体会到任何痛苦(真是太好了!)现在,如果AI进行10000局游戏,测出一个对局的胜率所花费的时间是30分钟左右。

 

 

第五步、单卡组合

这里来到了最神秘的一步——当我们听到“利用AI测试环境最好套牌”这个命题的时候,我们难免会想到,是让AI从零开始,直接通过赛制中所有可用的单卡排列组合出一套牌来。这个计算量对于个人计算机来说是不现实的(说真的,如果有这个算力肯定会去直接挖矿吧...)实际上,Ruckus仍然是从人类得到的胜率最高纯白套牌起步的:

经典

我们以这套牌为原型,对它进行一组单卡的变动(例如,增加一个艾德琳,减少一个锁咒僧),即可测出这个改动相较于原型来说是更优化还是更弱化,例如增加一个艾德琳,减少一个锁咒僧这个改动将套牌胜率提升了1.5%,如果我们增加一个平原,减少一个辉侯求索客,结果是套牌胜率降低了1.3%。如果我们先测出每一个单项变动收益最大的版本,再基于这个版本重复此流程,最终便会得到最优解。但是,很遗憾的是这个计算量对于个人计算机来说仍然非常巨大,需要4天的时间才可以完成。

Ruckus进行了最后一次时间上的优化——不直接测试一对对的单卡变动,而是简单地增加某一个单卡一张,将套牌变成61张,然后再减少一张,将套牌变成59张。利用这些+1和-1后的套牌和原型进行测试,得出结果后,将+1胜率提升最多的情况和-1胜率提升最多的情况叠加。

比如在这张图中,+1提升最多的是次元洞和空境亡灵(很好理解,因为对手都是小生物套牌),而-1提升最多的是精英锁咒僧(锁不到快攻的东西)。

这是一个非常大胆的优化,它不一定能带来最优解,但能得到足够好的结果。不过Ruckus也说明此算法有一个缺陷,那就是它可能会错过全域最大值,而只测出局部最大值,这与我们的原型套牌有关。想要解决这个问题需要用到贝叶斯算法,这一期测试中没有考虑这个步骤一是为了节省时间,二是因为此问题比较容易出现在Synergy非常强的原型套牌里,这里使用的原型小白快没有这个问题。

 

 

第六步、结果与分析

经过了两周、500万场对局的计算,Ruckus的测试终于来到了终点——一套不论你怎么改变结构,胜率都会下降的套牌。

4 可雕学徒 
4 携带式次元洞 
3 领途导灵 
4 旭金哨卫 
4 辉侯求索客 
4 无畏仇敌 
4 空境亡灵 
4 护教蛮兵 
4 华辉护教军艾德琳 
1 军团天使 
20 平原
4 霜龙洞穴 

这个测试结果其实并不令人感到意外——不要忘记我们的环境里只有小白快,能够高效去除对手生物的生物显然得到了最大发挥蛮野护教军、空境亡灵全部满编。而那些针对控制的单卡全部被淘汰下岗,莎利雅、锁咒僧和英灵神瑞丹妮。

次元洞满编,我个人认为这并不只是因为它可以高效去除生物,更是因为环境里也有大量的次元洞,可以互相去除,这情形就有一点像是没有被禁的心灵失足——为了对抗心灵失足,当然是满编心灵失足啦。

所以,这个测试结果基本符合了我们的预期,AI改牌没有做出特别离奇的选择,侧面说明测试思路本身是合理的。接着Ruckus用这套牌去天梯受虐了,其实打快攻体验是很不错的,面对跨金桥巨龙则真的非常难受。

 

AI测牌,能行吗?

首先,通过上面的测试步骤,我们不难发现,万智牌的容量并不允许我们使用AI全权接管套牌构筑的工作——计算量太大,且收益有限。Ruckus仍然需要利用人类依靠对局经验组出来的套牌作为模板,再层层深入。而且我们看到整个模拟过程中做出了诸多让步:

  • 进行测试的AI不是“最强”的万智牌AI,它们对对局进展的分析能力有限;
  • 模拟测试的环境本身就是纯理想化的,缺少其他类型套牌参与;
  • 单卡修改仅局限于现有套牌的牌张选择,没有考虑到增加新种类单卡的可能性,也没有考虑备牌;
  • 所得到的结果并不是严格的最优解,因为没有使用“动态”的优化,而是一层一层递进的。

即便是这样宽松的实验,也占用了一个谷歌工程师和一台家用电脑一周的时间。我们也许可以增强算力,但是这样会带来明显的经济负担——我们有必要通过这种方式来探索最强的万智套牌吗?它能给我们带来足以弥补租金和电费的效益吗?而且,我们还面临一个严肃的问题——一个一周就被AI破解的环境,还能好玩吗?也许这项研究在不久的未来可以成为某些战队的测试辅助工具,就像专门为游泳比赛开发的鲨鱼衣一样。但我们显然不希望万智牌这么快就迎来AI暴力破解的那一天。

诚然,Ruckus的实验存在很多技术局限,但他的整体思路是非常值得借鉴的,这篇文章的初衷也在于分享他的解题思路,而不希望大家把注意力放在他得到的那套畸形小白快上。从原视频中观众可以直观感受到他作为谷歌工程师拥有的清晰的条理性,我个人推荐有条件的读者可以再看一遍原视频。你怎么看待这项研究?你觉得AI替代人肉测牌是件好事吗?欢迎在评论区留下你的看法!

打赏文章
全部评论 45条
按时间排序

还没有评论