A Modal Logic for the Hide and Seek Game

Authors: Qian Chen, Dazhu Li, Yaxin Tu, Sujata Ghosh, and Fenrong Liu
To appear in: Graph Games and Logic Design: Recent Developments and Future Directions, Trends in Logic 66, Springer.

Links

• Manuscript PDF: A Modal Logic for the Hide and Seek Game
• Earlier version: Logic of the Hide and Seek Game: Characterization, Axiomatization, Decidability

Abstract

This paper studies the game of hide and seek as a graph game from a modal logic perspective. It proposes a logic for expressing moves and strategies in the game, and shows how adding an equality constant that models the winning condition makes the logic undecidable. The paper compares the expressive power of the proposed logic with standard modal counterparts, gives a characterization theorem for its expressiveness, proves that model checking is P-complete, studies axiomatization, and explores connections with related product logics. Although the logic is designed for a two-player game with a hider and a seeker, the results transfer naturally to settings with more players.