Introduction
In my previous two blog posts on game algorithms, I showed how to search for a ship in a battleship game. Now, I’m going to show how to sink a ship as soon as your search algorithm gets a hit. In this article, I’m only going to discuss possible algorithms, there will be no accompanying code.
Ship Length and Direction Unknown
One of the challenges to battleship is that you don’t know what size the ship is that you hit, once you have made the first hit. You also don’t know which direction it is facing. So the first step is to figure out the direction (and hope it’s a PT boat, so you can sink it at the same time you discover the direction).
So the first thing to do is find the direction. We all learned this technique after playing battleship the first few times in our lives. Basically, we fire on each square above, below, to the left and right of the location that we got a hit. Ignoring any squares that are already hit. I usually follow a circular pattern until I get another hit, but you can do a cross pattern too. In order to reduce the amount of shots you need to take, you can do some analysis of the board and determine if you need to shoot each square, or possibly, any remaining ship is too long to fit in the direction that you might test. For example, here is a 5×5 map with one destroyer:
We managed to get a hit at square
1,1. If we next fire on square 0,1, we might get a hit, but we could also
get a miss. Same with square 1,0. However, if you shoot at square
1,2 or square 2,1, you’ll notice that we will get a hit, no matter where the
destroyer is positioned (remember a destroyer occupies 3 squares). So we
only need to fire on 1,2 and if that was a miss, then 2,1 to find the direction
of the destroyer.
This indicates that we could create an algorithm that checks each possible
position of a destroyer that contains square 1,1 and determine what the
probability is that it would be located in any of the possible surrounding
squares. Then we can choose the most probable squares first.
Now, let’s assume we shot square 1,2 and got another hit. We’re also
assuming that we only have one destroyer on the board. So the board looks
like this:
Now we have a 50% chance that we can sink the ship by firing on square 1,0 and a 50% chance that we can sink the ship by firing on square 1,3. So we just take a chance and shoot one side, then, if that didn’t sink the ship, fire on the other side. Ship sunk.
Multiple Ships on Map
OK, now we have a map containing two or more ships, let’s say a destroyer and a PT boat on the same 5×5 map. Now, what would happen if the map looked like the above map and you fired on square 1,0 and 1,3 and both missed?
You guessed it. There’s a PT boat facing vertical on the right side of a vertically facing destroyer. The PT boat is a no-brainer, since there is only room for it to fit in squares 0,2 and 1,2. The destroyer could still occupy 0,1 or not.
So, we would need an algorithm to determine that if we shot on both sides of a ship and it didn’t sink, then we hit two ships. The algorithm could get a bit tricky once we have figured out that we hit more than one ship, because the second ship could be facing the other way. However, any ship facing horizontally, will eventually get sunk. According to the rules of battleship you must announce which ship was sunk. So now we’ll also need to verify that the ship sunk matches the number of squares shot at. Here’s an example:
In this example, once square 1,3 is shot the announcement that the PT boat was sunk should indicate that square 1,1 doesn’t belong to the PT boat (assuming we fired square 1,3 last). At this point, we would know that the destroyer is vertical with one of the squares on location 1,1.
Here’s another scenario:
In this scenario we got our first hit on square 1,1, then we fired 1,2 followed by 1,3, then sunk a destroyer at 1,4. So now, the cell at 1,1 is the PT boat. However, it could still occupy any of the remaining 3 squares (0,1 or 1,0 or 2,1).
Other possibilities include scenarios where several ships are lined up in parallel, causing a row of hits that don’t sink any ship, but are actually hits on many ships.
Conclusion
I believe I have covered all possible scenarios that will occur in battleship. However, it would be wise to write a simulator that randomly positioned all the ships on a 10×10 map and then used the seek until hit algorithm followed by the algorithms described above to sink your ships. Executing this simulator in a loop thousands of times followed by a test that scans the map and ensures that all ships have been sunk would be a good way to verify your algorithms are correct.
Also, if you are writing the game itself, then unit tests are a must. You should set up each scenario and run a unit test based on the scenario to make sure each algorithm executes correctly.
One other aspect to keep in mind (assuming you’re going to write a battleship game and use these algorithms) is that this will be a very hard game to beat. So you might want to have an adjustable game difficulty and dumb down a few of the algorithms when in easy mode. You’ll also want to randomize your shots when seeking ships. If you don’t, then the algorithm will always shoot in the same pattern and the person playing the game could catch on to the best places to hide their ships.
To make the game more difficult, you could get even more sophisticated and record the patterns that the human player uses when they hide their ships (assuming it’s only one person playing the game). After a few dozen games, ship position rankings can be recorded, like battleship positioned near edge of map 80% of the time, or PT boat positioned near the middle of the map 60% of the time. Then the computer can take random shots near the edge or in the middle first to increase the likelihood of hitting a ship early.
One other detail to note: I didn’t mention if each side takes one shot per turn or multiple shots per turn. The algorithms described above assumed one shot per turn. If you’re taking multiple shots per turn, then the above algorithms still apply, except it’s best to try and sink the discovered ship as quickly as possible. If you can determine the direction that the ship is probably facing, then you can shoot an entire line to try and hit any possible positions that the ship is in. It’s better to waste a shot or two and sink a ship as fast as possible, which would reduce the number of shots the enemy can take.