论文标题
火车，游戏和复杂性：通过输入/输出小工具进行0/1/2-player运动计划
Trains, Games, and Complexity: 0/1/2-Player Motion Planning through Input/Output Gadgets
论文作者
论文摘要
我们通过局部“输入/输出”小工具分析了具有单独入口和出口的局部“输入/输出”小工具的计算复杂性，以及从入口到退出的允许遍历的子集，每种遍历都会改变小工具的状态，从而改变允许的遍历。我们在零，一单和两人游戏设置中研究了此类小工具，特别是将过去的运动规划式直通式工作[DGLR18，DHL20]首次延伸到零游戏游戏，通过考虑将每个Gadget的小配件之间的“分支”连接到每个Gadget的Entrance to a Entort of Undrol gadget to a Enture Gadget的Entrance。我们的复杂性结果包括在L，NL，P，NP和PSPACE中的遏制；以及NL，P，NP和Pspace的硬度。我们将这些结果应用于视频游戏因子（序列]和Trainyard的受限版本中的某些机制的PSPACE完整性，从而改善了[ALP18A]的结果。这项工作增强了切换图，到达[DGK+17]和可及性切换游戏[FGMS21]的先前结果。
We analyze the computational complexity of motion planning through local "input/output" gadgets with separate entrances and exits, and a subset of allowed traversals from entrances to exits, each of which changes the state of the gadget and thereby the allowed traversals. We study such gadgets in the zero-, one-, and two-player settings, in particular extending past motion-planning-through-gadgets work [DGLR18, DHL20] to zero-player games for the first time, by considering "branchless" connections between gadgets that route every gadget's exit to a unique gadget's entrance. Our complexity results include containment in L, NL, P, NP, and PSPACE; as well as hardness for NL, P, NP, and PSPACE. We apply these results to show PSPACE-completeness for certain mechanics in the video games Factorio, [the Sequence], and a restricted version of Trainyard, improving the result of [ALP18a]. This work strengthens prior results on switching graphs, ARRIVAL [DGK+17], and reachability switching games [FGMS21].
