  A major open problem in the area of infinite-duration games is to
characterize winning conditions that are determined in finite-memory
strategies. Infinite-duration games are usually studied over edge-colored
graphs, with winning conditions that are defined in terms of sequences of
colors. In this paper, we investigate a restricted class of finite-memory
strategies called chromatic finite-memory strategies. While general
finite-memory strategies operate with sequences of edges of a game graph,
chromatic finite-memory strategies observe only colors of these edges.
  Recent results in this area show that studying finite-memory determinacy is
more tractable when we restrict ourselves to chromatic strategies. On the other
hand, as was shown by Le Roux (CiE 2020), determinacy in general finite-memory
strategies implies determinacy in chromatic finite-memory strategies.
Unfortunately, this result is quite inefficient in terms of the state
complexity: to replace a winning strategy with few states of general memory, we
might need much more states of chromatic memory. The goal of the present paper
is to find out the exact state complexity of this transformation.
  For every winning condition and for every game graph with $n$ nodes we show
the following: if this game graph has a winning strategy with $q$ states of
general memory, then it also has a winning strategy with $(q + 1)^n$ states of
chromatic memory. We also show that this bound is almost tight. For every $q$
and $n$, we construct a winning condition and a game graph with $n + O(1)$
nodes, where one can win with $q$ states of general memory, but not with $q^n -
1$ states of chromatic memory.
