Battleship: Examining Edge and Adjacency Ship Placements and Target Selections

Battleship is a classic guessing board game for two players. Initially, each player is given a certain number of ships, each of a specific size, to place on their grid. Next, the players take turns guessing shots at the other player’s grid with the intention to hit and sink their opponent’s ships. The first player to sink all the ships of the other player wins. This project analyzed strategies for ship placement and shot targeting, specifically exploring the balance between avoiding placing ships on the edges of the board or adjacent to each other vs. having the opponent target spaces that are not on the edge or adjacent to another ship. The rationale is that placing ships along the edge or next to each other would make it easier for the opponent to sink the ship after an initial hit is discovered. However, if the opponent knows that ships tend to not be placed along the edges or next to each other, they reduce their search space accordingly, thus making it harder to sink ships that actually lie on the edge or are adjacent to each other. This balance is investigated through Battleship games that are played out between a ship placement agent and a shot targeting agent. The placement agent rejects edge and adjacent ship placements with varying probabilities, while the targeting agent rejects shot positions that lie along edges and next to sunken ships with varying probabilities. A mixed-strategy Nash equilibrium was found such that the placement agent would randomly place their ships 98% of the time, but for the other 2%, completely reject random placements that are along the edge or adjacent to another ship. The selection agent would completely reject random shots on the edge or adjacent to a sunken ship 57% of the time, but for the other 43%, would only reject with a 0.75 probability. The balance holds asymmetrically for the two agents in this equilibrium: while the placement agent would favor randomness in its placements, the targeting agent would want to be more deliberate in its shots.