Introduction
If you read my last game algorithm blog post you’re probably screaming at me “Where’s the rest of the game AI ?!!” So in this post I’m going to go more in depth on searching for a ship to sink. In a future post, I’ll show how to figure out where to fire once a ship has been hit once in order to sink it with the fewest moves possible.
What About the Destroyer?
First, I’m going to demonstrate what happens if the size of the ship has changed. If you downloaded the sample code from the last game algorithm blog post, you’ll see that there is a variable name that you can pass into the main method called lengthOfShip. If you change that to a 3, you’ll see a resulting map firing solution like this:
Which is not the solution we’re looking for. We are expecting something like this:
Which is one less shot and equal to 25 / 3 (rounding up to capture the last location). The reason for the mapping error is due to the fact that we have more than one possible arrangement for choosing the next shot. In this case the edge shots are all equally ranked and the algorithm went off course when it chose the first edge case of 0,2. Here’s what the list looked like at this point:
0,2 [3] 0,3 [3] 1,4 [3] 2,0 [3] 2,4 [3] 3,0 [3] 4,1 [3] 4,2 [3] 0,0 [2] 0,1 [2] 0,4 [2] 1,0 [2] 1,3 [2] 3,1 [2] 3,4 [2] 4,0 [2] 4,3 [2] 4,4 [2] 1,2 [1] 2,1 [1] 2,3 [1] 3,2 [1]
If the algorithm had chosen 0,1 or 0,3 first, then it would have worked out. In order to ensure that we get the best outcome, we could implement a look-ahead algorithm, but I’m going to move on for now, because there are other issues to consider and this whole problem could work out on its own.
I ran this with a battleship (4 spaces) and this is the resulting pattern:
It appears that ships with even number lengths work and odd does not. I can try a carrier, but I’ll have to increase the map size, otherwise it’s just a trivial diagram.
My purpose in pointing out the fact that even numbered ships happen to work out is that we are going to eventually be searching for the PT boat (unless we get lucky when we search for another ship and hit it early on). Let’s say we start with the carrier and we get a hit, then we switch to the battleship and we get a hit (I’m assuming we don’t hit a different ship). Once the carrier and battleship are sunk we can search every 3 squares to find the destroyer and sub. The problem with this algorithm is that we will eventually start hitting odd numbered squares. If we start by searching by every four squares, we’re guaranteed to hit a carrier or a battleship. For a 10×10 box, we will hit both of these within 26 shots. Then we can switch to the 2 square search mode and we are guaranteed to hit the remaining ships within an additional 34 shots (for a total of 50 shots).
But, I’m not happy to just guess at which search algorithm would be best, so I’m going to write a dumb and dirty program to randomly position all the ships on a 10×10 board and use a step-down pattern of 5,4,3 and 2 to see how many shots it would take to sink all ships. Then I’m going to try and use only even numbered patterns 4 and 2) to do the same. Then I’ll compare. To make sure I get the maximum shots, I’ll have to loop and put in random ship positions thousands of times. I could create a program that finds every combination of ship positions, but I think random positions will save time and get close.
I ran the loop 20,000 times for each algorithm to see what I could come up with. Then I re-ran each algorithm several times to see if the max number would change and I came up with this:
Step down algorithm (5,4,3,2,): 59 shots, max Even algorithm (4,2): 40 shots, max
The difference between the two algorithms is much larger than I expected, but it seems conclusive to me that an algorithm that searches every 4 squares until the largest un-sunk ship is a length of three, then every 2 squares is the most efficient algorithm.
Download the Code
If you want to experiment with the code yourself, or you want to use my methods as part of your own battleship game, you can download the code from my GitHub account by clicking here.