Introduction to the Prisoners Versus Guards Game
From MaRDI portal
Publication:3637652
zbMATH Open1167.91005arXiv0801.0833MaRDI QIDQ3637652
Timothy Howard, David E. Woolbright, Eugen J. Ionasçu
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.)
2-person games (91A05) Games involving graphs (91A43) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Positional games (pursuit and evasion, etc.) (91A24)
Related Items (1)
Uses Software
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)
