Playing Dominoes Is Hard, Except by Yourself

摘要

Dominoes is a popular and well-known game possibly dating back three millennia. Players are given a set of domino tiles, each with two labeled square faces, and take turns connecting them into a growing chain of dominoes by matching identical faces. We show that single-player dominoes is in P, while multiplayer dominoes is hard: when players cooperate, the game is NP-complete, and when players compete, the game is PSPACE-complete. In addition, we show that these hardness results easily extend to games involving team play.