Thursday, June 19, 2008

Battleship Game Algorithm Explained (Part 3)

This is part 3 of the mini-series explaining the inner workings of the Cubido C# Pirates Winner Algorithm. We have talked about how to find the cell best suited for a trial shot. Now let's see what we can do to improve the accuracy of sinking shots, that is the follow-up shots once a trial shot hit on a ship.

So what needs to be decided at this point is in which direction to continue shooting after the first hit. The stakes are high - after all it's possible to produce three unnecessary misses until we know for sure were the ship is really located.

Let's have a look at the following scenario, and suppose that there is one ship left of size 4, one ship of size 3 and one ship of size 2:



It somehow seems tempting to select the eastern neighbor cell for the next sink shot, because of the large unknown space in that direction. But as it turns out that would be a mistake.

A better approach is to calculate the probabilities for the ships that are still left on the battlefield to be located on each unknown neighbor cell (of course considering the fact where we have hit the ship already). This is very similar to our strategy when placing trial shots.

The ship of size 2 can be located in either of the four directions, so this does not really help.

There is 1 possibility for the ship of size 3 to be located on the western neighbor cell, 2 possibilities on the northern neighbor cell, 2 possibilities on the eastern neighbor cell and 2 possibilities on the southern neighbor cell. So the western cell is out of the game.

Regarding the ship of size 4, there is 1 possibility to the west, 2 to the north, 2 to the east and 3 to the south. The southern neighbor is our target of choice.

In case we miss we'll give it another try the next round by applying the same mechanism. After all the probabilities have changed by then (the ship is then more likely to be positioned horizontally).

Once we hit a second ship cell we can be sure about its orientation, but may still not know about the exact location. So we continue to calculate probabilities for neighbor cells on each side until the ship has been sunk. After that we store the information about which ship size just has been sunk, mark all cells surrounding the ship with State Impossible, and switch back to trialshot mode (as explained in part 1).

In part 4 we are going to put all of that together, and have a look at the resulting sourcecode.

Previous Postings:

Followup Postings: