[本篇全文] [回复本文] [本篇作者: etone] [本篇人气: 342]
发信人: etone (模范未婚夫), 信区: CompSci
标 题: 从博德之门到形式语义
发信站: 小百合BBS (Fri May 13 02:18:46 2005)
为了庆祝本版重新开张，贡献一点原创。另外因为学期已经结束了，也不想说些太严肃的
东西，就谈谈游戏吧。
我玩的最多的游戏就是Baldur's Gate系列，这个游戏应该有不少人听说过，是AD&D规则的
rpg。这个系列诞生至今已超过5年了，相比时下的游戏，技术上已然落后了很多，但仍然
吸引着无数铁杆如我者一玩再玩，的确堪称rpg史上的经典。
但玩的多了，一些歪门邪道就渐渐被人们琢磨出来了，关于这有一篇著名文章叫"The Her
o's Guide to A Successful Adventure"。可以参见：
http://members.chello.nl/~j.vanthull/BG2SR/Stuff/Cheese.htm
这篇文章专门记述了上百个Baldur's Gate的exploit。这个exploit顾名思义就是对游戏引
擎或游戏规则的盘剥，专门有一个词形容这个叫cheesy，就是指不要脸的打法。这个chee
se不同于cheat，并不是对游戏规则的违反，而是在体制内通过一些意想不到的方式来达到
利益最大化。平心而论Baldur's Gate从引擎到规则都已经做得相当不错了，在平衡性方面
放在今天也绝对是游戏的楷模，但由于游戏setting的庞大，仍免不了被勇于探索的玩家们
捅出许多漏洞，由此可见人类在大工程面前的无助。
今天要讨论的是利用computer science的一些理论来研究怎样可以避免这些chees，让机器
代替最终玩家来扮演adversary的角色，或者干脆从根本上保证杜绝cheese的出现。
Hero's Guide里面的提到的cheese，大致可分为两类。一类就是单纯的语义bug，只不过这
里违反的不是program的逻辑，而是游戏逻辑。一个例子就是Baldur's Gate的战士类角色
可以选择guard别人，让战士拿弓箭guard另一个人，再让那个人冲进敌人房间然后关上门
，你就可以看到，战士的箭穿过门射击敌人。诸如此类的还有伪谈话和potionswap等tric
k。另一类cheese就不再是语义bug了，因为把它放在游戏规则里也未尝不可，也说不上它
就一定违背了游戏逻辑，但它的存在却会破坏游戏的平衡。这样的例子多见于一些魔法的
组合，原来为了平衡而给不同魔法加上的限制在组合之后就不在有效了。例如globe of b
lades可以让人周围被剑气包围，打架时靠近的敌人会受到伤害，而sanctuary可以让敌人
只要你不打他就不打你，但如果两个魔法都施了之后，只要站到敌人身边，就见他乖乖不
动直到被剑气弄死。这样的法术不能说就不符合游戏逻辑，但它的存在实在是很赖皮，破
坏了游戏的平衡。
对于第一类bug，可以使用形式语义中针对语义bug采取的种种办法。但由于游戏在软件结
构和程序逻辑方面的独特性，直接应用传统的方法往往并不合适。我本人对语义所知甚少
。因此这里也就是胡乱说说，希望专业人士能够出来指正，我也很想就这个问题讨论讨论
，了解一下真正搞PL的人采用的方式。
第一个办法就是指哪打哪，给一个property然后做proof。一般这个property都是针对一类
具体的bug例如overflow,memleak之类，然后找到一个proof可以证明这段代码没问题。但
这个方法很难满足游戏设计的需求，因为计算机程序的逻辑相对而言比较单纯，可以一类
一类bug的枚举。实际中，单单证明一个overflow free就算是杜绝了一大类隐患。但游戏
逻辑可以极其丰富和多样化，虽然往往只是现实的一个抽象，但比起机器的specificatio
n，游戏逻辑要更加接近现实的多，很难通过枚举的方式来总结good/bad behavior。
第二个办法就是画地为牢，既然无法单挑掉所有的狼，咱们就圈个羊圈，牺牲一点一般性
，换来不用proof的安全性。这个就类似type theory搞的，在设计PL之前先设计type sys
tem，然后好的语言也就水到渠成了，写出来的全是好程序。这当然是比较理想的情况了。
对于游戏而言，这个方法的问题在于：游戏系统中找不到属于这个语言的位置。目前的游
戏开发（特指rpg的开发），一般是分为engine,script和data，放下数据不说。引擎和脚
本各司其职，谁也不适合作成支持游戏逻辑的type system。目前的引擎一般是把声音图像
的驱动，数据的parse和游戏逻辑的实现一包揽，还要顺便搞一个脚本语言解释器，由于要
实现底层的声音图像，因此都是用通用的计算机高级语言实现，一般视programmer爱好而
定，大部分是c/c++，间或也有用lisp和ocaml的。因此游戏逻辑的实现往往和这些东西搅
和在一起，没有办法使用专门设计的type system。而脚本部分往往是文案人员写就，因此
要使用接近自然语言的脚本语言。让他们用受诸多限制的为游戏定制的language也不现实
。因此我觉得现在的游戏软件体系还是有问题。至少应该再分出一层来。除了一开始上帝
说“要有光”于是就有了光之外，上帝还要拿出一天来规定秩序，之后才是在这个舞台上
彩排节目。因此engine的用处应该是底层物理条件的支持，另外还要实现一个为不会破坏
游戏逻辑而专门设计的语言，然后由这个语言来实现游戏世界，最上层才是在这个世界中
发展的剧情。至此都是从软件工程的角度考虑。而具体该怎样去设计这个专门为游戏逻辑
而设计的语言，靠诸多限制来谋求安全性的type theory究竟是否强大到足以支持丰富而多
样话的虚拟世界的逻辑，是否type theory先天的局限性限制了它只能胜任机器的逻辑，抽
象的计算机器和演算的计算与表达能力与这个世界之间究竟有没有根本的差距，这就是la
nguage和theory要考虑的事情了。
第三个防cheese的办法是一个美好的愿望。如果人们可以亲自给出整个游戏逻辑的specif
ication，然后让机器verify游戏的代码有没有违背它，那这个问题也就解决了。但这个方
法做了太多的假设，把整个model描述出来，这在工程上就是non-trivial的，而且就算描
述出来了，谁又来verify这个描述是不是有问题，就算这个描述没问题，机器有没有能力
去做这样一个判定。但是讨论一下不同条件下这个verification过程的可计算性和计算复
杂性的确是一个有趣的理论问题。
单就一个语义bug就说了这许多，下面来谈谈第二类cheese，也就是体制内破坏游戏平衡的
元素。
这个问题比语义bug要复杂，相比于语义bug这种遇见就可以枪毙的大是大非的问题，游戏
平衡的定义就成问题。而且游戏逻辑是个definition，可以由设计者任意规定，但游戏的
平衡性却是游戏的一个客观属性，需要人们去判定的。因此在这个问题上可做的文章也要
多一点。
首先就是平衡性的定义。单纯这么提出来，似乎人人都觉得平衡与否只是一个人的感觉而
已，是无法量化的。但如果把游戏的model剥离出来，就会觉得这个问题还是有讨论余地的
。这里我们先把问题单纯化一点，影响游戏平衡性的因素，这里我们就只考虑游戏的规则
。因此由AI等因素例如糟糕的寻路能力引起的对平衡性的破坏暂且忽略。因此所有的电脑
上的AD&D rpg就都成了类似magic: the gathering一类的筛子纸牌游戏。而把游戏的规则
抽象并generalize之后，其实就是game，这里的game是指game theory里面定义的一个数学
结构。而平衡性就是防止“一招鲜，吃遍天”的情况，例如猜拳是平衡的，tic-tac-toe是
不平衡的，因为先手有必胜策略，没有禁手的五子棋也是不平衡的。利用game theory中对
game的种种characterization，其实不难给出平衡性的定义。
因此接下来的一个问题就是，有了一个game，如何去判定它的平衡性。这个问题让人联想
起去年STOC的一篇paper: The Complexity of Pure Nash Equilibria。在篇paper讨论的
是，给出一个game的简短描述，计算它的纯纳什均衡，这个问题的复杂度。作者Papadimi
triou自称这是史上第二烦琐的归约（第一是Probabilistic Checkable Proof）。类似的
对于游戏平衡性，也有相对应的理论问题。但可能从computation的角度要比Pure Nash E
quilibria难，因为game balance与否关系到整个状态空间的分布，而game的action spac
e可以呈game描述长度的指数级，直觉上就不像是会有一个polynomially checkable proo
f，因此可能连NP都不是。好在人们对此也只要个近似。通过在action space里面进行ran
dom walk，可以从stationary状态中估计个大概，但mixing time仍然是个问题。
即便成功的判定了game的平衡性，发现有不平衡，对游戏规则的修改也并非trivial的。目
前游戏设计者采用的都是启发式的办法，通过玩家的反馈，启发式的修改游戏规则，例如
Blizzard对星际争霸的支持，但这种方法的收敛性仍值得怀疑。并不能保证收敛的，也有
补丁打过反倒更不平衡的。因此有个问题就是，是否存在一劳永逸的解决办法。设计游戏
时就可以肯定它是平衡的，换句话说这叫游戏设计的原则，再换句话说这叫game balance
的充分条件。这就已经是一个纯数学问题了。Trivial的条件有很多，non-trivial的我还
不知道，我对game theory也不是很了解，不知有没有现成的结果可用。
有句话叫：酒肉穿肠过，佛在我心中。其实打游戏也是可以打出计算机科学的。
[返回] 中文XML论坛 - 专业的XML技术讨论区 →
计算机理论与工程 → 『 理论计算机科学 』 → [转帖]从博德之门到形式语义
(订阅本版)
2005/5/16 21:01:00
顶端 
[转帖]从博德之门到形式语义(7264字) － eyounx，2005年5月16日
新浪微博
