登陆后访问



H
I
S
T
O
R
Y

数学模型教你如何成为星际争霸高手·上篇——确定性模型

摘要:本文中,作者用确定性模型告诉大家星际争霸高手的修炼途径。
一、背景介绍
星际争霸是暴雪公司的经典作品,它的故事发生于26世纪,主要讲述了银河系边缘三个种族:虫族(Zerg)、人族(Terran)和神族(Protoss)(还有一个极其神秘的种族叫Xel'Naga,虫族和神族都是由这个种族创造出来的,不过这属于星际争霸2的故事,本文不涉及)之间明争暗斗,争夺霸权的故事。在游戏中,玩家可以选择操控这三个种族之一,并创建一支军队打败对手或完成指定任务。每个种族都有自己的特点,却又很好地保持了游戏的平衡性,这是星际争霸能成为经典的原因之一。在本章中,我们用U(t)来表示玩家的部队总数(U是依赖于时间t的函数)。
二、兵工厂数量与多线程并行(Multithreading)
星际争霸的上手难度较高。新手玩家通常把大量的注意力放在华丽的战争场面,或对单个单位的操控上,而忽视了建立军队的过程和资源的采集,比如在不知不觉中,你的资源已经达到了这个数字:

图1
妥妥的万元户!然而总军力只有44个人口,远远不到200的人口上限。可见,这时大部分操作都是浪费了的。很多新手从头到尾只会建造一个兵工厂,因此部队的生产过程是单线程的,而不是多线程并行(多个兵工厂同时生产部队)的。下图大致表明了多个兵工厂和单个兵工厂在相同U值(生产部队总数量,用横轴表示,横轴的数字只起到参照物的作用,并不代表真正的U值)下的效率(纵轴)对比。注意,U较小时,多个兵工厂和单个兵工厂效率差异并不大,但它们的效率都是呈对数(回忆一下log函数的图像)增长的;随着U的增大,所有兵工厂逐渐处于饱和状态,故生产效率不再随着U的增加而增加。

图2
所以在职业对战中,我们可以看到双方几乎都建有大量兵工厂。

图3
三、高手的单机策略——逻辑增长模型(Logistic Model)
高手和新手最大的区别在于,他们更加善于整体地看待这个游戏,因而把整个游戏的节奏;例如在什么时候建造新的兵工厂,什么时候开采新的资源,都有整体的规划。尽管每个高手都有自己的作战风格(这在数学上可以用随机项或误差项来表示,用以描述个体差异),但这种整体性的节奏(可以用趋势项来表示,用以描述整体形势)却是惊人的相似。
如果我们先暂时忽略掉个体差异(随机项),可以想象,U(t)(部队总数)其实就是生态学中单一种群的人口数(Population),而单一种群的总数满足以下微分方程:

在星际争霸中,我们只需考虑部队的出生率(生产率)和死亡率(死于电脑之手)。在单机情形下,电脑以固定的频率对玩家发动攻击,因而玩家部队的死亡率可近似看做种群的自然死亡。在1836年,比利时数学家P.Verhulst提出了单一种群的逻辑增长模型:

这个方程解的图像是这样的:

图4
可以看出,常数K起到的作用是限制部队总量。这个常数由人口上限、资源总量(图1所标示的3个参数)和电脑对玩家的攻击频率共同决定。
值得一提的是,在以上方程(图5)后面再加一项,便得到了1978年加拿大数学家Ludwig等人提出的食心虫爆发模型(Spruce Budworm Outbreak Model,食心虫是一种害虫),用以解释这种虫灾爆发的原因。后面加的那一项描述害虫的非自然死亡,例如被鸟吃,被杀虫剂杀死等。这个模型也可以描述蝗虫灾害。虫灾固然爆发迅速,但通常不会大面积扩张,这个可以用另一个模型——多孔介质力学方程(Porous Media Equation)来解释,不过这不在本文探讨范围之内,有兴趣的读者可自行查询。
高手玩家在快速增长区域中,U(t)(部队总数)增长迅速,这个现象会在第二章继续提及,请各位读者注意这一点。
四、新手常犯错误——神经元脉冲模型
和高手相比,新手的U(t)不会像图六那样满足逻辑增长模型,因为新手不仅只会建造一个兵工厂,而且只会在某些特定时刻生产部队。例如突然看到自己的基地被攻击,猛地想起基地里没有太多防守的部队,自己的先头部队已经长征到民风淳朴的偏远山区去了,怎么办啊怎么办!游戏不是电影,天降奇兵是不可能的,于是手忙脚乱地压榨那唯一的兵工厂,疯狂生产部队。如此,新手们的U(t)图像大致是这样的:

图5
显然图7和图5的稳定增长模式有本质性的差异。满足图7的方程被称作踢足球(kick)模型,用方程表示为:

图6
注意这是一个迟滞微分方程。这个模型还可以用来描述单个神经元的电信号脉冲:

图7
五、单机作战小结
在和电脑的对战中,要想从新手蜕变成为高手,除了要多加练习以外,更应该注意的是高手的大局观——他们的U(t)是符合逻辑增长模型的。有意识地把神经脉冲模型转化为逻辑增长模型,有助于单机技术的提高。
光说无用,经过练习,小编已经可以轻易打爆电脑啦!为了更加符合逻辑模型,小编特意用了单兵种推进打发(虫族的多头怪,可以远程攻击,攻击效率非常高,价廉物美)。前文提到过,逻辑模型中的K由资源和人口共同决定,如果你的资源一直保持在较低水平(资源极大化利用)并且人口上限一直为200,那么恭喜你,你的战术是符合逻辑模型的。

图8
六、高手间的较量—— 双种群竞争模型(Lotka-Volterra Competition Model)
也许仍然有读者比较怀疑第三节中的逻辑模型是否真的适用于星际争霸,那么下面的分析将解除你的怀疑。
观赏过星际争霸职业比赛以后,读者可以发现一个现象:比赛开始前10分钟,对战双方的发展进度都比较缓慢,多数精彩场面都来自于农民(最基本的部队,用以建造各类建筑和采集资源,几乎没有攻击性)间的相互限制(如下图)。

图9
这看起来很无聊。但游戏进行到10分钟以后,画风一瞬间变成了这样:

图10
真是精彩!只可惜双方兵力都几乎消耗殆尽了,有些意犹未尽,不用着急,仅仅一分钟后:

图11
细心的读者可能意识到,大战之所以能发生地如此频繁,是因为对战双方都处于逻辑模型(图6)中的快速增长区域。
但是双人对战和单机情况是有区别的!因为对战中,双方的策略是会随时发生变化的。如果我们用U(t)表示玩家A的部队总数,V(t)表示玩家B的部队总数,那么能不能再逻辑模型的基础上做一些修改,而得到一个更符合实际的模型呢?这就是Lotka-Volterra双种群竞争模型。

这样一来,除了两个r(出生率常数)和两个K(限制常数),又多出来两个b,这也为模型的参数估计(Parameter Estimation)带来了不小的麻烦。参数估计又称为反问题(Inverse Problem),相当于已知方程的解,反过来确定方程中的各个参数。在自然科学领域中,反问题无处不在,甚至比建模本身更为复杂。反问题通常的解决方法需要利用统计学中的参数回归、非参数回归和似然估计等各种指导思想以及梯度算法、自助(Bootstrap)和交叉验证(Cross Validation)等各种具体技巧,这个话题小编以后还会提及。
当图14中的各种参数满足一定条件时,U和V的图像会呈现出稳定的周期性表现,如下图:

图12
图中每一个环路H都对应一个周期解,表示U和V之间此消彼长,相爱相杀的暧昧关系;这种暧昧的关系正好描述了本节开始时双方拉锯战的现象。而在数学中上图15中的环路被称作极限环(Limit Cycle),在常微分方程专家的眼中,寻找极限环甚至比寻找方程的具体解更为重要,究其根底,是源于自然界中无处不在的周期性。熟悉分歧理论(Bifurcation Theory)的读者可以看出,图15中的极限环是由霍普夫分歧(Hopf Bifurcation)产生的。
七、确定性模型的局限
至此,本文至始至终讨论的都在讨论确定性模型(Deterministic Model)——因为微分方程建立以后,它的解是可以被估计出来的。读者可以从上面的分析可以看出,相对简单的确定性模型就可以粗略地解释极为复杂的现象。但简单的模型只是对具体问题的简易化处理,那么如何建立更为贴切的数学模型?这既是数学建模的魅力,也是它所面临的挑战。
那么星际争霸游戏中还有哪些未考虑的因素呢?太多了,但主要体现4点:动态策略、微操、游戏环境(地形、路面宽度、陆战和空战等)和兵种特色(相克、视野、射程、攻击间隔、技能释放等)。为节省篇幅,下面只讨论动态策略和微操。
1. 动态策略
所谓动态策略,是指对战双方的作战策略会随着游戏进度的变化而变化。这样Lotka-Volterra双种群竞争模型就变成了:

和图14的差别在于,所有的参数都会随着时间而变化。可以想象,改良后的双种群竞争模型可以产生更加丰富的结果,但模型的分析难度也随之上升。值得一提的是,双方的科技状况也能使参数发生变化,而且这种变化是不连续的(例如玩家A完成某项升级以后,其部队的作战能力能产生质的飞跃)。
2. 微操
新手玩家最容易被各种赏心悦目的微操(Micro,就是指对少数几个兵种的具体操控)所吸引。尽管更多决定游戏走向的是整体战略,但有时犀利的微操能起到扭转战局的作用,比如:

图13:甩飞龙

图14:黑暗圣堂武士砍地雷
还有最令人叹为观止的陆战队员(最低成本的人族单位)无伤击杀潜伏者(高成本、高科技含量的虫族单位)

图15
其之所以叹为观止,有3个原因:1) 三个陆战队员竟然在同一时刻朝不同方向移动;2) 每一次移动都恰好避开了潜伏者的攻击;3) 三个陆战队员每一次移动都恰好能对潜伏者发动一次攻击。那么这种操作是如何做到的呢?无他,唯手熟尔。有兴趣的读者可以从农民绕基地移动开始练习,原理是一样的。

图16
抛开操作层面不谈,可不可以建立数学模型来描述这些精妙的微操过程呢?答案是肯定的,但没有必要,主要原因在于微操的情景实在太多,具体情况需要具体分析。所以数学家们通常直接把这些复杂的个体差异直接看作随机项(或误差项)。尽管个体差异并不一定是随机的,但用随机模型去处理,通常能达到良好的模拟效果。这就是为什么随机模型能在金融领域、控制论和运筹学中运用广泛的原因。

 

声明:文章转自【京师数科】微信公众号,版权归原作者所有,转载仅供学习使用,不用于任何商业用途,如有侵权请联系删除,谢谢。

相关文章

奇妙的数字:巧合数

Posted by - November 10, 2017 1592
世界上,无时无刻不在发生着一些看似偶然的巧合,有让人遗憾的,也有让人庆幸的,在数学上,也有很多的巧合。

数学之美|填色游戏

Posted by - November 09, 2017 1844
人们提起数学之“美”时常意指其抽象涵义,罗素称之为“朴素冷峻之美……庄严纯净,能够达到严格的完美”。然而,人类也一向从数学中发现审美上的...