Well first of all randomly placing ships and shooting is actually a pretty good strategy. This is what the default player does and any deviation from it can be pretty badly punished by it.
One simple thing that people did to start improving over the random start was restricting placement of ships to a single half or quarter of the board. Doing this allowed most teams to start beating the initial strategy.
However clustering your ships is only effective against random shot placement so when people start implementing targeting you actually become more vulnerable. The first effective targeting strategy was surprisingly simple, if you hit something choose an adjacent square as your next target.
The team that squeezed to the top refined this by choosing an adjacent square that hadn’t already been fired at. The next level of improvement would probably be a non-trivial look at the probability that another ship square lay in the adjacent squares by looking at the information surrounding them.
There was a lot of work around the concepts of adjacency and whether the square had been fired at and the teams all seemed to converge towards the clojure.set library (if they were aware of it).
I’m now thinking of what fiendish problem would force and exploration of this library as it seems incredibly powerful for all different kinds of problems.