18

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.

Dbz
  • 2,721
  • 4
  • 35
  • 53
  • 6
    [The Google results](https://www.google.com/search?q=battleship+probability+map) looks promising... – Bernhard Barker Jul 29 '13 at 07:51
  • 1
    Probable given which model? Are all possible ship locations equally probable (i.e. uniform distribution)? Or do you have another distribution to model the locations of ships? – mitchus Jul 29 '13 at 15:48
  • 2
    There was a competition on Stackoverflow about this: http://stackoverflow.com/questions/1631414/what-is-the-best-battleship-ai Answer #3 uses a heatmap over most probably battleship locations – Thomas Ahle Aug 02 '13 at 09:09
  • Also have a look at this article: http://thevirtuosi.blogspot.dk/2011/10/linear-theory-of-battleship.html – Thomas Ahle Aug 02 '13 at 09:19
  • Have you taken a look at this code (https://github.com/GrahamBlanshard/AI-Battleship/blob/master/prograham/battleship/ProbabilityMap.java) – scohe001 Aug 08 '13 at 03:12

4 Answers4

5

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.

pseudoDust
  • 1,336
  • 1
  • 10
  • 18
  • I believe the number of permutations will be too huge to iterate through in feasible time, and you'll likely end up with roughly or even exactly equal probabilities for each square. It's easy to prove there will be 4 lines of symmetry at the least (vertical, horizontal and 2 diagonal ones). What makes sense, however, is to gather statistics based on real AI vs human games. It's a plausible assumption that humans will tend to use some squares more than others. It may also be dependent on particular person, so the AI may learn and try to distinguish players. – Karadur Jul 29 '13 at 07:33
  • Perhaps I could start with each square having the same probability, and as events happen, it updates squares around it in real time. The question then would be how exactly should the `probability_board` update in response to misses and sinks. Hits are easy – Dbz Jul 29 '13 at 08:26
  • @Karadur - It seems you are only considering an empty board, there isn't much you can say about an empty board in any case, other then - don't guess near the eadg - which my method would solve. But the strategy only really gets interesting when the you already made some guesses. As for the large amount of permutations, the point is you don't need to check every permutation you only need to check (5+4+3+3+2)*2 = 34 options per square i.e. 3400 total, that's not much... plus OP's (@Dbz) suggestion makes it even easier. – pseudoDust Jul 29 '13 at 14:07
  • @Dbz - That's a great idea, i'll elaborate as an edit to my answer – pseudoDust Jul 29 '13 at 14:09
2

Nice question, and I like your idea for statistical approach.
I think I would have tried a machine learning approach for this problem as follows:

First model your problem as a classification problem.
The classification problem is: Given a square (x,y) - you want to tell the likelihood of having a ship in this square. Let this likelihood be p.

Next, you need to develop some 'features'. You can take the surrounding of (x,y) [as you might have partial knowledge on it] as your features.

For example, the features of the middle of the following mini-board (+ indicates the square you want to determine if there is a ship or not in):

OO*
O+*
?O?

can be something like:

f1 = (0,0) = false
f2 = (0,1) = false
f3 = (0,2) = true
f4 = (1,0) = false
**note skipping (1,1)
f5 = (1,2) = true
f6 = (2,0) = unknown
f7 = (2,1) = false
f8 = (2,2) = unknown

I'd implement features relative to the point of origin (in this case - (1,1)) and not as absolute location on board (so the square up to (3,3) will also be f2).

Now, create a training set. The training set is a 'labeled' set of features - based on some real boards. You can create it manually (create a lot of boards), automatically by a random generator of placements, or by some other data you can gather.

Feed the training set to a learning algorithm. The algorithm should be able to handle 'unknowns' and be able to give probability of "true" and not only a boolean answer. I think a variation of Naive Bayes can fit well here.

After you have got a classifier - exploit it with your AI.
When it's your turn, choose to fire upon a square which has the maximal value of p. At first, the shots will be kinda random - but with more shots you fire, you will have more information on the board, and the AI will exploit it for better predictions.

Note that I gave features based on a square of size 1. You can of course choose any k and find features on this bigger square - it will give you more features, but each might be less informative. There is no rule of thumb which will be better - and it should be tested.

amit
  • 175,853
  • 27
  • 231
  • 333
1

Main question is, how are you going to find statistically probable locations. Are they already known or you want to figure them out? Either case, I'd just make the grid weighed. In your case, the initial weight for each slot would be 1.0/(SIZE^2). The sum of weights must be equal to 1. You can then adjust weights based on the statistics gathered from N last played games. Now, when your AI makes a choice, it chooses a coordinate to hit based on weighed probabilities. The quick and simple way to do that would be:

  1. Generate a random number R in range [0..1]

  2. Start from slot (0, 0) adding the weights, i.e. S = W(0, 0) + W(0, 1) + .... where W(n, m) is the weight of the corresponding slot. Once S >= R, you've got the coordinate to hit.

This can be optimised by pre-calculating cumulative weights for each row, have fun :)

Karadur
  • 1,226
  • 9
  • 16
  • I think a weighted grid is a good idea. I don't want to gather statistics though because I generate ship placement randomly – Dbz Jul 29 '13 at 08:31
1
  • Find out which ships are still alive: alive = [2,2,3,4] # length of alive ships
  • Find out spots where you have not shot, for example with a numpy.where()
  • Loop over spots where you can shoot.
  • Check the sides of the given position. Go left and right, how many spaces? Go up and down, how many spaces? If you can fit a boat in that many spaces, you can fit any smaller boat, so this loop I'd do it from the largest ship downwards, and I'd add to the counts in this position as many +1 as ships smaller than the one that fits.
  • Once you have done all of this, the position with more points should be the most probable to attack and hit something.

Of course, it can get as complicated as you want. You can also ask yourself, instead of which is my next hit, which combinations of hits will give me the victory in less number of hits or any other combination/parametrization of the problem. Good luck!

Jblasco
  • 3,827
  • 22
  • 25