Network-Centric Battleship

Alex Gordon led the participants in an exercise to explore how search games played on complex networks are different than search games played on grids. To do this, he developed a complex version of the game Battleship™.

The traditional version of the game Battleship™ is played on four square grids, where two players each have two grids. One of the player’s boards has an arrangement of ships, each containing a number of peg-holes corresponding to the number of “hits” each ship can endure. This board is also used to record attacks by the opponent; attacks occur one grid space at a time. The other board displays attacks on the opponent. Players win by filling an opponent’s peg holes before the opponent fills theirs.

When one of the sides is bombed, there are three different outcomes: miss, hit or a hit that sinks a ship. Each of these outcomes provides different information to the side doing the bombing. Of course, a miss results in a greater chance for a hit on the next move. In addition, if the player is able to strike their opponent’s ship without sinking it, this reveals the (at most) four locations around the hit that will result in more damage to the vessel. This is obviously a linear game that relies on strategies of attrition and exhaustion (attrition and exhaustion both for the information and for the ships themselves).

A complex version of the game can be constructed by re-wiring the boards to make them look more like the internet or other complex networks. The game becomes much more challenging and non-linear, and advantage comes not from exhaustive search, but from a deep understanding of network topologies.

One of the most interesting results is that ships can hide in plain sight in a complex network. In the grid, a hit reveals the four locations where subsequent bombs are most likely to result in another hit (immediately North, South, East and West of the first hit). This means that subsequent bombs have a 25-per cent probability of a hit. Now consider the same ship on a complex grid centered on a hub with 25 connections. In this case, a hit will reveal the locations of only 4-per cent hit probabilities. Depending on the game state, this might result in a player bombing to exhaustion around this hub instead of searching the rest of the network. This result is just one of the counterintuitive outcomes that the players found in Network-Centric Battleship.