Finite State Strategies in One Player McNaughton Games

摘要

In this paper we consider a class of infinite one player games played on finite graphs. Our main questions are the following: given a game, how efficient is it to find whether or not the player wins the game? If the player wins the game, then how much memory is needed to win the game? For a number n, what does the underlying graph look like if the player has a winning strategy of memory size n?