Battleship AI about sinking part under certain rules

Question

I'm having some troubles in finding if, under certain rules, is possible to code an efficient AI for the sinking part of battleship.

Rules are:

• the length of the shortest ship could even be 1. You get to know it at the beginning, when game manager gives you the ships array to place
• ships can't overlap, but they may be adjacent
• game manager tells you if your last shot was an hit, a sunk or a miss. No information about the length of the ship you hitted/sunk

Well, what I don't manage to express formally is the length of sunk ships. I can't see the way to understand, once I sunk a ship, the length of it.

I'd like to use a density approach to estimate where to shot based on the length of still in game ships, but without a system to get the length of a sunk ship, my density never gets "smarter". For the time being, I just save North/South/East/West spots of every hit and consider the job done once my stack is empty. That's very turns consuming of course.

I try to clarify what I'm asking: suppose you have a bidimensional array where you keep trace of your shoots result in this way:

u = unknow spot

m = you shooted on x, y and game manager told you "miss"

h = you shooted on x, y and game manager told you "hit"

s = you shooted on x, y and game manager told you "sunk"

suppose the board is 5 * 5. At the beginning you have this:

      1 2 3 4
    1 u u u u
    2 u u u u
    3 u u u u
    4 u u u u

suppose you shoot on 2, 3 and game manager tells you "hit", now you have:

      1 2 3 4
    1 u u u u
    2 u u h u
    3 u u u u
    4 u u u u

ok, now you start looking around your last shot. No matter if you use a density approach or a stack of N/S/E/W spots from where you hitted. Let's say your algorithm came up with 3, 3. This time is miss:

      1 2 3 4
    1 u u u u
    2 u u h u
    3 u u m u
    4 u u u u

so now you try 2, 2, and it's an hit:

      1 2 3 4
    1 u u u u
    2 u h h u
    3 u u m u
    4 u u u u

now let's say 2,1 and game manager tell you "sunk":

      1 2 3 4
    1 u u u u
    2 s h h u
    3 u u m u
    4 u u u u

Well: knowing that ships may be adjacent, how you get to know the length of the ship you've just sunk without shooting on every single N/S/E/W spot? In this case for istance you'd need to shoot on 2,4 and on 1,3 to be almost sure about what you sunk, and it's turns consuming. See Mark Bessey example below: that kind of situations are even more turns consuming && uncertain than mine.

So the question is simple: there isn't anything better than this N/S/E/W time consuming && uncertain approach?

Hope it clarifies the matter.

p.s. I'm aware of this question, but I can't read C# language... just started some months ago with java :)

p.s. 2 I'm aware of this too (see last illustrations) where as far as I understand the things look quite the same except for the fact that he considers the min length = 2. I could always code 2 algorithms (one if I detect a min lenght > 1, one more "turns consuming" if min length = 1), but I don't get how he manage the thing... looks like he considers only density...

p.s. 3 Why closed? I'm looking for an algorithm working under conditions... I gave conditions and what the algorithm should do. How can I clarify it? How should I express this kind of question? (sorry for asking, no polemic intended, just learning)

Answer 1

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.