The following general variant of deterministic “Hats” game is analyzed. Several sages wearing colored hats occupy the vertices of a graph, the kth sage can have hats of one of h(k) colors. Each sage tries to guess the color of his own hat merely on the basis of observing the hats of his neighbors without exchanging any information. A predetermined guessing strategy is winning if it guarantees at least one correct individual guess for every assignment of colors. For complete graphs and cycles, the problem of describing the function h(k) for which the sages win is solved in the present paper. A “theory of constructors,” i.e., a collection of theorems demonstrating how one can construct new graphs for which the sages win is developed. A new game “Rook check ” equivalent to the Hats game on a 4-cycle is introduced and completely analyzed.