0

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

Conditions 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
  • game manager use two methods to comunicate with my player: the first asks where to shot, the second tells the result of it and so on

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. If you imagine a bigger and more populated board, things are even more turns consuming && uncertain.

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

Hope I was clear in explain my question.

p.s. I'm aware of this question, but I can't read C# language: just started some months ago with java, by the way if someone is willing to explaing me Dreadnought algorithm for the sinking part I would be glad :)

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...

Community
  • 1
  • 1
Goet
  • 57
  • 1
  • 1
  • 8
  • 3
    Repost of: http://stackoverflow.com/questions/16577070/battleship-ai-about-sinking-part-under-certain-rules – zch May 16 '13 at 22:37
  • @goet Seems like you already found your answer. Surely you don't expect someone to port a chunk of C# to Java for you. Just work your way through enough of a tutorial to understand the answer you have. Besides, for algorithms over plain arrays, Java and C# are barely distinguishable. – millimoose May 16 '13 at 22:37
  • 2
    @goet If you can read Java you can read C#, they're very similar. – Jim Garrison May 16 '13 at 22:40
  • I don't expect someone to port anything... it's not what I asked... I'm just asking for a general explanation of the algorithm. I'm working on it from almost a week and still don't get how it can be so precise as I saw... however I don't want to be harassing, so please delete this question if you believe it's right to do so and I'll not open a new one :) – Goet May 16 '13 at 22:49
  • If you receive no information regarding the hits, and a 1x1 ship is possible, then I'd simply have the algorithm store the shot data and look for necessary shapes; that is, if the layout of hits/misses/sunk dictates that one of the ships in the array *has* to have been sunk, remove it from the board and adjust your algorithm accordingly. At the beginning, you'd be looking for all ships, but as you eliminate the possibility of a certain type of ship being in play, you can adjust the strategy to search more efficiently for the remaining ships -- you'd just have to handle the elimination logic. – cabbagery May 16 '13 at 22:49
  • @cabbagery Thanks, it's what I was come up with. I'm storing the hitted spots in 2 arrays: one vertical one horizontal, depending on the second hit. It's the most intelligent thing I could get till now, but it has the problem that with certain configurations you can't be sure about what you sunk anyway! – Goet May 16 '13 at 22:55

0 Answers0