The complexity of Scotland Yard
Merlijn Sevenster · 2006
This paper discusses a case study of the board game of Scotland Yard from a computational perspective. Interestingly, Scotland Yard is a genuine “playgame ” with imperfect information. For reasons not completely clear to me, games with imperfect information have escaped the interest of researchers in Algorithmic combinatorial gametheory. I show by means of a powerset argument, that Scotland Yard can also be considered a game of perfect information, that is surprisingly similar to the original game – up to isomorphism, that is. Using the powerset analysis, I show that Scotland Yard has PSPACEcomplete complexity be it with or without imperfect information. In fact, imperfect information may even simplify matters: if the cops are supposed to be consequently ignorant of Mr. X’s whereabouts throughout the game the complexity is ‘but ’ NP-complete. 1