coan.net: Nice ideas, I like the Moving Battleboats best!

Here's another: We already have Behemoth Chess, so why not Leviathan Battleboats? It would be like "plain" Battleboats (one shot per turn), except the "beast" strikes at a random square on each turn, so effectively you have two shots. The random factor means you would have to adjust your shooting pattern during the game.