The true colors of memory: a tour of chromatic-memory strategies in zero-sum games on graphs
Appears in collection : Discrete mathematics and logic : between mathematics and the computer science / Les mathématiques discrètes et la logique: des mathématiques à l'informatique
Two-player turn-based zero-sum games on (finite or infinite) graphs are a central framework in theoretical computer science — notably as a tool for controller synthesis, but also due to their connection with logic and automata theory. A crucial challenge in the field is to understand how complex strategies need to be to play optimally, given a type of game and a winning objective. I will give a tour of recent advances aiming to characterize games where finite-memory strategies suffice (i.e., using a limited amount of information about the past). We mostly focus on so-called chromatic memory, which is limited to using colors — the basic building blocks of objectives — seen along a play to update itself. Chromatic memory has the advantage of being usable in different game graphs, and the corresponding class of strategies turns out to be of great interest to both the practical and the theoretical sides.
