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 the first player is that eventually the sequence of colors along the play belongs to some regular language over 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.
翻译:本文研究了在图表上玩的双玩者零和游戏,并为以下问题作出了贡献:考虑到一个目标,需要多少记忆才能最佳地发挥作用?我们研究了经常目标,第一玩家的目标是,游戏的颜色顺序最终属于某一种普通语言,而不是限定的单词。我们从中获取了对两个玩家的此类目标的彩色记忆要求的不同特征,我们从中得出了复杂的理论说明:决定是否有小的记忆结构足以最佳地发挥功能,对于两个玩家来说,NP是完全的。我们的一些定性结果适用于更一般性的目标类别:从表面学上来说封闭的和从表面学上开放的组合。