半肾
精华
|
战斗力 鹅
|
回帖 0
注册时间 2014-2-27
|
本帖最后由 deadbeef 于 2016-1-4 05:33 编辑
也就是说你实际上是想寻找一个 能让局部最优解 和全局最优解 产生巨大误差的系统喽？
通常来说 局部与全局的差异 一般是来自博弈的不可预知性的
但是并不是说没有博弈就无法构造这样一个系统
那么下面我就举个例子一步一步构造一个能够使局部最优与全局最优产生巨大误差的没有博弈内容的系统
场景就用最单纯的RPG打木桩模式 我方单纯攻击 敌人不会还手 目的就是在一定回合内打出最高输出
目的非常单纯，这里直接以n回合的输出作为评估函数S，描述单回合输出值的函数为D
因为每回合输出值会发生变化才存在策略问题，这里让D成为回合数t的映射，表示为D(t)
用Sigma(i=a, b; F(i))表示对函数F的自变量i在a到b的范围内求和
那么可以得到S函数为
S(n) = Sigma(t=1, n; D(t))
接着我们设计一个最简单的伤害算法，也就是设计函数D
这里直接就用最传统的 玩家攻击力A 与 目标体质值C的差值吧 考虑到A与C的值在一般系统中是相同数量级的 所以这里简单的对A乘上系数2
因为需要玩家来做决策，所以让玩家攻击力A表示玩家使用的技能攻击力，也就是说A值可由玩家选择，也是回合数t的一个映射，表示为A(t)
那么单回合伤害计算函数可以写为
D(t, A) = 2 * A(t) - C
将上述2个函数整合得到
S(n, A) = Sigma(t=1, n; 2 * A(t) - C)
= 2 * Sigma(t=1, n; A(t)) - n * C
接着给这个最简单的游戏规则S来分别计算局部最优解和全局最优解
局部：
对于 S(n, A) = Sigma(t=1, n; D(t, A))
一个非常通用而简单的局部最优解的求法是
A(t) = AMAX(P(S(t, A)))
这里的AMAX表示能让其中的函数达到最大值的A
P表示对当前S(t, A)，以不同的输入A得到的一个预估评分
这里最简单的评分P，就是以S的增量D来表示，也就是最传统的极大似然估计
那么这里的局部最优解就成了
能令D(t, A)最大的A(t)值
在上述最简单的D(t)中，很显然A(t)和D(t)呈1次线性关系，换句话说攻击力A越高， 伤害D越大
所以局部最优解无疑为攻击力最高的那个技能的A值，也就是A的最大值，这里用Ax表示
全局：
这里虽然A(t)并不能用代数表示，但是因为A(t)的最大值是和t无关的常数，很显然Sigma(t=1, n; A(t))的全局最大值就是当A(t)全部为Ax时
于是这个系统的全局最优和局部最优是完全一致的
那么回到一开始的目的 把这个系统修改成一个能让全局和局部产生偏差的系统
由于目的S是非常单纯而直白的，这里就只对每回合伤害D的算法进行修改
首先对于这个系统的要求是：局部最优值要区别于全局最优值
如果说单一回合伤害D(t)中与t相关的部分的取值，仅仅是一个与当前回合玩家决策A(t)有关的函数
那么可以很容易想到，每回合的输出仅受当前玩家决策影响，当前最优的局部解一定也是全局解
所以应该往D(t)的计算中引入玩家决策A(t)的历史成分
这里按照最容易想到的方式，即让前述D的计算公式中，目标体质C为一个受玩家决策A(t)影响的函数C(t,A)
但是考虑到被攻击的目标能够直接受玩家决策影响，确实有点不合理，这里换作让C受每回合被攻击伤害D的影响，即C(t,D)
这里值得一提，想让函数C中包含D的历史成分，最简单的方式是让C成为总伤害S的函数（因为S中包含D的历史成分）
但是注意到一点，这样的话每回合伤害D变成了当前A和当前S的函数
这就意味着对于当前回合来说，如果之前造成的总伤害数值一样，那么D又会变成一个仅与当前A相关的值
根据数学归纳法很容易得到，这种状况局部最优解和全局最优解是一样的，并不是设计这个系统时想要看到的情况
所以这里直接使用伤害D的历史值，而不使用总伤害S的当前值
这里依旧按照最简单的求和思路写C，但是给每一个不同时间的D加入不同的系数K
C(t) = K(1) * D(t-1) + K(2) * D(t-2) + ... + K(t-1) * D(1)
=Sigma(i=0, t-1; K(t-i) * D(i))
这里可以很容易的套入一个现实模型，比如攻击目标受到攻击后，会利用被攻击时的能量来产生一个护盾
而系数向量K就是这个护盾关于时间的衰减，可以简单的写成K(t) = 1/t，即一个倒数衰减
不过这里为了计算更简单，我选择更简单的衰减，即K(1)=1; K(t>1)=0
那么C就退化成一个很简单的状况
C(t) = D(t-1)
即仅以上一回合受到的攻击来生成护盾
接着来调整计算回合伤害的D函数了
为了让D的历史成分对于当前D的影响并不是一个简单的1次线性，这里简单的使用了C的2次项，来给函数引入简单极点
然后需要根据护盾C的值，调整一下A的系数，为了能够更好的表现出局部解与全局解的差别，这里调整系数为1/Ax，式中Ax为A的可选最大值
因此将D写作
D(t) = 1/Ax * A(t) - C(t) ^ 2
= 1/Ax * A(t) - D(t-1) ^ 2
====================================
到这里，这个系统的2个主要函数已经都设计出来了，将整个系统表述如下：
对于以下5元组
{玩家输入的由技能攻击力组成的决策向量A， 连续n回合对目标进行攻击后目标受到的总伤害r，
每回合玩家造成伤害的计算公式D， 所有n回合玩家对目标造成总伤害的评价公式S，
用于计算评价的内部参数向量P（仅包含D的输出值）}
A(t) 属于 [0, Ax]
D(t, A) = 1/Ax * A(t) - D(t-1)^2
S(n, D) = Sigma(t=1, n; D(t))
而对应的背景描述为：
玩家可以使用各种攻击力的技能对一台装配有最新型能量护盾的魔象进行攻击
这台魔象并没有还击能力，但是他的防御系统可以将玩家造成的伤害，转化成能量护盾，来抵挡玩家后续造成的伤害
玩家的目的就是进行攻击，尽快摧毁这台魔象
====================================
到这对上述的系统做一点数值运算，来说明局部最优解与全局最优解在这个系统上的差异
假定玩家能够使用的技能攻击力为0～10,即Ax=10
局部：
对于D，由于上回合伤害D(t-1)为已经发生的即成现实，并不受玩家这回合决策影响
因此无疑，每一回合只要选择最大攻击力10，即为局部最优解
全局：
1回合时，无疑全局和局部是相同的
2回合时，将上述S(n)进行展开
S(2) = 1/10 * A(1) + 1/10 * A(2) - (1/10 * A(1))^2
因为第二回合选择并不影响前2回合总值，A(2) = 10很容易想到
这是个很简单的2次函数，不难求出最大值S(2) = 5/4， 当A(1)=5时
这样2回合的全局最优策略就变成了第一次用5点攻击，第二次用10点攻击
与上述局部最优已经开始产生差距
之后我以脚本跑了下结果，在有限的计算能力内，相差比较大的有6回合时
全局最优策略为 6, 10, 9, 10, 10, 10 最大输出为3.734
此时如果使用全10的局部最优解，最大输出则只能达到3.0
对于回合数较多的情况，想要枚举整个策略向量A求和，这是一个时间复杂度为o(Ax^n)的算法
即为指数时间复杂度，被认为是不可能在有限时间内暴破的
所以这个系统可以认为在回合数n较大的时候，是对暴力求解全局最优解有防御能力的
当然，由于这只是个举例子的系统，很多地方都往尽量简单的地方考虑的
不排除有什么方法能够快速求解全局最优解，或者有什么更好的求解局部最优解然后向全局进行逼近的方法
这个例子只是为了描述一种，能够同时抵御全局求解和简单的局部求解逼近的代数系统
====================================
说了上面那么多，总结一下就是想说
就像我前面说的，我认为游戏设计的目的，从来就不是真实
设计者能够根据自己的目的，来设计出相应的规则
重要的并不是规则的形式（代数还是非代数的），而是设计时的目的本身
就像我上面举例最后得到的规则，仅仅是一个简单的代数运算打木桩的游戏，玩家却没法以一般的经验规律或者简单代数来得到最高输出的策略
这正是因为，我设计这个规则的目的就是为了让他们没办法轻易得到这个策略
而并不是因为我尊重现实，设计规则反应了客观世界的规律之类的无关紧要的事情 |
|
楼主: 傅满洲
沪公网安备 31010702007642号 )
发表于 2016-1-4 02:23
我也想说 这就是mh的思路