Hi, I'm making a PC implementation of the battleship advanced mission game. I am now designing the AI for this game and I was hoping someone here on gamedev.net could point me in the correct direction. I would like to emphasize that this is not a normal battleship game. If you don't know battleship advanced mission take a look at the following link and read the information about the fourth game mode. http://www.hasbro.com/common/instruct/BattleshipAdvancedMission.pdf Thank you very much for your help

The strategy is essentially the same as normal battleship. The problem really boils down to this:

1. What are the minimum number of moves required to find N bodies.

Every shot you make should be the shot the eliminates the largest number of possible locations for the largest ship that is still floating. Shoot, rinse, repeat. When you get a hit on a boat (and don't know where it is) you're next shot should be the one that a) helps determines the boats position, and b) eliminates the largest number of remaining positions for the largest floating ship.

You hunt for the largest ship because once you've found it you get 'free' information. If you find the aircraft carrier, then you've also found 5 places where the other ships are NOT.

The search planes, exocets, and whatnot, don't really change the search stategy at all-- it's still one of determining 'what action eliminates the largest number of possible locations on the grid'-- you just have more options available to help you eliminate possibilties.

As far as defence goes: There are probably all kinds of 'optimal' layouts for Battleship Advanced that would maximize the number of turns required to find your ships. This might be an interesting problem to apply a Genetic Algorithm to.

If take out initial placement of ships, you could also apply a Game Tree to this problem. It's definately one of MINimize you're search time while MAXimizing the opponents. The evaluation function could, at the very least, return the number of possible locations left for all ships. I think it would lend itself very well to move transposition since the board is entirely static after the first turn.

W

If your battleships are only lines on a grid (like the x line below) :
1 2 3 4
---------------------
| x | x | x | x | 1
---------------------
| . | . | . | . | 2
---------------------
| . | . | . | . | 3

and not other shapes then it's a little bit easier when it comes to determing ships position. Say that the above "ship" is the biggest one in your game. In case you hit 1*1 you only have 3 possible directions to check, down, left and right (let's assume that the ship's on the edge of the board). What willh said about the "largest ship" is very true, so that would be the main goal for the AI. So find some way to determine if what you've hit is the big one or not.

What I recommend is training the AI to determine if there are to ships drawn one near the other or not, if you don't do this, the PC might get "confused" about what he hit or not. Take this example:

1 2 3 4
---------------------
Ship A | x | x | x | x | 1
---------------------
Ship B | x | x | x | . | 2
---------------------
Ship C | x | x | . | . | 3
---------------------
No Ship | . | . | . | . | 4

If AI hits 1*1 and goes further with 1*2, 1*3 and 1*4 (where it hits nothing)it will think it took down Ship B (which it actually didn't, it only took down one part of every battleship.) Also it could continue with 3*1, 3*2 and think that Ship C is down as well, thus leaving Ship A the only left target when actually there are 3 more to go...

Hope this was helpfull. I made a battleship game in C some time ago, but altough I had preety much of the AI settled down (at least concept) I never finished it. Good luck with the game ;)

Thnx for all the good replies. I will certainly put those to good use.

Hazard org: you can determine what's been hit and destroyed, even in situations like the one you mentioned, provided your search strategy always follows 'available' lines.

You just need to gaurantee that the last shot on a boat is at either one of the ends of the ship. From there (provided you know which boat was sunk) you can deduce the position.

Anyone up for a friendly game of computer-vs-computer battleship? :)