You should look into multi-player paper battleship as it plays any number of players and plays in the same amount of time (depending on board size).