Kaggle

I recently found a great website which hosts competitions related to machine learning. I am currently competing in the freeway travel time contest and the grant proposal contest. I think Kaggle has potential to be very successful. The contest sponsors benefit by getting good solutions to tough problems at a relatively low cost. The contest participants benefit by getting access to interesting problems and the potential of winning cash prizes.

Christmas in Sri Lanka

From left to right: Nathan (dad), Archie (dog), Martha (mom), George (tortoise), Skylor (brother), Aaron (brother), Byron (me).

Al Zimmermann's Programming Contests

Over the last couple of days I have been working on a programming contest called Topswops. I am currently ranked 31 out of 312. This is the third Al Zimmermann programming contest I have competed in. The site has some very interesting optimization problems. In my first two contests I ranked 65 out of 414 and 49 out of 143.

Game Review

I noticed that somebody wrote a review about the laser game I made. The game got quite a bit of traffic when I posted a link to it on Reddit. I am pleased.

Lasers

Thanks to everyone for the useful feedback on my Laser game so far. I have added another three levels, making a total of ten. I am trying to order the levels in increasing difficulty. However, I am having trouble comparing the difficulty of levels (since I already know the solution to levels when I design them, it is hard to judge how hard it would be for someone else to solve them). It would be great if I could get some more feedback on if you encounter an earlier level which appears to be more difficult than a later level.

Batman

[link]

Lasers

My laser reflection game now has seven levels. I have found that it is much easier to create levels for this game than it was for the art gallery problem game. I think the last two levels are quite challenging, so let me know if you manage to beat them.

Lasers

Today I started working on a new Java game. It will be a geometry-based puzzle game. The idea is to position mirrors so that they reflect lasers to a set of targets. I have posted a prototype version here.

State of the Art

For my master's thesis I have been looking into compression-based techniques for classification, clustering, and anomaly detection. I have implemented a classification algorithm using PAQ and evaluated it on three datasets. So far the results look very promising and it seems to get state of the art results on all three datasets. The first dataset (called 20news) involves categorizing newsgroup articles into one of twenty categories. The other two datasets are spam-filtering (ling-spam and PU1). For the spam-filtering datasets a tradeoff can be made between spam/ham misclassification rates. I therefore evaluated my algorithm using ROC curves. Although my algorithm wasn't the best spam-classifier on all portions of the ROC curves, on both datasets there was still a significant portion in which it got state of the art results.

It's Alive!

After the suitcase incident, my desktop has been broken for the last six months. Earlier this week I replaced its motherboard. When I tried booting, I was disappointed to hear that it was still just beeping error codes. However, the error codes this time indicated a memory problem (which is different from the beep codes I was hearing before). I identified the damaged stick of RAM and removed it. Finally my computer seemed to boot normally, except that it unexpectedly turned off about 30 seconds later. I identified this problem to be due to the heatsink not attaching properly to the CPU. I ordered a new heatsink from Ebay and it arrived today. I just put in the new heatsink and the computer seems to be functioning normally. yay. In total, transporting my desktop in a suitcase destroyed the motherboard, one stick of RAM, and the CPU heatsink.

Art Gallery Problem

My art gallery game now has seven levels. Designing challenging levels is surprisingly difficult. Today I implemented mirrors which reflect the guard visibility polygons (seen in the screenshot above). Hopefully mirrors will allow me to create harder levels.

Logarithmic Scales

[link]

Genius

[link]

Art Gallery Problem

I was looking through Wikipedia's list of NP-complete problems to try to come up with an idea for a game. A few of the problems on the list have already been made into games. I thought the art gallery problem might make an interesting game. My research on Google suggests that it has never been adapted into a game before. I spent the day implementing the game and have posted it online here. So far I have only made four levels but I plan on adding more soon.

Google Offer

I just accepted a job offer from Google! The position is Software Engineer. After I finish my master's degree, I will be moving to Mountain View, California.

ACM Eligibility

During the last two weekends I competed in tryouts to be part of the UBC programming team. I did well enough to qualify for the first team. However, yesterday I noticed on the 2010 ACM eligibility chart that I am ineligible because I am slightly too old (by four months). We tried emailing the ICPC manager but she verified that I can not compete :(

Happy Petrov Day!

Thank you Stanislav Petrov for saving the world on September 26, 1983.

Sri Lanka

Last week I finished my internship at Google. I have been in Sri Lanka for about a day now. Cathay Pacific managed to lose both of my suitcases on the way here. So far I like Sri Lanka. It seems to be similar to India except better in a number of ways.

Homework

Translation courtesy of reddit user thelifan:

My life here is terrible. Work environment is not great and benefits are little. But don't worry, everyday only about 10 people are seriously injured and I'm very careful. We opened a small shop, business isn't bad. Although I don't understand very much English, but I can still understand what white men say. Hopefully we can become successful, I will work hard and take care of myself.

Are you guys well? Miss you very much, hope to see you again.

Skydiving!

This morning I went skydiving from 15,000 feet. It was an incredible experience. The free-fall lasted for about one minute and parachuting lasted five minutes. The "falling" sensation only lasted for a few seconds after leaving the plane. Once reaching terminal velocity, the free-fall was quite comfortable (and surreal). My instructor let me control the parachute for part of the descent. We also performed a fun maneuver spinning the parachute around in a tight spiral. A few years ago I went bungee jumping. I think making the jump was probably scarier for bungee jumping than skydiving. However, I enjoyed everything about skydiving a lot more than bungee jumping.

Skydiving!

Next week I am planning to go skydiving with some Google interns. Should be fun!

YouTube Easter Egg

For YouTube videos with the new layout style, performing the following steps will start up a game of Snake:

1) Click on the video to give it keyboard focus
2) Hold the left arrow key

Here is a YouTube video that it will work on. Discovered via Reddit.

Body Invaders

[YouTube link]


[YouTube link]


[YouTube link]

National Geographic

New Camera!

I am now the proud owner of a Panasonic Lumix DMC-ZS7. Today I took some photos with it around the Google campus. One of my favorite features of the camera is that it tags pictures with GPS coordinates. Picasa Web Albums automatically creates a Google Map with the photo locations.

Demon's Souls

Today I finally beat Demon's Souls. I am pretty proud of this accomplishment given how ridiculously hard the game is. It is the best PS3 game I have played.

RoboCup 2010

I am currently in Singapore attending RoboCup 2010. UBC Thunderbots is competing in the small size league. We played four games and did not advance to the semi-finals. We lost three games and won one game. The Thunderbots website has lots of pictures, videos, and a blog. I will be in Singapore for one week.

TopCoder Open

Today I discovered that TopCoder is hosting an interesting marathon match over the next month. The problem is pretty simple:

Input: list of edges
Output: vertex locations
Goal: minimize number of edge intersections

There is an online scoreboard which shows your ranking after each submission. I was in last place after my first submission. My second submission was quite an improvement and put me in second place =)

siarco

I just released an open source version of the arithmetic coder I discussed in my previous post. The project is hosted at http://code.google.com/p/siarco/.

Nice Weather

[link]

Arithmetic Coding

This week I wrote a program to perform arithmetic coding. Arithmetic coding is useful for data compression. This summer I plan to release an open source lossless data compression algorithm which uses the coder.

The program to do the arithmetic coding is only around 150 lines of Java code. For a while I had a really annoying bug related to precision errors with floating point numbers. The vast majority of the time I spent developing the program was trying to fix this bug. Today I finally figured out a great solution to the precision problem which has almost no computational overhead and is theoretically guaranteed to always be correct.

Wikipedia claims "every programmatic implementation of arithmetic encoding has a different compression ratio and performance." I find this statement surprising because I think I can construct a proof showing that my program encodes the input with exactly the minimal number of bits. If the number of bits is not divisible by 8, my program uses a few extra bits in order to store the resulting bytes to disk. As far as I know it is impossible for another arithmetic coder to achieve a better compression ratio. I tried testing the program on several files and it achieved a compression ratio extremely close to the theoretical cross entropy limit.

In terms of performance my algorithm also has nice properties. The time and space complexity are both linear in terms of the number of input characters (which is optimal). The code only performs basic arithmetic operations on primitive data types, so it should also be very efficient. The code works with any input alphabet size. I plan to convert the program to optimized C code and compare its performance to other arithmetic coders. Since I am already confident that its compression ratio can not be beaten, if it turns out to be faster than other arithmetic coders as well, then my algorithm could be an important contribution =)

Googleplex

I really enjoyed my first week at Google. So far I have mostly been doing training. The food at the Googleplex is amazing. I will be eating breakfast, lunch, and dinner there, so I will only have to cook for myself on weekends. I have been trying to go to a different café for every meal. My apartment is about a 30 minute bike ride from the campus, so that exercise might help counteract the abundance of free food. Google gave me a nice bike to use over the summer.

Yesterday I bought a new monitor so that I can play my PS3. I also bought a game called Demon's Souls. I tried getting Demon's Souls at three different places in Vancouver but they were all sold out. In Mountain View I tried checking Best Buy and Toys Я Us but they were also sold out. Finally, I found a copy at Game Stop (which turned out to be their last copy). The ridiculous thing is that this game was released over half a year ago. The gameplay is incredibly addicting (and incredibly difficult). It is the best PS3 game I have played.

Suitcase Computer

I recently discovered that traveling with a desktop computer in a suitcase is a bad idea. When I was packing for my trip to Mountain View I spontaneously decided to bring my desktop computer since I had lots of extra room in my suitcases. I have traveled with a desktop computer before without any problems.

The first annoyance was that both my suitcases were way over the weight limit, so I was charged expensive overweight fees. I would have been under the weight limit without the computer. When I arrived in Mountain View and started unpacking the computer, I noticed a horrible rattling sound when I moved it. A rattling sound indicating loose components in the case.

The CPU heatsink had somehow become detached and was bouncing around inside the case the entire trip. Today I bought some thermal grease and reattached the heatsink. When I tried to boot the computer it started making beeping sounds and immediately shutdown. It is most likely the motherboard which was damaged. I wish I had just left the computer in Vancouver.

Imagine Cup

Surprisingly, we advanced to round 2 of Imagine Cup. Here is the demo we submitted. 150 teams out of 700 advanced. Only 6 teams advance to the finals. We are debating whether finishing the game is worth the time investment given we have such a low probability of making it to the finals :D

lol

Googleplex

I just accepted the internship offer from Google. I will be headed to the Googleplex this summer. Numenta replied saying that they will not be giving me an offer. I will be doing a 14 week internship at Google. When I finish the internship in August I plan on visiting my parents in Sri Lanka for a few weeks before returning to UBC.

Summer Internship

Today I got internship offers from both Google and Facebook. I am just waiting to hear back from Numenta before I make a decision of which to accept. On Friday I visited Numenta for a full day of interviews. Jeff Hawkins and I were on the same flight to San Francisco. We shared a taxi from UBC to the airport and he even gave me a ride to my hotel after the flight! It was a great opportunity to talk with him about HTM.

o_o

Contests and Interviews

There is a new programming contest on Al Zimmermann's webpage: http://www.azspcs.net/Contest/MagicWater. I am currently ranked 8th out of 56. The contest lasts months, so there is no way I will maintain this high rank :D. On the son of darts contest I currently have a score of 90.00 and a rank of 59 out of 384.

Three friends and I are entering the Game Design category of Imagine Cup. Today we submitted a game demo. It is a simple text adventure game using Silverlight. The game also works in Linux using Moonlight. I wrote the text parser for the game. Our team was speculating that we probably put the fewest man-hours into making the game out of all the competitors (so I will be surprised if we advance to future rounds). If we make it to the finals we get a free trip to Poland.

I am currently in the interview process with Google, Facebook, IMO, and Numenta for a summer internship. Later this week I will be flying down to California for a full day interview at Numenta. Coincidentally, Numenta's founder Jeff Hawkins is giving a talk at UBC this week. I have scheduled a meeting with him when he gets here!

Son of Darts

I spent the entire day working on Son of Darts. I am now in 71st place out of 379. My current submissions use a variety of searches including stochastic local search, backtracking, greedy, and various heuristics. Out of the 19 Canadian competitors I have the highest score :D

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.