Battleship is two player guessing game played on a grid. Players secretly place non overlapping ships on their own grid horizontally or vertically. Each ship takes up a certain amount on the grid and the goal is to sink all the enemy ships by taking turns guessing at the locations. If a ship is hit, it is reported and if it is sunk by guessing all points the ship is on it is reported.
Games will be simulated using two different methods, traditional and using a density grid. The traditional method involves randomly guessing at locations and if a hit occurs, the area around it is searched until the ship is sunk. The density grid method uses the remaining ships and knowledge of missed shots to create a density grid of likely places the ships may be. The two methods will be shown and average guesses it takes to win.
To create the game, a grid will be used and populated with five ships. The ships will have a size of 5, 4, 3, 3, and 2 placed randomly on the grid either vertically or horizontally and no overlaps.
The ships will be stored as a data frame:
The grid will be a 10x10 matrix of zeros.
The next step is to populate the grid with the ships. The ships will be looped over and checked if overlaps or out of bounds and if not, place it.
The traditional method of playing is to guess a location and if it is a hit, search around area until ship is sunk. This is repeated until all ships are sunk.
Create random guesses
Guess and Search
The idea here is to continue guessing and searching until there are no more ships left. A guess will be marked with a -1 and ships are marked with values greater than 0, when there is no more values in the grid greater than zero, the ships are all hit and the game is over.
To search would be best done with stack, pushing a hit onto it, pop it off and search around it and add any new hits onto it. This will be mimic’d in R using a recursive function.
Now can combine the search function with guessing, the generated board will be set as a semi global variable using the «- operator.
Simulate a million games and record the number of guesses taken:
The idea of this is to build up a density of where the ships can be and guessing at the highest density places first. When a ship is found, the area around it like before.
Creating Density of Ships
To create this, all possible places where the ships can be located is built up in a matrix. This is done by looping over the grid and checking if there was a miss. This will serve as the density grid.
We need to update ship ids for the density grid so when ships are destroyed the density grid is properly recreated.
Set up density search, this is almost identical to the Guess Search earlier just now creates a density grid to search with:
Set up simulation:
Looking at the histograms:
As expected, randomly guessing at ship locations can be greatly improved with a little math. Not only did it take about 10 fewer turns, the variance has been reduced.
The one section that can be greatly improved is searching around a ship once it is found. The way this was implemented was a very naive way of doing it. In reality, all the points are never guessed and once the way a ship is facing, the guesses are directed in that direction. This could be implemented and should reduce both methods number of turns. As well, the implementation in R is really bad and should of been done in another language for efficiency.