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

Multitouch Screen

Summary:
I built a 30" multitouch podium on wheels using a webcam, projector, laptop, and some failures.

This project goes back to Summer 2007 when I had just completed my freshman year at college, so I'm a little hazy on the details. This started back in the days before the iPhone and before multitouch screens were in everyone's pockets. Large multitouch screens were a common DIY project on the internet, and open source software libraries for processing input were starting to appear. I decided this would be a fun project to try, and luckily had a summer job that offered to pay for it (as long as they could keep it in the end). I was working as a web developer for the local community college at home, and they decided a multitouch screen would be a cool tech demo for prospective students.

Motivation:
Build a large multitouch screen podium for educational purposes.

Build Details:
Luckily I found some old pictures I took during the build process, so I will try to piece them together to form a coherent story. The basic concept is to have an infrared camera pointed at the back of an acrylic panel. Through some image processing, fingertips placed on the panel will be registered as individual 'blobs' and tracked as mouse pointers. My first build attempt was to use FTIR to create infrared bright points wherever a finger touched the panel. The infrared light originates from LEDs placed on the edges of the panel pointed inwards. First step was to drill holes in the edge of the panel for the LEDs and solder them together.

I don't remember how many there were, go ahead and count for me.

Holes drilled, LEDs placed.

Soldered together.

Whole panel with wires for short segments of LEDs. Also pictured, messy workbench.

The CCD sensors in webcams are usually sensitive to the wavelengths of IR light emitted by the LEDs I chose. Unfortunately, the webcam I was using had a IR-blocking filter installed. I was able to open up the lens assembly, smash the filter to tiny pieces, clean it out, and reinstall the lens to get a working IR webcam. Since I only want to pick up IR light and not visible, I taped a stack of exposed film negatives to the front of the lens. The film negatives look opaque to the eye, but actually pass IR light through fairly well.

After setting up the panel above the IR webcam, I found that it did not work. Placing a finger on the panel did not create a spot of reflected IR light that the webcam could pick up. I also tried placing a silicone rubber sheet above the panel to increase contact area, but it didn't help. I don't think I ever found out why it didn't work, and I can't think of a good reason now.

Fortunately there is another method of detecting fingertips on the panel that does not involve the side-mounted LEDs. Assuming there is a source of IR light either from above or below the panel and there is an IR diffuser placed on the panel (like a sheet of tracing paper), objects placed directly on the panel will have sharp outlines, while anything farther away will appear blurry. Using an unsharp mask in the image processing, I was able to filter out blurry shapes and isolate any objects placed on the panel.

With a working method of detecting input, I went on to build the podium part. Since the intended use was for showing off to prospective students, I went with a simple gloss black box on wheels.

Basic shape.

Panel rested on a few screws sticking in from the sides.

Painted black.

Wheels, because carrying would end in tragedy.

Added fans to keep the computer cool in the Texas Heat.

Inside the box I placed a laptop and a small projector to display the screen image on the panel from the bottom. Once I had the image processing software calibrated, the results were impressive.

Demo code to show image processing steps alongside a cool fluid/smoke code using the multitouch input.

Calibrated between the webcam, laptop, and projector.

With everything working, I modified NASA World Wind (similar to Google Earth but open source and Java) to use multitouch input. It did all of the things you would expect from Google Earth running on an iPad, with zooming, rotating, and scrolling with gestures. I demoed the screen at an open house day at the college and nearly broke it in the process. The wooden frame was not really sturdy enough to handle being moved around much or even rolled over rough concrete. Still, it performed spectacularly and wowed many young children. My summer job ended days later, and I'm not sure if the screen was ever used again. Still, it was quite an experience.



Insights:
1) If you add wheels to something, make sure it is stable enough to handle a little shaking.
2) For a screen this large, expect people to rest objects/arms on the sides, causing spurious touch events.
3) Sometimes, fancy algorithms can make up for failures in build design.

Introduction

Years of successfully avoiding getting my own blog, and then this happens. Oops.

Well now that it exists, I suppose I should say a little something about why it exists. I tend to work on a lot of projects outside of my real job*, and would like a place to publish what happens. Typically these projects involve some mixture of electronics, programming, and photography. I don't intend on writing up full tutorials on how to do these things, mostly because it would take up too much of my time. Instead, I plan on documenting a few things for each project; the motivation, build details, results, and insights gained. Some of these projects of mine go back a few years, so the posts might not be in chronological order. I also will be learning this whole blog thing as I go, so posts may get a few post-publishing edits before they make sense.

* I'm a graduate student in astrophysics, so I'm using the term "real job" very loosely.