Battleship Search Algorithym

[cjqp]

Does anyone know of a good algorithym for the game "Battleship"?

cjqp

[jemidiah]

I honestly blanket every other square in a grid when I play, though it does get boring so I usually break from the pattern. Other than complete randomness, you could use some type of grid like above.

[sql_lall]

It depends how much time u have or what stage in the game u r at, or how many squares are left...

Cos u could do a greedy search, find which square is most likely to contain a boat.

Or you could look ahead more, and find which *SET* of moves are best, but this takes longer

[cjqp]

Hmm, thanks for responding! The method I've used in the past is an X and then filling in the regions most likely to have ships. Unfortunatly, the dang 2x1 ship (forget its name) usually excapes me no matter what I do.

I guess I'll put some methods in (programming the game for a computer assignment) and see which are best

Thanks,
cjqp

[sql_lall]

Yeah, the only way to get the 2x1 is to do a criss-cross grid of the whole thing, like checker-board, that's the only way of definitely getting the 2x1...

[wossname]

I find a quick way to find a ship is to start in the centre and work outwards in a spiral, jumping every other square.

Once a hit is scored, check north, east south and west of it and continue in a direction that works. When that direction stops working run back to the start of that line and go in the other direction until the ship sinks.

Always remember the squares you've tried before!

Won every match in a computer algorithm competition last year. :smug: :annoying smirk:

[cjqp]

Thanks wossname! I'm still developing the program's interface (VB has a maximum of like 230 controls on a form, so I'm having to use SetParent API and this has become a little tricky lol), but I'll try your algorithym when I get to that part.

cjqp

[wossname]

Why don't you use a grid control? Or create a control array at runtime.

[opus]

In my opinion the best way to win battlefield is this:
First try to get the bigest ship, to get this one you only have to check every fourth square (the big one has four squares).
When hitting a ship, destroy it. The smaller the ship you , the better for you.
When all big one are sunk, change to the next smalllest ship (a ship of 3 squares, shoot only every third square). Continue until you have only the 1 square ships left, then you have to shoot at every square.
Of course you store the squares already shot, and you can use some smart search algo's the select the most effective square. Like, if you try to search for a three square ship, and the squares to shoot form an cross, you better shoot the centre, that way you only need one shot.

[cjqp]

Thanks for the suggestion opus, I'll add it to the list I'll try.

cjqp

[dis1411]

i've heard that bombing in triangles works well..