Ghost Ships

The player has limited information about the game board, and must do the work of determining the location of his enemy's ships. If a player fires on a square and is informed that the missile struck something, or if a ship moves into a player's visible area (around his own ships), the location of an enemy ship has been revealed.

However, typically only one segment is seen at a time, and there are a number of possible ship placements that a segment could represent. We call these possibilities ``Ghost Ships''. When the A.I. learns something about the enemy's position, it places a set of Ghost Ships on the board, representing hypothetical locations of enemy ship.

The Ghost Ships have an associated probability, and as the game progresses they are aged. If the enemy ship segment disappears from view, then the ship must have moved; we then remove the original Ghost Ship and place new ones at each location the ship could have moved. As ships are ``split'', each new ship's probability is only a fraction of the original's.

The probabilities are used by a smart firing algorithm to decide what part of the board is most likely going to contain an enemy ship, and thereby deciding where to fire.

Though there may be several explanations for an enemy ship's movement, not all are possible. Conflict resolution is used to remove Ghost Ships which cannot represent an actual enemy ship, perhaps because the ship would be over an exploded square, or because the ship would be visible but we can't see it.