使用有效的状态表示方法和搜索算法来识别“Safari激增时段”谜题中的有趣实例

《IEEE Aerospace and Electronic Systems Magazine》：Using Effective State Representations and Search to Identify Interesting Safari Rush Hour Puzzle Instances

　　

摘要：

玩家觉得解谜游戏很有趣，但一旦解决了问题，就没有动力再重新玩一遍。此外，谜题游戏通常具有庞大的搜索空间，完全探索这些空间是不现实的。在这些空间中寻找有趣的谜题实例可以帮助谜题设计者为玩家提供新的挑战，从而保持他们的兴趣。可以采用不同的算法策略，即程序内容生成（Procedural Content Generation，简称PCG），这些策略需要一种表示方法，使算法能够有效地探索游戏的状态空间。本文介绍了几种用于遍历基于组合网格的谜题状态空间的PCG方法，并在Safari Rush Hour游戏中进行了演示。我们引入了一种枚举系统，该系统将状态分组到由整数值表示的簇中，从而便于探索。我们的方法可以并行遍历整个簇，并根据难度或多样性等指标来识别其中的谜题。我们比较了这些方法在探索商业谜题游戏Safari Rush Hour的状态空间方面的有效性，并分析了基于解法长度的被探索簇。结果表明，在簇级别进行搜索可以帮助我们在更短的时间内探索更多的状态，而不会丢失信息。此外，我们还分析了簇的拓扑特征，如大小和谜题部件的数量，这些特征可能会影响解法长度。这些观察结果为基于搜索的程序内容生成在谜题游戏中的应用提供了机会。通过识别和优先处理有潜力的簇，我们可以更高效地获得更好的结果。