What is the best Battleship AI?

Question

Battleship!

Back in 2003 (when I was 17), I competed in a Battleship AI coding competition. Even though I lost that tournament, I had a lot of fun and learned a lot from it.

Now, I would like to resurrect this competition, in the search of the best battleship AI.

Here is the framework, now hosted on Bitbucket.

The winner will be awarded +450 reputation! The competition will be held starting on the 17th of November, 2009. No entries or edits later than zero-hour on the 17th will be accepted. (Central Standard Time) Submit your entries early, so you don't miss your opportunity!

To keep this OBJECTIVE, please follow the spirit of the competition.

Rules of the game:

1. The game is be played on a 10x10 grid.
2. Each competitor will place each of 5 ships (of lengths 2, 3, 3, 4, 5) on their grid.
3. No ships may overlap, but they may be adjacent.
4. The competitors then take turns firing single shots at their opponent.
   • A variation on the game allows firing multiple shots per volley, one for each surviving ship.
5. The opponent will notify the competitor if the shot sinks, hits, or misses.
6. Game play ends when all of the ships of any one player are sunk.

Rules of the competition:

1. The spirit of the competition is to find the best Battleship algorithm.
2. Anything that is deemed against the spirit of the competition will be grounds for disqualification.
3. Interfering with an opponent is against the spirit of the competition.
4. Multithreading may be used under the following restrictions:
   • No more than one thread may be running while it is not your turn. (Though, any number of threads may be in a "Suspended" state).
   • No thread may run at a priority other than "Normal".
   • Given the above two restrictions, you will be guaranteed at least 3 dedicated CPU cores during your turn.
5. A limit of 1 second of CPU time per game is allotted to each competitor on the primary thread.
6. Running out of time results in losing the current game.
7. Any unhandled exception will result in losing the current game.
8. Network access and disk access is allowed, but you may find the time restrictions fairly prohibitive. However, a few set-up and tear-down methods have been added to alleviate the time strain.
9. Code should be posted on stack overflow as an answer, or, if too large, linked.
10. Max total size (un-compressed) of an entry is 1 MB.
11. Officially, .Net 2.0 / 3.5 is the only framework requirement.
12. Your entry must implement the IBattleshipOpponent interface.

Scoring:

1. Best 51 games out of 101 games is the winner of a match.
2. All competitors will play matched against each other, round-robin style.
3. The best half of the competitors will then play a double-elimination tournament to determine the winner. (Smallest power of two that is greater than or equal to half, actually.)
4. I will be using the TournamentApi framework for the tournament.
5. The results will be posted here.
6. If you submit more than one entry, only your best-scoring entry is eligible for the double-elim.

Good luck! Have fun!

---

EDIT 1:
Thanks to Freed, who has found an error in the Ship.IsValid function. It has been fixed. Please download the updated version of the framework.

EDIT 2:
Since there has been significant interest in persisting stats to disk and such, I have added a few non-timed set-up and tear-down events that should provide the required functionality. This is a semi-breaking change. That is to say: the interface has been modified to add functions, but no body is required for them. Please download the updated version of the framework.

EDIT 3:
Bug Fix 1: GameWon and GameLost were only getting called in the case of a time out.
Bug Fix 2: If an engine was timing out every game, the competition would never end.
Please download the updated version of the framework.

EDIT 4:
Tournament Results:

Answer 1

I second the motion to do a lot more games per match. Doing 50 games is just flipping a coin. I needed to do 1000 games to get any reasonable distinction between test algorithms.

Download Dreadnought 1.2.

Strategies:

• keep track of all possible positions for ships that have >0 hits. The list never gets bigger than ~30K so it can be kept exactly, unlike the list of all possible positions for all ships (which is very large).

• The GetShot algorithm has two parts, one which generates random shots and the other which tries to finish sinking an already hit ship. We do random shots if there is a possible position (from the list above) in which all hit ships are sunk. Otherwise, we try to finish sinking a ship by picking a location to shoot at which eliminates the most possible positions (weighted).

• For random shots, compute best location to shoot based on the likelihood of one of the unsunk ships overlapping the location.

• adaptive algorithm which places ships in locations where the opponent is statistically less likely to shoot.

• adaptive algorithm which prefers to shoot at locations where the opponent is statistically more likely to place his ships.

• place ships mostly not touching each other.