What Is the Best Battleship Ai

What is the best Battleship AI?

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.

Can I minimax a battleship 2 player game?

Short answer: No.

The minimax algorithm needs some sort of evaluation of the gamestate in every node. In battleship you don't have all information as a player or AI (opponent ships are not known) which makes it impossible to do this. You could of course cheat and let the AI test all possible moves and find the hidden ships X moves ahead, but I would say this is against the rules.
The AI would then always find the ship and always make hits which would also make it very boring to play against.

You can find some inspiration for example here on other algorithms to use.

Battleship AI about sinking part under certain rules

You can't actually have perfect knowledge about the length of any sunken ship under those rules. You can assign some probability, but there's no way to get the length of a particular ship. Consider the one-dimensional version:

0123456789
.XXXXXYY..

Where "X" and "Y" represent different ships. If you start firing at position 4, and keep going right, you'll sink a ship after 4 hits. You know the ship you just sunk is no more than 4 spaces long, but it could be anything from 1-4 spaces in practice.

The most likely thing is that you hit a single ship, but you can verify that by back-tracking from the first hit. In this case, you'll get hits all the way back to position 1, and then another ship will be reported as "sunk". So you know that ship X + ship Y are a total of 7 spaces long. There are only a few combinations that can add up to 7, so there's some information there. Unfortunately, there are a number of possible two-ship combos that add up to 7.

It's much worse on the 2D board:

 0123456789
A..........
B..........
C..A.......
D..A.......
E..ABCDEE..
F...BCD....
G...BCD....
H....CD....
I.....D....
J..........

If you shoot from E0 to E9, you'll score 6 hits, and one sunk. Without checking each spot from D2 to D7, you can't be sure whether any of those hits was on a perpendicular ship sticking down into row E. You'd also have to check F2 to F6, to make sure there are no ships in the other direction.

---

Related Topics