论文标题
扫雷器中的相过渡
A Phase Transition in Minesweeper
论文作者
论文摘要
我们研究了经典扫雷游戏的平均案例复杂性，在该游戏中，玩家在二维晶格上推断了矿山的位置。众所周知，玩Minesweeper是Co-NP完整的。我们从经验上表明，扫雷器表现出类似于研究精心卫星相过渡的相变。高于关键的矿山密度，几乎不可能通过逻辑推断玩扫雷器。我们使用降低来使其无法满足地表征扫雷器实例的硬度，并表明硬度在相变的峰值。此外，我们在多项式时间方法的相变时证明了算法屏障。最后，我们评论对相变渐近行为的期望。
We study the average-case complexity of the classic Minesweeper game in which players deduce the locations of mines on a two-dimensional lattice. Playing Minesweeper is known to be co-NP-complete. We show empirically that Minesweeper exhibits a phase transition analogous to the well-studied SAT phase transition. Above the critical mine density it becomes almost impossible to play Minesweeper by logical inference. We use a reduction to Boolean unsatisfiability to characterize the hardness of Minesweeper instances, and show that the hardness peaks at the phase transition. Furthermore, we demonstrate algorithmic barriers at the phase transition for polynomial-time approaches to Minesweeper inference. Finally, we comment on expectations for the asymptotic behavior of the phase transition.
