Cooperating in video games? Impossible! Undecidability of Team Multiplayer Games

作     者：Coulombe, Michael J. Lynch, Jayson 

作者机构：MIT Comp Sci & Artificial Intelligence Lab 32 Vassar St Cambridge MA 02139 USA 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2020年第839卷

页      面：30-40页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Undecidability Games Computational complexity Imperfect information 

摘      要：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 from Hearn and Demaine s Games, Puzzles, and Computation [7], 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. (C) 2020 Published by Elsevier B.V.