A framework for proving the computational intractability of motion planning problems
J Lynch - 2020 - dspace.mit.edu
This thesis develops a framework for proving computational complexity results about motion
planning problems. The model captures reactive environments with local interaction. We …
planning problems. The model captures reactive environments with local interaction. We …
[HTML][HTML] The computational complexity of Angry Birds
The physics-based simulation game Angry Birds has been heavily researched by the AI
community over the past five years, and has been the subject of a popular AI competition …
community over the past five years, and has been the subject of a popular AI competition …
[HTML][HTML] Cooperating in video games? impossible! undecidability of team multiplayer games
MJ Coulombe, J Lynch - Theoretical Computer Science, 2020 - Elsevier
We show the undecidability of whether a team has a forced win in a number of well known
video games including: Team Fortress 2, Super Smash Brothers: Brawl, and Mario Kart. To …
video games including: Team Fortress 2, Super Smash Brothers: Brawl, and Mario Kart. To …
All Paths Lead to Rome
All roads lead to Rome is the core idea of the puzzle game Roma. It is played on an $
n\times n $ grid consisting of quadratic cells. Those cells are grouped into boxes of at most …
n\times n $ grid consisting of quadratic cells. Those cells are grouped into boxes of at most …
ASP-Completeness of Hamiltonicity in Grid Graphs, with Applications to Loop Puzzles
MITH Group, J Brunner, D Hendrickson… - arxiv preprint arxiv …, 2024 - arxiv.org
We prove that Hamiltonicity in maximum-degree-3 grid graphs (directed or undirected) is
ASP-complete, ie, it has a parsimonious reduction from every NP search problem (including …
ASP-complete, ie, it has a parsimonious reduction from every NP search problem (including …
The Legend of Zelda: The complexity of mechanics: Discrete and computational geometry, graphs, and games
J Bosboom, J Brunner, M Coulombe… - Thai Journal of …, 2023 - thaijmath2.in.cmu.ac.th
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 …
Zelda series of video games. In each case, we prove that the generalized game with that …
ASP-Completeness of Hamiltonicity in Grid Graphs, with Applications to Loop Puzzles
J Brunner, L Chung, ED Demaine… - … Conference on Fun …, 2024 - drops.dagstuhl.de
We prove that Hamiltonicity in maximum-degree-3 grid graphs (directed or undirected) is
ASP-complete, ie, it has a parsimonious reduction from every NP search problem (including …
ASP-complete, ie, it has a parsimonious reduction from every NP search problem (including …
Advanced spikes 'n'stuff: an NP-Hard puzzle game in which all tutorials are efficiently solvable
C Ikenmeyer, D Khangure - … on Fun with Algorithms (FUN 2024), 2024 - wrap.warwick.ac.uk
We adjust Alan Hazelden's 2017 polynomial time solvable puzzle game Spikesn'Stuff: We
obtain the NP-complete puzzle game Advanced Spikesn'Stuff with 3 trap types so that each …
obtain the NP-complete puzzle game Advanced Spikesn'Stuff with 3 trap types so that each …
Coordinating" 7 Billion Humans" Is Hard
A Panconesi, PM Posta… - … Conference on Fun with …, 2024 - drops.dagstuhl.de
In the video game" 7 Billion Humans", the player is requested to direct a group of workers to
various destinations by writing a program that is executed simultaneously on each worker …
various destinations by writing a program that is executed simultaneously on each worker …
Baba Is Universal
Z Abel, D Hendrickson - … on Fun with Algorithms (FUN 2024), 2024 - drops.dagstuhl.de
We consider the computational complexity of constant-area levels of games which allow an
unlimited number of objects in a fixed region. We discuss how to prove that such games are …
unlimited number of objects in a fixed region. We discuss how to prove that such games are …