4 papers
Characterizing the Decidability of Finite State Automata Team Games with Communication
Michael Coulombe, Jayson Lynch
In this paper we define a new model of limited communication for multiplayer team games of imperfect information. We prove that the Team DFA Game and Team Formula Game, which have…
The Legend of Zelda: The Complexity of Mechanics
Jeffrey Bosboom, Josh Brunner, Michael Coulombe +4
We analyze some of the many game mechanics available to Link in the classic Legend of Zelda series of video games. In each case, we prove that the generalized game with that mechan…
Tetris is NP-hard even with rows or columns
Sualeh Asif, Michael Coulombe, Erik D. Demaine +4
We prove that the classic falling-block video game Tetris (both survival and board clearing) remains NP-complete even when restricted to 8 columns, or to 4 rows, settling open prob…
Edge Matching with Inequalities, Triangles, Unknown Shape, and Two Players
Jeffrey Bosboom, Charlotte Chen, Lily Chung +12
We analyze the computational complexity of several new variants of edge-matching puzzles. First we analyze inequality (instead of equality) constraints between adjacent tiles, prov…