McConnell & Zhao：用遗传算法实时生成「恰到好处」难度谜题 — Fukai 的读书笔记

一段落概述

我今天选择的，是一篇报告以遗传算法「当场」制作谜题、并针对每位玩家调整难度的尝试的论文。题材是一种与 Cosmic Express 十分相似的、用一笔画运送货物的路径谜题。作者们记录玩家的解题方式（花费时间、重试次数、差一点解出来的次数等），以此确定下一个难度，再用遗传算法（模仿生物进化、逐步探寻优解的方法）以每题约7秒的速度生成符合该难度的谜题。

18人的小规模实验显示，仅以时间为指标的版本明显逊色，使用多项指标的版本在「难度恰到好处」和「有进步感」的评价上更高。这是一篇将实时生成与自适应难度调整直接相连、偏重实现的论文。通过这篇文章，即可了解其制作了什么、如何制作，以及发现了什么。

引言

本论文为 Matthew McConnell 与 Richard Zhao（加拿大卡尔加里大学计算机科学系）合著的「From Frustration to Fun: An Adaptive Problem-Solving Puzzle Game Powered by Genetic Algorithm」。本文出处为2025年9月在 arXiv 上公开的预印本（arXiv:2509.23796）。稿件附有 AAAI（人工智能学会）的版权说明和致匿名审稿人的谢辞，可以理解为已为 AAAI 系发表做准备或已被采用，但我在可确认范围内以 arXiv 版本为出处。

我选择这篇论文，是因为它正好处于 Puzzlebyrinth 所涉及的核心题材之中。路径谜题的自动生成、难度的量化、玩家建模（从游戏记录中推断「这个人目前的水平」）、以及动态难度调整（在游戏过程中上下调整难度的机制，DDA = Dynamic Difficulty Adjustment）。这些都被整合进了一个可以实际游玩的系统，甚至附有算法的伪代码。让制作游戏的人可以直接参考，这种精细程度令我欣喜。

先说一点。这是一篇引用尚少的较新预印本，实验也只是18人参与的先导（预备性）研究。因此可以「证明」的结果并不多。我将原文数值原样引用，并在最后明确区分哪些是可以断言的、哪些是不可以的。

背景

「针对每个人调整难度」这一想法本身并不新颖。无论在游戏还是教育领域，「太简单会无聊，太难会挫败，两者之间是沉浸（心流）」的想法早已被广泛使用。作者们也以一个古典知识点为出发点：个别指导对学习极为有效（Bloom 于1984年指出，接受个别指导的平均学生比普通课堂的平均成绩高出2个标准差）。

那么，缺少了什么呢？据作者们整理，现有的大多数自适应学习系统「离线」运行。即在事后分析数据以备下次使用，而在游戏过程中即时改变内容的系统较少。此外，迄今使用最广泛的适应指标是 time-on-task（任务所花时间），但其单独使用的有效性很少得到验证。

因此，本研究着手于：(1) 制作一个能够与非自适应基准进行比较的实时在线难度调整系统，(2) 将时间这一单一指标单独切出，质疑其有效性本身——这两个方面。生成的核心采用了 PCG（程序化内容生成）的代表性方法——遗传算法。

方案

首先是游戏本身。作者们用 Unity 制作了 APSG（Adaptive Problem-Solving Game）。题材是仿照 Cosmic Express（Hazelden, Davis, Tyu, 2017）的路径谜题。在 n×n 的格子上，从起点到终点画出一条（无分支的）路线。货物容器沿路线每次移动一格，一次只能运输一件货物。在指定装货点拾取货物，在指定卸货点卸下。路线不能交叉，必须考虑顺序才能解开。难度主要由格子大小、装卸货点数量和特殊格子的配置决定。

每次即时制作谜题的是遗传算法。用语言描述其机制如下。首先准备一批谜题候选，分别评分（适应度=fitness），评估其「距目标难度有多近」。选出高分者作为父代，将两者交叉（crossover），再随机变异（mutation）生成子代。反复经历数代后，谜题便向目标难度逐渐靠近。作者们以 Scirea（2020）的 NSFI-2POP 结构为基础框架。

交叉有其巧思。谜题以文字的二维地图（# 空格、X 路线、P 装货、D 卸货、S 起点、E 终点等）表示。随机选取列将两个父代左右切断互换，通常会使路线断裂。于是用 BFS（广度优先搜索，从近处开始依次探索，找出最短连接方式）重新补全路线，装卸货点则按距离重新配置在被路线分割的各区间内。最后一定验证是否可以解开。为了防止生成损坏的解，在流程中内置了修复机制。

适应度随「目标是哪种难度」而变化。作者们为路线长度（8～50）、转角（0～20）、空格数、装货数（1～12）、直交的装货等要素分别设定目标值，根据难度1～10进行插值。评分是对各要素「距目标有多近」进行加权求和（不使用公式，总之是距目标越远扣分越多的形式）。

那么，谁来决定目标难度呢？是玩家模型。系统观察玩家状态，向下一道谜题提出「提高/降低/维持」的建议。依据是解题时间、尝试次数、回溯（消除所画路线一部分重来的次数）、重置次数、差一点（特殊地点漏选不足25%）的险胜次数。有趣的是，将尝试次数作为「硬约束」（必须满足的安全阀，失败多时不提高难度），将其余作为「软约束」加权打分，平滑地决定升降幅度。

实验使用的参数为种群大小300、交叉率80%、最大代数10、最大格子10×10。在此设定下，各难度的谜题均约需7秒生成。增加种群、代数和格子可以制作更大更复杂的谜题，但生成时间也会大幅增加，作者们直率地写道。

发现

实验参与者18人。每人游玩了 APSG 的3个版本：Standard（使用所有玩家模型指标的版本）、Increasing（无论成绩如何都将难度每次提高1的版本）、Time-based（仅以时间为指标的版本）。呈现顺序因人而异，以减少熟悉带来的偏差。总体上反应积极：89%「感到智识上受到刺激」，94.5%「运用了解决问题的能力」，72.2%「需要批判性思维」（均为同意/强烈同意）。

关键比较，以原文数值引用。「减少了挫败感」（1～10，越高越好）：Standard 6.47、Increasing 6.94、Time-based 6.83，方差分析（ANOVA，检验多组平均差异）无显著差异（F(2,51)=0.072, p=0.93）。另一方面，「难度恰到好处」：Standard 6.06、Increasing 5.67、Time-based 4.44，存在差异（p=0.039），Standard 与 Time-based 的差异尤为明显（p=0.004，效应量 Cohen's d=0.869，效应量是差异大小的指标）。

「感到难度有变化」：Standard 8.17、Increasing 7.56、Time-based 6.89（无显著差异，p=0.149）。「有进步感」：Standard 8.56、Increasing 7.5、Time-based 6.0，此处出现了明显差异（p=0.005，Standard 对 Time-based 为 p<0.001，d=1.083）。从日志数据来看，Standard 与 Increasing 的平均难度几乎相同（5.53 与 5.50），而 Time-based 为3.87，比基准平均快25.67秒解出。可以解读为难度没能充分提高。

总结来说，使用多项指标的版本在体感指标上总体更高，仅使用时间的版本显示出「容易停留在简单水平」的弱点。作者们以此为依据，表明今后将以 Standard 型为核心加以完善。但 Standard 与 Increasing 之间的许多差异在统计上并不显著，这一点作者们自身也明确写明了。

应用场景

具体列举对制作游戏和谜题的人的实际用途。首先，如果你正在制作类似 Cosmic Express 或仓库番（Sokoban）系的路径谜题，这篇论文的适应度函数可以直接作为难度旋钮使用。为路线长度、转角、空格数、装货数、直交的装货等「可测量的量」设定目标值，据此进行生成。可以用数字而非语言把握难度，使各难度段的批量制作更加容易。

其次，如果你在构建超休闲游戏的 PCG，「不只依赖时间」的教训会很有用。本论文同时使用了回溯、重置、险胜次数，并实测了仅使用时间版本的弱点。对于容易流失的休闲层，越是用多个行为信号早期检测卡关，越有价值对下一道谜题的难度进行微调。

第三，如果你为生成谜题的「损坏」而烦恼，交叉之后用 BFS 修复路线、最后一定验证是否可以解开的设计可以直接借鉴。不仅限于 GA，不丢弃而是修复合成后损坏的候选这一想法，对制约强的谜题整体都有效。此外作为第四点，正如作者们作为未来应用所举的例子，这还可以延伸到逻辑谜题、算术练习题、面向有学习障碍学习者的练习题的难度调整。游戏之外，教育现场也在射程之内。

局限性

首先是作者们自身承认的弱点。参与者仅18人，结果处于先导阶段。决定性重要的是，没有与完全非自适应版本（静态基准）的比较，没有这个就无法严格说明「减少了多少挫败感」，作者们也写明了这一点。时间指标也只是单独切出来评估，将各指标逐一去除以确定有效指标的消融研究（验证设计哪个部分有效、将要素逐一去除的实验）留待今后的课题。阈值也是按组决定的，个体差异被舍去。

以下是 Fukai 阅读后的发现。第一，约7秒的生成时间如果同步运行，可能会打断节奏。本论文没有将此视为问题，但与商业谜题「爽快地进入下一关」的感觉存在紧张关系。第二，Standard 与 Increasing 之间的许多差异并不显著（18人的检验力不足）。因此「Standard 最佳」是建议而非证明，这是我的解读。

第三，我最在意的是，适应度衡量的是路线长度和转角等「难度的代理指标」，而非人们感受到的认知难度本身。代理指标与体感可能存在偏差。实际上在这个实验中，解题手感与客观难度也不一定成直线关系。最后，题材 Cosmic Express 是商业游戏，「仿照」其进行的再现需要注意权利方面的事宜——这是与论文主张无关的、针对实施者的注意。

Fukai 的解读

这里只写我的解释，先声明这是我的解读。我想将这项研究定位在 PCG 的重心从「尽量多样化制作」向「为眼前一位玩家量身制作」转变的潮流之中。用设计批评的语汇来说，这接近于关卡设计师一直在暗中做的「看清对方、出下一手」这种调整的自动化。有趣的是，这种自动化不是用高级机器学习，而是用枯燥易读的遗传算法和手写约束这类工具来实现的。就可复现性而言，我反而欣赏这种朴素。

结语

为想深入了解的人画一条地图线。本论文的遗传算法以 Scirea（2020）的「面向计算思维的自适应谜题生成」为基础，如果想深挖生成方，先去那里。如果想对 PCG 整体有个概观，Shaker・Togelius・Nelson 的《Procedural Content Generation in Games》是定番。如果对玩家建模和 DDA 感兴趣，从本论文参考文献中的 DDA 综述（Lopes & Lopes, 2022）追踪相关研究的分支，便可看出这一篇处于何种位置。接下来，我自己想找正面测量代理指标与体感偏差的研究来读一读。

再次强调，这是基于18人先导研究的预印本，尚处于未被广泛讨论的阶段。正因如此，我认为它适合作为不急于结论、拿回去思考「什么可以断言、什么不可以」的一篇。今天早上我也手持热的浓绿茶，一边在打印出来的 PDF 上用彩笔划线一边读完了它。

参考文献

・From Frustration to Fun: An Adaptive Problem-Solving Puzzle Game Powered by Genetic Algorithm (McConnell & Zhao, 2025, arXiv preprint 2509.23796)

・同论文 HTML 版（正文・图表・算法伪代码确认）

・关联研究: Scirea, M. (2020) "Adaptive puzzle generation for computational thinking"（本论文遗传算法结构 NSFI-2POP 的基础）

・关联研究: Shaker, Togelius & Nelson (2016) "Procedural Content Generation in Games"（PCG 定番文献）

・关联研究: Lopes & Lopes (2022) "A review of dynamic difficulty adjustment methods for serious games"（DDA 综述）

・题材游戏: Cosmic Express (Hazelden, Davis & Tyu, 2017)