Intro
I have a few blog post subjects in progress, but they’re going to take some time to develop the sample applications that I’ll need in order to explain the techniques that I’ll be blogging about. In the mean time, and due to a little A.D.D. on my part, I’m going to do a blog subject that is more of an analysis process. I’ll show some of the complex ideas that go into designing an algorithm and ensuring it’s success.
Battleship
So I was playing battleship on my iPad. It’s a great time-killer and my goal is to beat the enemy with as few moves as possible. In this rendition of Battleship, you start with 5 ships and you get one shot per ship per turn. So you start the game with 5 shots per turn, until the enemy sinks one of your ships, then you only get four shots per turn. The strategy of this version is a bit different from the one-shot-per turn variety. First of all, if you expect to win, you need to cut down the number of shots that your enemy gets to take per turn, so it takes him longer to find your ships. So that means that as soon as you get a hit, you need to sink that ship immediately, even if you waste a few shots.
Before I get to the strategy of what to do when you get a hit, I’m going to discuss how to minimize your shots to get that first hit. In order to hit all ships with a minimum number of shots, you’ll need to account for the PT boat. This is the smallest ship in the fleet and it takes up 1 square by 2 squares. That means that you can technically shoot every other square in a checkerboard pattern and hit a PT boat with a maximum of 50 shots (10 x 10 / 2). Here’s what the pattern might look like:
If the game board contained only one PT boat and you followed this pattern, then eventually, you’ll hit that boat within 50 shots. This is much more efficient than just randomly shooting on the board because any shots next to each other is a wasted shot.
There is something else here worth considering. First of all, what are the chances that a PT boat is in the upper left corner? Since there are only two possible positions that a PT boat could occupy the corner square, there are only two possibilities of hitting a PT boat in that corner. Contrast this with a square that is on the edge of the map and then there are three possibilities that PT boat is in that position. If the boat is away from the edge, then there is the possibility that a PT boat could be positioned from four directions. So it would seem that an algorithm that shoots the edges of the map and the corners last will eliminate more positions that the PT boat could be in. Of course, this would make for a weak algorithm because sooner or later the opponent is going to catch on to this strategy and position their PT boat in one of the corners. But let’s ignore that for now and go on the assumption that we want to fire the next shot and maximize the possibility of hitting the PT boat.
The first algorithm we’re going to need is to collect a list of each possible location of a PT boat on the board. I’m going to cut the map down to a 5 by 5 map to make this easier to visualize, but here’s the list of possible PT boat locations:
0,0 (Vertical) 0,0 (Horizontal) 1,0 (Vertical) 1,0 (Horizontal) 2,0 (Vertical) 2,0 (Horizontal) 3,0 (Vertical) 4,0 (Vertical) 0,1 (Vertical) 0,1 (Horizontal) 1,1 (Vertical) 1,1 (Horizontal) 2,1 (Vertical) 2,1 (Horizontal) 3,1 (Vertical) 4,1 (Vertical) 0,2 (Vertical) 0,2 (Horizontal) 1,2 (Vertical) 1,2 (Horizontal) 2,2 (Vertical) 2,2 (Horizontal) 3,2 (Vertical) 4,2 (Vertical) 0,3 (Horizontal) 1,3 (Horizontal) 2,3 (Horizontal) 0,4 (Horizontal) 1,4 (Horizontal) 2,4 (Horizontal)
As you can see, I’m starting at zero, and the max coordinate is 4. Now, let’s get all the cells that each of these ships could occupy and make a sorted list of these cells and how many times the cell can be occupied by a PT boat. This is just a brute-force program designed to prove a point that we already know. So here goes:
0,0 [2] 0,1 [3] 0,2 [3] 0,3 [3] 0,4 [2] 1,0 [3] 1,1 [4] 1,2 [4] 1,3 [4] 1,4 [3] 2,0 [3] 2,1 [4] 2,2 [4] 2,3 [4] 2,4 [3] 3,0 [3] 3,1 [4] 3,2 [4] 3,3 [4] 3,4 [3] 4,0 [2] 4,1 [3] 4,2 [3] 4,3 [3] 4,4 [2]
OK, so now we can see that squares like 0,0 (corner square) only occur twice and squares that are not near the edges (like 1,1 and 3,1) occur four times. What this means is that if the user randomly positions their PT boat at any of the possible coordinates and orientations, then there is a greater chance of hitting that boat at square 1,1 than at square 0,0.
Here’s what a corner square looks like (showing 2 possible locations of a PT boat):
By creating an algorithm that spits out this list and then ordering the list by largest occurrences to smallest, we can choose which square to shoot. Now we need to enhance this algorithm to ignore any squares that have already been shot.
So let’s say that position 2,2 was shot last turn and it was a miss. Now what possible locations are left for our PT boat and what is the occurrences?
0,0 [2] 0,1 [3] 0,2 [3] 0,3 [3] 0,4 [2] 1,0 [3] 1,1 [4] 1,2 [3] 1,3 [4] 1,4 [3] 2,0 [3] 2,1 [3] 2,3 [3] 2,4 [3] 3,0 [3] 3,1 [4] 3,2 [3] 3,3 [4] 3,4 [3] 4,0 [2] 4,1 [3] 4,2 [3] 4,3 [3] 4,4 [2]
Notice how there are only 24 squares above. That’s because we’ve already shot at square 2,2 and that doesn’t appear in the list anymore due to the fact that a PT boat can’t be located at that square. Also notice how square 1,2 (adjacent to 2,2) has been reduce to a 3 from a 4.
What would happen if our algorithm was changed so that we would just grab the first largest hit count square and fired a shot, then recomputed and continued until all hit counts reached zero? Would the computer take 25/2 shots in total? What would be the shot pattern that results?
Here are the results:
1,1 1,3 2,2 3,1 3,3 0,2 2,0 2,4 4,2 0,0 0,4 4,0 4,4
That’s 13 shots, which is correct and here’s what it would look like on the map:
The next algorithm to consider is an algorithm to sink a ship after it has been discovered, but I’m not going to go over that algorithm in this blog post.
Get the Code
You can download the code at my GitHub account here. I have commented logging as I went along but you can uncomment the log statements and view the raw data in the log file which will be located in the C:logs directory.