How to generate statistically probably locations for ships in battleship

Question

I made the original battleship and now I'm looking to upgrade my AI from random guessing to guessing statistically probably locations. I'm having trouble finding algorithms online, so my question is what kinds of algorithms already exist for this application? And how would I implement one?

Ships: 5, 4, 3, 3, 2

Field: 10X10

Board:

OCEAN = "O"
FIRE = "X"
HIT = "*"
SIZE = 10
SEA = [] # Blank Board
for x in range(SIZE):
    SEA.append([OCEAN] * SIZE)

If you'd like to see the rest of the code, I posted it here: (https://github.com/Dbz/Battleship/blob/master/BattleShip.py); I didn't want to clutter the question with a lot of irrelevant code.

Answer 1

The ultimate naive solution wold be to go through every possible placement of ships (legal given what information is known) and counting the number of times each square is full.

obviously, in a relatively empty board this will not work as there are too many permutations, but a good start might be:

for each square on board: go through all ships and count in how many different ways it fits in that square, i.e. for each square of the ships length check if it fits horizontally and vertically.

an improvement might be to also check for each possible ship placement if the rest of the ships can be placed legally whilst covering all known 'hits' (places known to contain a ship).

to improve performance, if only one ship can be placed in a given spot, you no longer need to test it on other spots. also, when there are many 'hits', it might be quicker to first cover all known 'hits' and for each possible cover go through the rest.

edit: you might want to look into DFS.

Edit: Elaboration on OP's (@Dbz) suggestion in the comments: hold a set of dismissed placements ('dissmissed') of ships (can be represented as string, say "4V5x3" for the placement of length 4 ship in 5x3, 5x4, 5x5, 5x6), after a guess you add all the placements the guess dismisses, then for each square hold a set of placements that intersect with it ('placements[x,y]') then the probability would be: 34-|intersection(placements[x,y], dissmissed)|/(3400-|dismissed|)

To add to the dismissed list:

1. if guess at (X,Y) is a miss add placements[x,y]
2. if guess at (X,Y) is a hit:
   • add neighboring placements (assuming that ships cannot be placed adjacently), i.e. add:
     • <(2,3a,3b,4,5)>H<X+1>x<Y>, <(2,3a,3b,4,5)>V<X>x<Y+1>
     • <(2,3a,3b,4,5)>H<X-(2,3,3,4,5)>x<Y>, <(2,3a,3b,4,5)>V<X>x<Y-(2,3,3,4,5)>
     • 2H<X+-1>x<Y+(-2 to 1)>, 3aH<X+-1>x<Y+(-3 to 1)> ...
     • 2V<X+(-2 to 1)>x<Y+-1>, 3aV<X+(-3 to 1)>x<Y+-1> ...
   • if |intersection(placements[x,y], dissmissed)|==33, i.e. only one placement possible add ship (see later)
3. check if any of the previews hits has only one possible placement left, if so, add the ship
4. check to see if any of the ships have only possible placement, if so, add the ship

adding a ship:

• add all other placements of that ship to dismissed
• for each (x,y) of the ships placement add placements[x,y] with out the actual placement
• for each (x,y) of the ships placement mark as hit guess (if not already known) run stage 2
• for each (x,y) neighboring the ships placement mark as miss guess (if not already known) run stage 1
• run stage 3 and 4.

i might have over complicated this, there might be some redundant actions, but you get the point.