Introduction to the Prisoners Versus Guards Game

zbMATH Open1167.91005arXiv0801.0833MaRDI QIDQ3637652FDOQ3637652

Authors: Timothy Howard, Eugen J. Ionascu, David E. Woolbright 

Publication date: 13 July 2009

Abstract: We introduce a two-player game in which one and his/her opponent attempt to pack as many ``prisoners as possible on the squares of an n-by-n checkerboard; each prisoner has to be ``protected by at least as many guards as the number of the other prisoners adjacent. Initially, the board is covered entirely with guards. The players take turns adjusting the board configuration using one of the following rules in each turn: I. Replace one guard with a prisoner of the player's color. II. Replace one prisoner of either color with a guard and replace two other guards with prisoners of the player's color. We analyze winning strategies for small n (n<5) and the maximum number of prisoners in general. We show that this maximum is less than (7n^2+4n)/11 and conjecture it is more likely 3n^2/5+O(n).

Full work available at URL: https://arxiv.org/abs/0801.0833

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Prisoners and guards on rectangular boards
• King independence on triangle boards
• On optimal strategies for a hat game on graphs
• κ-Dependence and Domination in Kings Graphs
• Cliques and constructors in ``Hats game. I

zbMATH Keywords

upper boundsdomination in graphswinning strategiesmaximal configurations

Mathematics Subject Classification ID

2-person games (91A05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Games involving graphs (91A43) Positional games (pursuit and evasion, etc.) (91A24)

Cited In (1)

• Prisoners and guards on rectangular boards

Uses Software

• OEIS

This page was built for publication: Introduction to the Prisoners Versus Guards Game

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3637652)