My Masters student Fionn Mc Inerney and I introduced a new variant of the game of Cops and Robbers, where the cop has the ability to build “walls” on vertices. In Wall Cops and Robbers, there are two players: a cop and a robber. The game starts with the cop building a “wall” on a vertex which blocks off that vertex so that the robber cannot occupy it. The robber then selects a vertex to occupy. The cop can build a wall on any vertex on his turn except for the vertex that the robber currently occupies. Hence, we may think of the cop as playing off the graph: she can teleport to any vertex when she moves. The robber, however, can only move along an edge to an adjacent vertex each turn (just like in ordinary Cops and Robbers). The robber is also allowed to skip his turn, but to avoid complexities, he may not move back to the vertex he occupied on his previous turn (that is, the robber cannot backtrack).

Our game has similarities to the The Angel Problem was first introduced by John H. Conway. The Angel Problem is a turn-based game played on either an infinite chessboard. The game is played by an Angel and the Devil. The Angel has power k, where k is a positive integer, which allows the Angel to move k spaces in any direction. The Devil has the same power as the cop in Wall Cops and Robbers, except that he eats squares in the Angel Problem while the cop builds walls on vertices. The objective of the game is the Angel trying to elude capture by the Devil on an infinite chessboard, which corresponds to an infinite strong grid (each cell is a 4-clique).

The objective of Wall Cops and Robbers is for the cop is to build walls to block off all adjacent vertices to the robber so that the robber can no longer move on his next turn. The objective of the game for the robber is to evade capture by the cop for as long as possible. The wall capture time of a graph is the least number of moves it takes for the cop to capture the robber on the given graph assuming that the cop and robber have both played their best strategies. Note that Wall Cops and Robbers is equivalent to the Angel problem, where the Angel has power k = 1 (although Angels can backtrack). The wall capture time is a new graph parameter.

Fionn proved some interesting things about the wall capture time of infinite grids. To our surprise, the cop can capture the robber on an infinite Cartesian grid in at most 14 moves. For the infinite strong grid (this is the Angel problem with k=1) and we can show it takes at most 246 moves. We also investigated hexagonal and triangular grids, as well as layered three dimensional grids (see the figure above).

Our paper will be presented at my keynote at the 2nd International Conference on Computational Models, Cyber Security, Computational Intelligence (ICC3) in Coimbatore, India this December.
Anthony Bonato.