预测玩家行为动态调整关卡难度——最小二乘问题求解

简介

在游戏开发中,游戏的关卡难度一直是个重要的问题。如果某个关卡难度固定,那么对于新手来说会有些困难,对于熟练的玩家来说又过于简单。但我们如果把它看成最小二乘问题,根据玩家在之前关卡中的表现,预测玩家在之后一关中的表现,就能把此关卡调整到合适的难度。

数据和问题分析

假如在一个冒险游戏中,玩家有一种属性:战斗力。而不同关卡所有敌人都是相同的,只是数量不同。根据前四关玩家的表现:
  • 第一关,玩家战斗力为2,干掉的敌人数目为1
  • 第二关,玩家战斗力为5,干掉的敌人数目为2
  • 第三关,玩家战斗力为7,干掉的敌人数目为3
  • 第四关,玩家战斗力为8,干掉的敌人数目为3
于是绘制得到如下的图:
 
 
我们想知道,在第五关时,假设玩家的战斗力为x,那么玩家能够干掉敌人的数目y是多少。我们想要找出一条近似公式。
根据图中的数据来看,发现它的变化趋势趋近一条直线,因此我们想到选取x的一次表达式ax + b = y来表达。也就是说,我们想要找到适当的a,b使下面的等式都成立。
  • 2a + b – 1 = 0
  • 5a + b – 2 = 0
  • 7a + b – 3 = 0
  • 8a + b – 3 = 0
但找到这样的a,b实际上是不可能的。于是我们想要找到的a,b变为了使上面各式的误差的平方和最小,即找到a,b使
(2a + b - 1 )^2 + (5a + b - 2 )^2 +(7a + b - 3 )^2 +(8a + b - 3)^2 (2a + b – 1 )^2 + (5a + b – 2 )^2 +(7a + b – 3 )^2 +(8a + b – 3)^2
最小。这儿的误差的平方就是二乘方,所以我们寻找的这条直线ax + b = y为最小二乘直线。,而解就是最小二乘解。

最小二乘直线求解

阅读以下内容需要矩阵乘法,转置矩阵以及逆矩阵的知识,这些知识可在任何一本有关线性代数的书上找到。
首先根据b + ax = y来构造矩阵。我们需要求解的方程组为
  • b + ax1 = y1
  • b + ax2 = y2
  • b + axn = yn
我们把这个方程组写为
z1
 
我们需要求的就是β。对于本文开头提到的冒险游戏例子,就是
 
 
对于Xβ = y的最小二乘解,我们可以根据公式
X^TXβ = X^Ty
来计算。
 
 
方程在坐标轴上图像为:
 
 
我们可以证明,这样找到的最小二乘直线,其误差是最小的。当然最小二乘解不只这一种解法。

结语

于是,我们根据第五关玩家获得的战斗力,就粗略计算出玩家根据自己的水平能干掉的敌人,并让系统生成相应数量的敌人。于是,不同水平的玩家就都可以在游戏中自得其乐了。
由于上面的例子中,玩家属性只有一个值,所以求最小二乘解比起其它方法可能稍显麻烦。但当玩家的属性逐渐变多,即未知量不止一个时,例如,玩家战斗力为x,生命值为y,干掉的敌人数为z,那么我们要求解的方程组就变为了
  • ax1 + by1 + c = z1
  • ax2 + by2 + c = z2
  • axn + byn + c = zn
此时,其它方法就不一定奏效了,而最小二乘解却依然能够快速求出。

Leave a Reply