0 votes
1 view
in AI and Deep Learning by (27k points)

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 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 to be played on a 10x10 grid.

  2. Each competitor will place each of 5 ships (of length 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

  5. The opponent will notify the competitor if the shot sinks, hits, or misses.

  6. Gameplay 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:

  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-ups and tear-down methods have been added to alleviate the time strain.

  9. The code should be posted on stack overflow as an answer, or, if too large, linked.

  10. Max total size (uncompressed) of 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. The best 51 games out of 101 games are the winner of a match.

  2. All competitors will play a match against each other, a 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!

1 Answer

0 votes
by (57.2k points)
edited by

There are many algorithms for winning the classic game of battleship.

I will explain the working of Battleship with the help of Hunt’s Algorithm. It includes an instruction to explore nearby spaces whenever a prior shot is hit. Every human who has ever played battleships can perform well.

The Hunt algorithm completes 50% of games within 65 trials until it gets defeated. Improvement comes from adding the parity principle to the Hunt algorithm.

  • Parity principle(helps in slow down the speed solvers immensely in official solves, and is generally seen as a pain to deal with) trains the algorithm to take into account that ships will always cover odd as well as even-numbered tiles on the board. For example, in the below visual, you should avoid shooting the upper left white tile when you have already shot its blue neighbors. It makes use of the Probability Density Function.

  • In this function, at the start of every turn, it works for all possible locations. Many different combinations are possible with five ships. These different combinations are all added up, and every tile on the board is assigned a probability that it includes a ship part, based on the tiles that are already uncovered.

                        image

If you want to make your career in Artificial Intelligence then go through this video:

Welcome to Intellipaat Community. Get your technical queries answered by top developers !


Categories

...