How about add a submarine to the game.

1. You can't kill submarines

2. They can only move one square per turn (diagonal OK)

3. They use "sonar" to detect enemy ships. They can't pin point them. Just detect that there is one or more ships above them (in the 3x3 square grid with the sub in the middle). As you move the sub around, you could deduce an enemy's ship location.

4. You get all of your shots plus one submarine move per turn.