  This paper studies two-player zero-sum games played on graphs and makes
contributions toward the following question: given an objective, how much
memory is required to play optimally for that objective? We study regular
objectives, where the goal of one of the two players is that eventually the
sequence of colors along the play belongs to some regular language of finite
words. We obtain different characterizations of the chromatic memory
requirements for such objectives for both players, from which we derive
complexity-theoretic statements: deciding whether there exist small memory
structures sufficient to play optimally is NP-complete for both players. Some
of our characterization results apply to a more general class of objectives:
topologically closed and topologically open sets.
