Archive for February, 2010

More Addictive than Nicotine

Saturday, February 27th, 2010

When I set out to design this year’s Google AI Challenge, one of my priorities was the make the contest as addictive as possible. I didn’t have to look far for inspiration. All I had to do was borrow a few tricks from the Big Tobacco marketing playbook.

  1. Get them hooked early. In order to deliver the first fix as quickly as possible, I posted a five-minute quickstart guide with instructions on how to get your name onto the global leaderboard in less than five minutes. I posted some simple working entries on the website which could be directly re-submitted without any modifications. Cigarette companies use Joe Camel to advertise to children, drug dealers offer free doses to lure first-time users, and the contest has Starter Packages.
  2. Instant gratification. In last year’s Google AI Challenge, people would have to wait between one and two hours to see their latest submission’s ranking. This means that if it’s 3:00 AM and you just submitted your code, there is a fairly large incentive to go to bed. This is clearly unacceptable. This year, participants were able to see their new ranking within at most five minutes. By shortening the feedback loop to almost nothing, we set up a situation that is very similar to a gambling addict at a blackjack table. Just one more hand…
  3. Lace it with addictive chemicals. Despite much effort, I was not able to figure out how to lace the contest with addictive chemicals. That being said, I am fairly sure that time spent working on the contest is highly correlated with intake of caffeine and MSG.

Cigarette companies use Joe Camel to advertise to children, drug dealers offer free doses to lure first-time users, and the contest has Starter Packages.

After all was said and done, I believe that my efforts paid off. Here are a few quotes from contestants, taken the day after the submission deadline:

“I’m glad the deadline wasn’t extended, i was sleeping better last night than the previous dozens of night. i was constantly working on it, that is finally over :)

“actually I dreaded the deadline getting extended. I am really happy it’s over. my obsessive-compulsive behaviour would have continued for some time”

“I am glad that this is finally finished too, or wife is going to get grumpy. (unrecognizable yelling at the background)”

So… Close…

Thursday, February 25th, 2010

Most people can imagine the joy that comes from watching the odometer of an old truck roll over.

It's like your 50th wedding anniversary, except better.

In the last couple days, I’ve been approaching a milestone of my own. The traffic for the Google AI Challenge website has been approaching our initial dream goal of 1,000,000 pageviews. This morning I got out of bed and immediately checked it, what with my being a Google Analytics addict. Here is how I found it:

So... close...

Couldn’t have cut it any closer than that. Looks like today is going to be the big day.

Genetic Algorithm Art Fail

Wednesday, February 24th, 2010

Today I have started an experiment to use a Genetic Algorithm to create artistic drawings. I hope to achieve results similar to Bergen and Ross from Brock University. As a test, I tried approximating the Mona Lisa in grayscale using only circles. Here is the result.

Fail.

While this is an interesting image, it doesn’t look a lot like the Mona Lisa. Some of the largest features of the Mona Lisa are present to a degree, such as a light region in the center, dark bottom corners, and a light top-right corner. However, I wouldn’t call this a success.

What went wrong? I believe that the set of genetic operators I chose (the Galib defaults) are not appropriate, especially the mutation operator. I will implement some new ones that make more sense and try again. Hopefully the results improve.

For the Genetic Algorithms, I am using Galib. For the image manipulation code, I am using CImg.

CImg Image Library for C++

Wednesday, February 24th, 2010

Today I started playing around with the CImg library. It’s a library for C++ which can read and write image files in many common formats, and also manipulate images in memory. I want to use it for some specific computer art projects that I have had in mind for a little while.

As a test to familiarize myself with the CImg API, I constructed the following image. It’s a bunch of multicolored semi-transparent circles placed in a golden ratio spiral pattern. Click the image for a bigger version.

A golden ratio spiral pattern, using multicolored semi-transparent circles

The Collatz Conjecture

Friday, February 19th, 2010

I have been fascinated by the Collatz conjecture for years. It’s a math problem that is so simple to understand, yet no mathematician has managed to solve it. Since the problem was first proposed by Lothar Collatz in 1937, many mathematicians have gone crazy trying to solve it. Here’s how it works.

The Collatz function takes one number, denoted by n, and turns it into another number. If n is even, the result is n/2. If n is odd, the result is 3n+1. For example, if n is 3 then the result is 10. If n is 4 then the result is 2. If n is 5 then the result is 16. You get the idea.

A Collatz sequence is formed by starting with a number, and repeatedly applying the Collatz function to extend the sequence. For example, the Collatz sequence for n=3 is 3-10-5-16-8-4-2-1. The Collatz sequence for n=5 is 5-16-8-4-2-1. The Collatz sequence for n=2 is just 2-1. Here is a picture of the sequences for n=7 and n=19.

After looking at some of these sequences, you may start to notice a pattern. No matter how high they go, they always seem to come back down to 1. Does every Collatz sequence always come back down to 1? Perhaps some of them get into a loop and keep going round forever, or perhaps some of them just keep going up and up towards infinity. This is the Collatz conjecture: prove that every Collatz sequence eventually comes back down to 1.

Another way to picture the problem is using total stopping times. The total stopping time of a number is the number of steps it takes for the number’s sequence to reach 1. The Collatz conjecture states that every number has a finite stopping time. Despite being such a simple problem, and being open for almost 75 years, nobody has managed to prove or disprove the Collatz conjecture.

There are a couple really tantalizing patterns in the total stopping times. Let me show you just one. Have a look at the first 1000 stopping times.

The first 100 total stopping times. The horizontal axis is n, and the vertical axis is the total stopping time of n.

Notice any patterns? It looks like some of the points are bunching up into short horizontal lines. Furthermore, these short horizontal lines seem to line up in large sweeping curves. To investigate these patterns further, I wrote a short C++ program to draw the same chart, except for the first ONE BILLION stopping times. This time, the x-axis is logarithmic.

The first one-billion total stopping times. The horizontal axis is n, and the vertical axis is the total stopping time of n.

Whoa, now that’s a pattern! Look at all those nice straight lines. Check out a closeup of the bottom-right part of that image.

Close-up of the patterns in the total stopping times

What is causing all those straight lines? Why are they all the same length? The most interesting question to me is, why is there always a long “dash” followed by a short “dot”? If we can explain the structure of these regular patterns, can we construct an exact probability distribution for the total stopping time of any number? Could this distribution be the key to finally proving or disproving the Collatz conjecture? If you want to do a bit of work on the Collatz conjecture, answering these questions might be a good place to start.

Google AI Challenge Goes Viral

Friday, February 5th, 2010


Today I had quite a shock when I checked the Google Analytics page for the Google AI Challenge website.  Yesterday, the daily traffic graph looked like this:

I had been pumping up the contest for a couple days, fighting for every additional visit I could get.  I had finally managed to get over 500 unique visitors in one day!  Very rewarding.
You can imagine my shock when I checked the Google Analytics today to find that the graph looked like this:
Wow.  Yesterday we had about 100 users, mostly from the University of Waterloo.  When I woke up today, we had 300 users from 37 different countries.  That happened fast.
So, what happened?  Where is all this traffic coming from?  Google Analytics tells me that most of the spike is coming from this Hacker News article and this Reddit thread.  I am hoping that the contest is in the early stages of going viral, and that the trend continues upwards.  On the other hand, this could prove to be a one-time spike.  I’ll update in a couple days to let you know what happened!

Google Analytics is More Addictive than WoW

Thursday, February 4th, 2010


It’s been a few days since we opened the Google AI Challenge website.  Since then, I have been having a bit of fun playing with the Google Analytics page that is attached to the contest website.  Google Analytics lets you slice and dice traffic statistics in all kinds of ways.  Here are some highlights.

Website traffic broken down by browser

I knew that usage of Internet Explorer was lower amongst students, but I didn’t expect it to be that low!  IE clocked in at just over 6%.  Firefox was the big winner, with almost half the unique visitors to the site.  My personal favorite, Chrome, weighed in second, followed by Safari.  What the heck is Opera?  :-)

Website traffic broken down by operating systemAlthough Internet Explorer has all but disappeared amongst students, Windows is still the operating system of choice.  I was surprised to see that Linux was ahead of Mac.  I would have been interested to see the breakdown of the different flavors of Linux, but the information was unavailable.

Most of the site’s visit have come from Canada at this point.  However, we’re about to launch a big push to raise awareness of the Google AI Challenge internationally.  I am hoping that by the end of the contest, this world map is all lit up.

Then there’s my favorite feature: the graph.  The graph appears on the front page of the Google Analytics dashboard, and shows your site’s daily traffic rise and fall over time.  It is all-consuming and addictive.  Must… make… the line… go… up!  The graph updates once per day at around 1 AM.  How cruel is that?  Try falling asleep at 11 PM like a normal person when you know that the graph will update in just two short hours!

Google AI Challenge Launched!

Monday, February 1st, 2010

We just officially launched the Google AI Challenge at the University of Waterloo.  Around 50 people attended the kickoff event today in MC 3003.  Many of them have already submitted simple entries, as you can see on the leaderboard!

This sudden onslaught on “real” users has helped focus our attention on a few issues.  First, there is a serious deficit of content on the website to help users get off the ground with their entries.  This should be mostly fixed within a few days.  Also, the Tron simulator that is currently part of the starter packages doesn’t work on Windows.  This seriously sucks, and I have to fix it ASAP.

Otherwise, everything seems to be running smoothly.  The contest backend is chugging along without complaint.  A few contestant expressed an interest in implementing advanced algorithms like A* pathfinding and Alpha-Beta search, which hopefully will keep UW from getting mauled when the competition opens at other schools.