Informed Battleship AI

Summary:

Set out to measure where people typically place ships in Battleship, possibly found pattern? Mostly learned about online survey biases.

This project is from a little after the Multitouch Screen, in Fall 2007 at the beginning of my sophomore year of college. A friend and I were considering algorithms to use in a Battleship AI and started to wonder if people tend to place ships in common locations. It seemed reasonable to assume corners would be frequently populated, but we didn't want to just build in a few heuristics based on guesswork. We decided to measure how often spots on the Battleship board were populated by ships by recording how people placed ships when playing.

Motivation:

To build an 'informed' Battleship AI, we wanted to measure how frequently spaces on the board are populated.

Build Details:

To record how people place ships, I wrote a simple web-app that presented the user with a blank board and allowed them to click to place ships. Once all of the ships are placed, the app would submit the placement mask to a database that would keep track of every entry as well as a composite board that combined every submission into a heat map.

Blank board presented to the user. Full of AJAX-y goodness.

Populated board with score that meant little to nothing.

I never had the energy to actually write a working Battleship AI, so after the ship placement was submitted, the app would return a score based on how much the submitted pattern differed from the current composite map. A low score was supposed to indicate that an AI using the recorded results would quickly find your ships by following a look-up table.

To collect data, I sent out a link to the app to college friends. We got maybe 40 submissions from that, but we wanted much more. After submitting a link to reddit, the number of submissions shot up above 600, enough to start looking for trends. The heat map below shows the frequency of a spot being occupied by a ship, with black being 10% and white being 25%.

Strangely symmetric?

First thing of note is how the upper left and bottom right corners are populated nearly a quarter of the time, while the other corners are significantly less. The whole board shows rough symmetry around a line connecting top left to bottom right, which seems strange to me now. Before I make any grand claims about significant patterns in Battleship placement, I would redo the experiment with a few changes:

1) Verify the code to make sure the board isn't accidentally getting flipped every now and then (I wasn't the best programmer back when I did this)

2) Log the IP address of a user to eliminate duplicate submissions.

3) Create an interface that is easier to use and mimics ship placement on a real board (the click-to-rotate might have biased the ship orientations)

Insights:

1) Asking people to fill out an online survey is asking for people to mess with your results.

2) If you want people to pretend to play Battleship, make an interface that mimics Battleship