更好地为解谜游戏划分困难程度

作者：clatterrr
2019-05-31
18 14 0

简介

这篇文章是 Petr Jarusek 和 Radek Pelanek 几篇有关谜题困难程度测量的论文的主要内容。

在这篇文章中，我们主要研究解谜游戏的困难程度划分。是什么让问题变得难以解决？为什么看似相似的两个问题，其困难程度却可能天差地别？我们应该使用怎样的测量方式来测量谜题的难度呢？

使用推箱子游戏收集数据

推箱子，英文名为“sokoban”，是一个规则简单却可以同时拥有很大难度的游戏。为了收集人们玩这款游戏时候的数据，我们使用 Javasripts 写了这样一个游戏，并将它放在网页上供人们游玩。

上图为两个推箱子关卡，分别作为关卡一和关卡二。

在所有 35 个关卡中，都只有 4 个箱子，并且地图大小也很相似。人们在这儿共作了 21511 次尝试，解决了 2071 次问题，能解决第一关的有 294 人，解决至少 20 关的有 35 人，解决全部 35 关的有 6 人。所有人一共花费了 785 个小时。我们不认识参与者，谜题顺序是随机的，解出谜题也不会得到报酬，所以我们收集到的数据都是有一定意义的。

我们在这些数据中发现，对这款游戏来说：

  1. 尽管 73.8% 的走法都会让游戏走入死胡同，不可能再胜利，但人类似乎很快就能发现他们的错误走法，并且重新开始游戏。
  2. 人们通常把时间花在离目标还有很远的时候，当离目标越来越近的时候，他的解决速度也会加快。

X 轴代表的是离目标的距离，而 Y 轴代表的解决问题所花费时间，蓝色的虚线代表第一张图的关卡一，粉红色的虚线代表第二张图的关卡二，红色实线代表所有关卡的中位数。

测量方式一：用电脑模型模仿人类解决问题

我们的目标只是模仿人类的行为，而不是模仿人类在解决问题中认知的发展。

基本原则

我们首先要研究人类解决问题的方式。我们的模型从初始状态开始，行为是以下两种方式的组合：

  • 随机：随机走出一步
  • 最优：走出能使自己离目标更近的一步

人类并不总是随机行动，也不总是最优行动，因此我们想知道该给以上两种行为的权重分别是多少。


模型公式

我们假定当前状态为（S），而下一个可能的状态为（S′），d（S）为目前状态到终点的距离，而 d（S′）为状态（S′）到终点的距离。我们给每一个行为打分，定义向下一个可能的状态行动的分数为 score（S′），使用下面的公式计算：

当不可能到达终点时，分数为 0。否则当下一步会使自己离目标更远时，分数为当前状态离目标的距离，而当下一步会使自己离目标更近时，分数为当前状态离目标距离再加上一个参数 B。假设选择状态（S′）的概率为 P（S′），并使用如下公式计算：

即状态（S′）分数越高，选择其的概率也越大。

有了这样的公式和参数 B，我们可以方便地调整这个模型。B 等于 0 时，模型所代表的人类玩家就在完全随机行走。当 B 越大，相当于这个模型所代表的人类玩家技术更好。


分析

我们用这个方法测试推箱子和另外两个解谜游戏：Rush Hour 和 Replacement puzzle。虽然这三个游戏的规则完全不一样，但我们惊奇地发现，当 B 大约为25时，模型和人类符合地最好。这可是三个完全不一样的游戏啊！这究竟是偶然还是事实呢？

上图左边为人类的行为，而右边为电脑模型解决问题的行为。不同的点代表不同的状态。可以看到模型和人类行为很接近。

测量方式二：问题分解

人类解决问题的另一个重要概念是问题分解。人类不像计算机那样能够系统处理问题（而且他们也不愿意），而更愿意把复杂的问题划分为简单的问题。如果一个问题能够被分解的话，那么困难程度对人类来说也将下降。


如上图，左边的关卡能被容易地分解为两个子问题，解决时间中位数的 3 分钟 02 秒，而右边的难以被分解，只能作为整体解决，解决时间中位数是 53 分 49 秒。

我们使用一种算法来尝试分别模拟人类将推箱子作为整体考虑和分解成子问题考虑时的情形。其结果将在后面给出。

我们也尝试将其分解成三个或更多子问题，但在我们的游戏中，其结果和分解成两个子问题差不多。因此我们不再详细列出。

评估比较

除了上面两种难度测量方式外，我们还引入另外两种测量方式。一是利用计算机算出最短路，即解决谜题需要的最少的步数。二是关卡中的总状态数，即关卡中所有可能出现的不同情况。我们首先为不同的难度测量方法绘制了散点图。

上图中，左上 X 轴为各个关卡离终点需要最少的步数，右上 X 轴为各个关卡的状态数，左下 X 轴为各个关卡可划分为不同简单问题的数量，右下为人类模型行走的步数（B 取值 25），而 Y 轴都是人类解决问题的时间中位数。

图中的 r 为皮尔逊相关系数（ Pearson correlation coefficient ），其用来反映两个变量 X 和 Y 的线性相关程度，r 值介于 -1 到 1 之间，绝对值越大表明相关性越强。可以看到，如上图右上，我们尝试用关卡总状态数来测量难度，但它的 r 的绝对值只有 0.11，统计学意义不大。

为了比较结果，我们除了使用了皮尔逊相关系数，还使用了基于排序的斯皮尔曼相关系数（ Spearman correlation coefficient ）——在困难程度测量的实际应用中，排序往往比绝对的值要好。

在最短路中，除了标准的最短路外，我们还用了一种更符合人类思维方式，但却违反最短路算法的模型。在下面的结果中，绝对值越大，与人类行为符合得越好。其中黑体数据具有统计学意义。


可以看到，在使用计算机算法将其分解成成两个子问题后，斯皮尔曼系数达到了 0.82。这是很好的结果，我们可以近似地认为，计算机使用这种方法解决某个推箱子关卡时，所使用的时间和空间越多，那这个关卡对人类而言也同样的越难。

在我们另一项对数独难度进行划分的研究中，我们使用专门针对数独进行调整的方法，其相关系数能达到 0.95。这证明我们使用计算机划分谜题困难程度的方法是非常有效的。

总结

在这篇文章中我们讨论了给不同关卡划分困难程度的方法。这样我们就能使用计算机预测谜题的难度，并解释为什么它们的难度如此不同。

这些问题和方法在教育学上非常有用——简单的问题让人感到无聊，过分复杂的问题却会令人沮丧，而为不同的学习者找到难度合适他们的问题显得至关重要（这也是 Petr Jarusek 和 Radek Pelanek 这两位大佬研究的问题）。

参考