The game of Hide and Seek serves as an important paradigm in computer science for studying search problems, and has attractive analogies with logic. This chapter focuses on an imperfect-information version of the game, where, as in realistic pursuit-evasion environments, players have only limited abilities. In the course of the play, they keep changing their positions and reason about each other’s positions based on what they have already known. In this work, we will identify the game design and explore a logical framework, epistemic logic for the hide and seek game (ELHS), to reason about the game. For this purpose, it is crucial to have a formal tool that captures how players update their knowledge, enabling us to characterize key aspects of the game, including the players’ winning positions. By exploring the connections between our logic and other existing logical systems, we show that the ‘static fragment’ of ELHS without the dynamic operators has a decidable satisfiability problem and a P-complete model-checking problem. We finish with a detailed analysis of such games using the logical language.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Knowing is Winning: An Epistemic Approach to the Hide and Seek Game

  • Dazhu Li,
  • Sujata Ghosh,
  • Fenrong Liu

摘要

The game of Hide and Seek serves as an important paradigm in computer science for studying search problems, and has attractive analogies with logic. This chapter focuses on an imperfect-information version of the game, where, as in realistic pursuit-evasion environments, players have only limited abilities. In the course of the play, they keep changing their positions and reason about each other’s positions based on what they have already known. In this work, we will identify the game design and explore a logical framework, epistemic logic for the hide and seek game (ELHS), to reason about the game. For this purpose, it is crucial to have a formal tool that captures how players update their knowledge, enabling us to characterize key aspects of the game, including the players’ winning positions. By exploring the connections between our logic and other existing logical systems, we show that the ‘static fragment’ of ELHS without the dynamic operators has a decidable satisfiability problem and a P-complete model-checking problem. We finish with a detailed analysis of such games using the logical language.