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

简介

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

数据和问题分析

假如在一个冒险游戏中，玩家有一种属性：战斗力。而不同关卡所有敌人都是相同的，只是数量不同。根据前四关玩家的表现：

• 第一关，玩家战斗力为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使



最小。这儿的误差的平方就是二乘方，所以我们寻找的这条直线ax + b = y为最小二乘直线。，而解就是最小二乘解。

最小二乘直线求解

阅读以下内容需要矩阵乘法，转置矩阵以及逆矩阵的知识，这些知识可在任何一本有关线性代数的书上找到。

首先根据b + ax = y来构造矩阵。我们需要求解的方程组为

b + ax1  = y1

b + ax2  = y2

...

b + axn  = yn

我们把这个方程组写为


我们需要求的就是β。对于本文开头提到的冒险游戏例子，就是


对于Xβ = y的最小二乘解，我们可以根据公式



来计算。


方程在坐标轴上图像为：


我们可以证明，这样找到的最小二乘直线，其误差是最小的。当然最小二乘解不只这一种解法。

结语

于是，我们根据第五关玩家获得的战斗力，就粗略计算出玩家根据自己的水平能干掉的敌人，并让系统生成相应数量的敌人。于是，不同水平的玩家就都可以在游戏中自得其乐了。

由于上面的例子中，玩家属性只有一个值，所以求最小二乘解比起其它方法可能稍显麻烦。但当玩家的属性逐渐变多，即未知量不止一个时，例如，玩家战斗力为x，生命值为y，干掉的敌人数为z，那么我们要求解的方程组就变为了

ax1  + by1   + c = z1

ax2  + by2   + c = z2

...

axn  + byn   + c = zn

此时，其它方法就不一定奏效了，而最小二乘解却依然能够快速求出。

作者：clatterrr
来源：露出你的犬牙
原地址：https://clatterrr.com/archives/1729