2021/07/30 by Margaret-Ellen Messinger, Messinger, Margaret-Ellen, Spencer Yarnell +1
Computer Science · Social Sciences · #Artificial Intelligence in Games #Combinatorics (math.CO) #Digital Games and Media #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2108.00101
openalex publication_date 2021/07/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the Firefighter problem, a fire breaks out at a vertex of a graph and at each subsequent time step, the firefighter chooses a vertex to protect and then the fire spreads from each burned vertex to every unprotected neighbour. The problem can be thought of as a simplified model for the spread of gossip or disease in a network. We introduce a new two-player variation called the Pyro game, in which at each step, the fire spreads from one burned vertex to all unprotected neighbours of that vertex. The fire is no longer automated and aims to maximize the number of burned vertices. We show, that unlike the Firefighter problem, one firefighter can contain a fire on the Cartesian grid in the Pyro game. We also study both the Pyro Game and the Firefighter Problem on the infinite strong grid and the complexity of the Pyro game.