计算创意学系列(番外篇):组合创造力和自动游戏生成

计算创意学系列(番外篇):组合创造力和自动游戏生成

在计算创意学系列的第二章第三章中,我们花了大量篇幅来介绍组合性创造力(Combinatorial Creativity),尤其是关于组合性创造力的一个非常有人气的理论——概念整合理论(Conceptual Blending)——以及基于概念整合理论的几种组合性创造力的算法实现。

组合性创造力研究的是一种特定的创造力,其中创作者通过在多个看起来无关的知识领域之间建立联系,发现了融合这些知识领域的新概念,继而得到有价值的新点子。比如,由自然界的鸟类得到启发而发明了飞机、从生物学意义上的“病毒”概念得到启发而发明了计算机“病毒”,将传统棋类游戏和角色扮演电子游戏结合而发明出策略战棋类电子游戏,都是组合性创造力的例子。

概念整合理论则以严谨的科学语言形式化(Formalize)了组合性创造力,将新点子的产生描述为思考主体将多个原本无关的概念网络中的概念映射到整合概念网络中的新概念的过程。

由于这套理论提出了关于组合性创造力的一个实实在在的过程模型,它推动了大量用计算机程序来实现自动组合性创造力的尝试。在计算创意学的第三章中,我们介绍了能够将已有概念组合成为新概念的DIVAGO系统、组合互联网上的信息生成比喻句的Metaphor Eyes、能够重组现有图片生成新图片的Deep Dream/Neural Style Transfer。

Neural Style Transfer能够组合来自不同输入图像的风格和内容形成新图像

今天,我们要来考察可计算的组合性创造力的一个更加有趣的应用——通过重组和混搭现有的游戏来生成全新的游戏。

游戏领域的概念整合理论

概念整合理论将来自两个领域的可类比的概念(比如“程序”和“病毒”)表示成两个输入概念网络(“输入空间”)。这些可类比的概念分别处于各自的概念网络,联结着各自领域的其他相关的概念。组合性创造力主体会创建一个新的整合概念网络,其中混合了来自两个输入概念网络的概念(“输出空间”)。

概念整合理论图解:病毒|程序的例子

‌一个自然的想法就是,一个游戏是不是也能表示成这样的概念网络?这个概念网络涵盖了关于这个游戏机制的一切,从而通过混合两个游戏概念网络,我们就能得到一个全新的游戏机制?

由佐治亚理工大学的学者Guzdiel和Riedl在2016年发表的论文《机器学习混合游戏关卡(Learning to Blend Computer Game Levels)》,就实现并探索了这个点子。

在这篇论文中,作者们针对2D平台跳跃游戏(比如超级玛里奥和星之卡比)设计了一种表示游戏关卡结构的层次化的概念网络。这个概念网络中的概念(节点)包括:

  • 每一个有独立行为逻辑的基本游戏对象(比如玛里奥、栗宝宝、库巴、一根水管),
  • 每一个基本游戏对象的所有可能的形态(不同尺寸、不同样式、不同形状的版本),
  • 每一个基本游戏对象可能出现在一个关卡中的数量,
  • 在一个关卡中重复出现的关卡片段。
重复出现的关卡片段的例子

通过在上述这些概念之间建立联接,我们能够用这个概念网络来表达关卡结构的一些内在规律。比如,

  • 库巴有三种形态,可以表示为库巴概念和分别表示库巴的三种形态的概念之间的联结;
  • 水管有高的水管和矮的水管,可以表示为“水管”概念分别与“高的水管”概念和“矮的水管”概念之间的联结;
  • 栗宝宝只会出现在普通的地面上(而不会出现在水管上面或者悬空),可以表示为栗宝宝节点和普通地面节点之间的联结;
  • 火山关卡中有很多熔岩地形,可以表示为火山关卡片段和熔岩地形板块概念之间的连结

这些联结表示游戏元素之间的关系,一方面有具体关系类型的标注,同时还可以有量化的标注。在这篇论文中,作者们就为每个联结引入了一个概率量值。从而,我们不仅可以表达“火山关卡中有很多熔岩地形”, 还可以具体到“火山关卡中出现熔岩地形的概率是多少”。

有了这样的概率标注之后,这样构建起的概念网络同时也是一种概率图形模型(Probabilistic Grapical Model)。通过根据这个概率图形模型进行采样,我们能够生成符合某个游戏内在逻辑的全新的关卡。

游戏元素的概率图形模型,以及通过采样生成的关卡

对于一个有着大量的关卡、成百上千的游戏对象、复杂的游戏机制的游戏来说,可以想像这个概念网络会是非常非常庞大的,以至于手工去构造这样的概念网络成为几乎不可能的事情。

为了解决这个问题,作者们在这篇论文中提出了用统计机器学习的方法自动构建这个概念网络。用户只需要提供一个关卡游玩过程的视频,机器学习算法就能够通过聚类分析(Clustering)的方法将视觉相似度达到一定程度的像素图单元(Sprite)自动识别为一个游戏对象,从而建立其对应的概念网络节点。

类似的聚类分析方法也能用于构建那些在关卡中被重复使用的关卡片段所对应的概念网络节点。有了这个节点之后,就能进一步通过统计节点两两之间共同出现的频次来得到它们之间联结的概率标注。

需要注意的是,这里的这种建立概念网络的统计机器学习方法并不是深度学习(Deep Learning),并不需要使用参数数量庞大的深度神经网络,因此也不需要非常庞大的训练数据集。

有了这样的方法之后,我们就能让算法读取一个游戏关卡1的游玩视频,自动构建概念网络1,再让让算法读取另一个游戏关卡2的游玩视频,自动构建概念网络2,最后使用概念整合的方法来整合两个概念网络得到整合概念网络。

如前所述,整合概念网络同时也是一个概率图形模型,按照它来进行采样,就生成了一个混合了关卡1和关卡2的整合关卡。

一个融合两个不同的超级马里奥关卡生成的新关卡

我们注意到这种方法的一个局限:它所提出的概念网络只能描述一个静态的游戏关卡结构,还没有真正触及到游戏机制——也就是玩家游戏世界的交互规则。

在Guzdial和Riedl在2018年所发表的另一篇论文《Automated Game Design via Conceptual Expansion(通过概念扩展的自动化游戏设计)》,他们在概念网络中增加了描述交互规则的元素。比如,马里奥碰到蘑菇会变大,也能够通过附有特殊标注(逻辑规则)的概念联结得到表达。在概念网络的整合上,这篇论文也使用看起来效果更好的“概念扩展(Conceptual Expansion)”,而不是照搬概念整合理论。

正如我们在概念整合理论的相关章节中提到过的,给定两个概念网络,可能的整合概念网络的数量非常庞大,是输入概念网络的节点数量的指数级别。因此在Guzdial和Riedl的两篇论文中,还需要再引入一个关于什么样的整合游戏才算是好的标准,用这个标准作为生成整合游戏概念网络时的优化目标,优先选择更符合这个标准的那些整合游戏概念网络。

这个优化目标可以是任何能够用可计算的方式来评估的量值,比如说:

  • 整合概念网络本身的的内聚性(Coherence):比如,一个将火山映射到雪山并将熔岩映射到冰川的整合游戏概念网络,比起一个将火山映射到库巴并将熔岩映射到水管的整合游戏概念网络,情理上更说得通一些。
  • 整合游戏的可玩性(Playability):如果地图上的一个可通过的地块被映射到了一个不可通过的地块,导致生成的关卡甚至都不可能玩到最后,那这样的整合游戏概念网络显然也是不可取的。
  • 整合关卡的趣味程度、挑战性和美观程度:通过借助深度神经网络,优化目标甚至可以是这样一些具有主观性的量度。如果能够事先在大量已有的游戏关卡和人们对这些关卡的趣味程度/挑战性/美观程度的量化评价所构成的数据集上训练出预测人们对未知关卡的这些方面的评价的神经网络,这个神经网络就能作为一个自动化代理(Surrogate Model)来给出人们对新关卡的评价的(的一个估计值),从而成为一个可计算的优化目标。
  • 整合关卡的新颖性:在计算创意学的第四章中,我们介绍了一种基于概率期望的“新颖性”概念的可计算的定义。因此理论上说,我们也能够通过这种方法计算出生成的新关卡的新颖程度,将这个新颖程度作为优化目标。

深度神经网络和组合式游戏生成

Guzdial和Riedl的两篇论文,人为设计了一套用于表示游戏关卡结构的概念网络语言(Schema)。这将对关卡结构的表达能力限制在了这套概念网络语言所能表达的范围内。如果游戏对象之间的关联非常复杂,无法用这样的网络结构来描述,那它也就不能反映在生成的游戏关卡中。

为解决这个问题,人们自然想到了深度神经网络及其所擅长的特征学习(这方面的具体解释请见计算创意学第三章中关于Deep Dream和Neual Style Transfer的介绍)。2020年由学者Sarkar等人发表的论文《用变分自动编码器来实现可控的游戏关卡混合(Controllable Level Blending between Games using Variational Autoencoder)》就尝试了一种叫做变分自动编码器(Variational Autoencoder)的深度神经网络架构来实现混合现有的游戏关卡来生成新关卡。

自动编码器(Autoencoder)是一种深度神经网络架构,它的本质是将输入数据(需要很大的数据量来描述)映射到一个低维的向量空间,在其中能够用较小的数据量来描述同样的信息(也就是压缩编码)。比如说,以图像这种输入数据为例,图像本身最原始的形式需要定义清楚每一个像素点的RGBA值,这样一个输入图像的数据表示就要包含图像的像素点总数乘以RGBA四个数值这么多的数据,通过使用自动编码器,我们可以使用一个数据量远小于这么多的向量来表示同样的图像。

传统的压缩算法会引入一个显式的“字典”概念,通过这个字典将较长的数据组合用较短的数据组合来替代,从而实现压缩。而基于神经网络的自动编码器是基于训练过程中自动发现的统计规律来“降维”,从而实现压缩的。

一幅原始的图像因为需要大量数据来描述,处于一个高维的空间,但是因为训练数据集中的图像不可能覆盖所有可能的像素值的所有可能的组合——实际上在所有可能的像素值的所有可能的组合所组成的巨大搜索空间中,训练数据集中的图像只覆盖了寥寥数个位置——因此,虽然原始图像处于一个高维空间,但是这个高维空间是非常稀疏(Sparse)的。

这就意味着完全有可能找到一个更加低维的空间,这个空间比起原始高维空间来小得多,但仍然具有足够的表达能力来区分训练数据集中所有的图像。

自动编码器就是自动寻找这样的低维空间的神经网络算法,它在训练和使用过程中还需要搭配自动解码器,通过优化神经网络参数,最小化编解码之后得到的图像和原始图像之间的差别,来实现自动编码器和解码器的训练。

自动编码器图解(图片来自网络,侵删)

读过计算创意学系列的读者可能会意识到,这个构建低维空间的意义实际上远不仅仅只是压缩——它还构建了一个概念空间。这个概念空间中包含了考虑范围内的那些图像可能具有的特征。

那么通过在这个概念空间中有目的地搜索,我们还能生成具有我们想要的特征的、训练数据集中没有的图像。除此之外,我们还可以将两幅图像用自动编码器各自映射到同一个概念空间,得到它们各自的特征,再融合它们的特征,用解码器得到一个融合了两幅图像的新图像。我们甚至可以通过控制两幅输入图像各自保留哪些特征来控制最后得到的新图像。

这里介绍的这篇2020年的论文,以及作者的几篇相同主题的后续论文([4], [5]),就通过这个原理来完成了游戏关卡的融合。作者将我们上面所讨论的例子中的“图像”换成了“游戏关卡”,利用一种可解释性较强、更可控的自动编码器——变分自动编码器(Variational Autocoder)——将两个游戏关卡各自映射到一个相同的低维“概念”空间,从而完成关卡的融合。

一个融合了塞尔达、银河城和洛克人的游戏关卡

这篇文章中,我们讨论了组合性创造力理论、特别是概念整合理论在自动化游戏生成中的应用。我们介绍的几篇论文,其共同特点是都在游戏的“表象”背后建立起了一个能够用统计机器学习的方法自动去发现的“特征表示体系”。Guzdial和Riedl的论文中,这个特征表示体系是手动设计的概念网络,而Sarkar等人的论文中,这个特征表示体系是深度神经网络自动构建的低维空间。

关注AI前沿的小伙伴可能了解,随着AI技术的发展,图像编辑工具中出现了大量非传统的“语义(Semantics)编辑”工具,比如Adobe推出的神经滤镜(Neural Filter)和NVIDIA推出的EditGAN。相较于传统的图像编辑往往都是直接在图像本身数据层面上进行操作,这些AI编辑工具实际上是在一个图像背后的特征空间中进行编辑,再映射回到图像本身的数据上。因为这些工具的存在,在语义层面上融合多幅图像也成为很容易的事。

Photoshop中的Perspective Wrap工具能够改变2D图像的视角
NVIDIA的EditGAN能够对图像进行各种各样的“语义编辑”(针对图像所描绘的内容,而不在像素点层面的编辑)

而这些基于特征空间的游戏自动生成技术,虽然现在还很不成熟,也让我们也不由地思考,或许不久的将来,游戏开发设计工具也能“语义化”——我们能够不仅仅在游戏的代码和具体素材本身的层面进行操作,也能在游戏背后的抽象特征空间上操作。

就像Adobe的智能照片滤镜能一键改变拍摄角度,EditGAN能一键将照片中的宝马车变成丰田车,说不定未来在某个游戏引擎中,我们也能一键将一个回合制策略游戏变成动作格斗游戏呢。

注:标题图来自游戏:SuperMash (SuperMash on Steam (steampowered.com))。这个游戏中你能体验到各种游戏类型的混搭会出现什么效果,很推荐!

参考文献

[1] Guzdial, M., & Riedl, M. (2016). Learning to blend computer game levels. arXiv preprint arXiv:1603.02738.

[2] Guzdial, M., & Riedl, M. (2018, September). Automated game design via conceptual expansion. In Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment (Vol. 14, No. 1, pp. 31-37).

[3] Sarkar, A., Yang, Z., & Cooper, S. (2020). Controllable level blending between games using variational autoencoders. arXiv preprint arXiv:2002.11869.

[4] Sarkar, A., & Cooper, S. (2021, August). Generating and blending game levels via quality-diversity in the latent space of a variational autoencoder. In The 16th International Conference on the Foundations of Digital Games (FDG) 2021 (pp. 1-11).

[5] Sarkar, A., & Cooper, S. (2021, August). Dungeon and Platformer Level Blending and Generation using Conditional VAEs. In 2021 IEEE Conference on Games (CoG) (pp. 1-8). IEEE.