Cooperating in Video Games? Impossible! Undecidability of Team Multiplayer Games
Coulombe, Michael J., Jayson Lynch · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2018
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 do so, we give a simplification of the Team Computation Game [Hearn and Demaine, 2009] and use that to give an undecidable abstract game on graphs. This graph game framework better captures the geometry and common constraints in many games and is thus a powerful tool for showing their computational complexity.