论文标题
对抗对手的记忆有限
Playing Against Opponents With Limited Memory
论文作者
论文摘要
我们研究\ emph {部分信息}当部分信息播放器具有\ emph {有限的内存}时，在具有欧米茄规范目标的图形上，基于欧米茄的两者转弯游戏。当环境玩家对系统播放器并不真正对抗时，这种游戏是反应性合成的自然形式化。环境玩家具有自己的目标，但是系统播放器的确切目标是未知的。我们证明，确定系统播放器获胜策略的存在的问题是PSPACE-HARD，以实现可达到性，安全性和奇偶校验目标。此外，当环境播放器无记忆时，问题是pspace complete。但是，确定环境玩家是否具有胜利策略要简单。它只是NP完整的。此外，我们构建了一个游戏，其中部分信息播放器需要至少$ \ MATHCAL {O}（\ sqrt {n}）$存储器以保留在大小$ \ MATHCAL {O}（O}（O}（n）$的游戏的游戏中）。
We study \emph{partial-information} two-player turn-based games on graphs with omega-regular objectives, when the partial-information player has \emph{limited memory}. Such games are a natural formalization for reactive synthesis when the environment player is not genuinely adversarial to the system player. The environment player has goals of its own, but the exact goal of the environment player is unknown to the system player. We prove that the problem of determining the existence of a winning strategy for the system player is PSPACE-hard for reachability, safety, and parity objectives. Moreover, when the environment player is memoryless, the problem is PSPACE-complete. However, it is simpler to decide if the environment player has a winning strategy; it is only NP-complete. Additionally, we construct a game where the the partial-information player needs at least $\mathcal{O}(\sqrt{n})$ bits of memory to retain winning strategies in a game of size $\mathcal{O}(n)$.
