Contests

UBC has a two week break due to the Vancouver Olympics. I have been using the time to work on various programming projects. I have become involved in a number of contests:

-RoboCup: A robot soccer contest. I am working on the AI for the robots. We recently sent in qualification materials. If we qualify, we get to compete at RoboCup 2010 in Singapore this summer. Last year we went to Austria for the contest.

-ImagineCup: Our team is planning to compete in the game design category. We haven't done much implementation yet, but we plan on creating a text adventure game (plus some simple graphics). If we make it to the finals we get to go to Poland this summer.

-Son of Darts: I just started this contest a couple of days ago. I am currently ranked 145th out of 368 competitors. I am using stochastic local search to optimize the solutions.

-BattleCode: A fun AI programming contest. Last year our team did pretty well.

This break I am also planning on submitting a paper about PPM to a NLP workshop. I also need to study for a big midterm happening in two weeks. It is going to be a busy break!

Harbin Trip

Over the last week I have been in China attending the ACM ICPC World Finals. The trip was really fun. I got invited to come even though I am not a competitor since I might be part of the UBC team next year. Six people from UBC came (one coach, three competitors and another guest). Harbin is in the northern part of China so was extremely cold. The temperature was usually between -10 to -30 Celsius. I have posted pictures of my trip here. There were a lot of activities organized by ACM so there wasn't much time to explore Harbin ourselves. Harbin is famous for ice and snow sculptures. There were sculptures lining the streets all over the city.

UBC did well at the finals. They got 18th place. I think UBC's record is 13th place. Here is the final scoreboard. There were three North American teams which did better: Stanford, Cornell, and Carnegie Mellon. These teams only did better on time and did not solve more problems than UBC. All three members of this year's team are not eligible to compete again next year. Based on the performance of the second and third UBC teams, it is extremely unlikely we will be nearly as good next year.

:)

Cutlery

I must get a complete set. Three to go!

Class Project

Here is the PPM project I have been working on. The paper may not be high quality since I had to rush to get it submitted on time. However, I am pretty excited about some of the topics it covers and the algorithm it introduces. I learned a surprising amount about information theory when researching the topic. I plan on continuing developing the algorithm and applying it to new domains.

:(

NIPS

Earlier this week I had a great time at the NIPS conference. I got to meet several famous AI researchers. The best part of the conference was the poster/demo sessions. My favourite posters were related to Hinton's Restricted Boltzmann Machines. I also got a chance to talk with some people from Numenta about HTM. Google and Microsoft Research both actively participated at the conference. Google had an interesting booth unveiling research they had done in using quantum computing for image search.

Disclaimer for the following paragraph: I know nothing about quantum computing and have a bad memory, so this information is not reliable. When I walked up to the booth I was very sceptical since as far as I know quantum computers are still theoretical. From what I understood they used adiabatic quantum computers to solve an optimization task. I think introducing the image search problem is misleading because any improvement in the image search is not necessarily due to the quantum computer. They should have introduced their image search algorithm and quantum optimization algorithm completely independently of each other. I would only be impressed if the quantum computer was solving an optimization problem faster than what can currently be done on a classical computer. I asked the Google guy the following question: "I remember seeing a proof that a certain type of adiabatic quantum computer could be simulated on a classical computer just as efficiently using simulated annealing. Any comments?" His response seemed to indicate that he thought that the quantum algorithm they were using could solve problems in polynomial time which could not be done on a classical computer. In addition, he gave a cool explanation of how the quantum computer did the optimization by simulating a particle in the search space and allowing the particle to travel through walls so that it doesn't get stuck in local minima. Also, the search space is slowly changed from an easy-to-solve "bowl" to the actual objective function so that the particle converges on the global minima. The algorithm supposedly needs to be run several times since it is stochastic and doesn't necessarily find the global minima every time.

Prediction by Partial Matching

I am currently working on a project for a natural language processing course. Given my interest in temporal pattern recognition, I decided to make the project about text prediction. For the last few weeks I have been really excited because I thought I discovered an innovative algorithm which was doing extremely well compared to existing methods. In particular, it completely outperforms my previous approaches using neural networks/HTM when it comes to almost any pattern recognition task. However, today I was disappointed to learn that almost exactly the same algorithm was discovered back in the 80s. It is a data compression algorithm called prediction by partial matching (PPM). PPM happens to be one of the best text compression algorithms, so at least its nice to know that I independently discovered it. However, I would have been much happier if I had been the first to do so.

Hockey Bears

I've done some online research on these bears, and as far as I can tell they appear to be genuine. [YouTube link]

Temporal Pattern Recognition

As an alternative to neural networks, I have found that a technique called linear predictive coding does a good job at temporal pattern recognition. I wrote a couple short scripts in MATLAB which do binary prediction and play rock paper scissors. The binary prediction seems to work better than the version I made using neural networks. I think that the RPS AI also works better than the version I made using hierarchical temporal memory, although I haven't interfaced the two programs together yet to test them.

CTV

A friend let me know that there was a clip of me on CTV. It was on a story about upgrading Vancouver's networking system for the Olympics. I was completely unaware that I had been filmed.

Genetics

Rock Paper Scissors

I have released a rock paper scissors (RPS) AI on my homepage. It was made using hierarchical temporal memory. RPS is a great domain to test temporal pattern recognition, so I am somewhat disappointed how poorly my AI does. Some people may be surprised that there is any strategy involved in RPS. After all, an AI which just outputs random moves will win 50% of the time. Humans are terrible at being random, so its not hard for an AI to win against people. When competing AI against AI, superior strategies can be determined based on their performance against a large number of opponents. This allows some AIs to get much better results than ones which just output random moves.

I have become really interested in hierarchical temporal memory since starting grad school. My supervisor Nando said that this might be a topic I can pursue for my thesis. I think there are some pretty major flaws with the implementation by Numenta. I implemented my own version using backpropagation neural networks. So far I have tested it in three applications (binary input prediction, handwritten digit recognition, and RPS). The results haven't been great. Next I plan on comparing it directly to NuPIC on their standard datasets. Hopefully my implementation does better! If so, this would be a great thesis topic.

2009 Pacific Northwest Contest

Today was the ACM ICPC regional programming contest. Here is the final scoreboard:

UBC^ got first place.
Stanford got second and third place.
UVic got fourth place.
UBC+ got 10th place.
UBC* got 15th place.

There were 77 teams competing. I was on UBC*. In theory UBC* was supposed to do better than UBC+. They lucked out because one of their members knew a specific algorithm from a graph theory course which allowed them to solve a very difficult problem (which only two teams solved). Our team did really well on time, but we got completely stuck once we reached five problems. In fact, we were in first place when we got to five problems. There were two or three additional problems which were definitely solvable, but unfortunately we didn't finish them in time :(.

Nort

I have released another Java game called Nort. This is a two player game based on Tron.

Soku

Today I made a game called Soku using Java (you can play it here). It is a remake of a game I made in high school. I think it is the best of the three Java games I have made so far (the other two being Ping and Swarm). Ping is also a remake of a game I made in high school.

Photo Crasher

Circles

Two perfectly round circles:

Four perfectly round circles:

my brain hurts.

Time Stop Version 1.0

I just released version 1.0 of Time Stop. This version has eight levels. Enjoy!

w00t

My computer is finally working. After letting it dry for a couple days, I finished replacing the motherboard. Unfortunately this didn't fix any problems. I bought a nice new 1TB drive from NCIX which finally got my computer working. I guess the other symptoms I saw might have been due to a corrupt Ubuntu live CD.