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.

:)

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.

Blargh

My computer has been broken for the last month. Today my new motherboard finally arrived. I decided to replace the motherboard on a picnic table outside because a) I wanted to clean my case without filling the room with dust and b) my room is too hot (it is currently 33°C outside and much warmer inside). I had a friend help me replace the components. Everything was going well until about half way through the process. Right when the computer was completely disassembled and parts were lying all over the picnic table, water starts flying at me from all directions simultaneously. Apparently the picnic table is positioned perfectly between at least three high-flow sprinklers. This was a terrifying experience since I know that water and computers do not mix well. It took several trips to get all the components out of range, so a few pieces got thoroughly soaked. I am going to leave the desktop disassembled and let it dry overnight. Hopefully the sprinklers did not destroy my computer :'(

Netflix Prize

The Netflix Prize contest is officially over. One month ago BellKor's Pragmatic Chaos made a submission with a 10.05% improvement over Cinematch. The contest ends 30 days after any submission over 10%. Yesterday a new team called The Ensemble made a submission at 10.09% accuracy (a 0.01% improvement over BellKor's Pragmatic Chaos). Today, 24 minutes before the contest finished BellKor's Pragmatic Chaos made a submission of 10.09%. Four minutes before the end The Ensemble made their final submission with a 10.10% improvement. Both of these teams were actually a combination of many smaller teams. In the end the key to victory was combining the results of a myriad of different algorithms/approaches.

Now that the Netflix Prize has finished I will start focusing on a new contest ☺. Eternity II is a puzzle with a two million dollar prize. I have written a solver using stochastic local search. My solution currently has a score of 437 out of 480. Last year the highest score was 467 (with a $10,000 prize).

Rhythm Recognition

I just posted a new applet on my website which can learn simple rhythms. The rhythms are input by clicking on a button. I plan on creating a few more applets which demonstrate some of the things temporal pattern recognition can be used for.

I actually think that temporal pattern recognition can be used for any task which requires intelligence. Intelligence is equivalent to the ability to recognize and predict patterns. The only reason that we haven't created intelligent AI is because pattern recognition is a difficult problem. Since the code I am using to recognize patterns is terrible compared to what most animals can accomplish, my demos will have to be constrained to relatively simple problems.

Low Ink

[link]

The Blob

The vast majority of my time working on Time Stop was spent making the blob. There were two main challenges in creating it:

Physics:

Since Box2D only simulates rigid body physics, I had to create the elastic body using many rigid components. I first created a grid of circles to act as the main body of the blob. The circles are allowed to overlap and are connected together using many forces. The forces keep the circles at a reasonable distance apart while still allowing them to move relative to each other. This is what gives the blob its elastic properties. I then added a chain of thin rectangles around the edge of the circles to act as a membrane. The membrane helps define the shape of the blob and also acts as a barrier for colliding objects.
Graphics:

OpenGL can only render straight lines. This creates difficulties when trying to render curves (a blob). A curve can be approximated using many straight lines. The straighter parts of the curve require less lines while the rounder part of the curve requires more lines. I used NURBS to create a smooth curve using the rectangles on the membrane as control points. In order to fill in the interior of the blob I used many solid triangles all connected at a central point.
I have released a new version of Time Stop. This version has better blob physics, faster game play, and a new (challenging) level.

Time Stop

The first version of my new game has been released! Time Stop is a 2D physics based puzzle game. It uses the Box2D physics engine, OpenGL, and Creative Commons background music. There is a single level which demonstrates the core game play mechanics. The game can be run by either compiling from source or using one of the Linux/Windows executables (the Windows version currently has some bugs).

Lost in Translation

I found my name in a German article about Imagine Cup. Here is what Google translate outputs on the relevant paragraph:

"
The word "Medaillienspiegel" is no coincidence. As the Olympic Games allegedly making the youth of the world, it is also the meeting of the young programmers conjunctive effect, especially on the development goals (Millennium Development Goals) is the UN. But the spectacle flag at the foot of the Pyramids, the Microsoft of a dispensation granted by the Egyptian government could carry out, showed otherwise. Uninhibited celebrated especially Brazil, China and Poland, with flags and speaking choirs, if a country team, a winner had reached space. The award presented to the winners banners schwenkend, only the Nationalhymen missing. Only the winners from the UK, Canada, the Czech Republic and the United States without a plume occurred at. "I do not know that my code is code is a Canadian," said Byron Knoll at the end of the Finals, as the nations around frenetically celebrated their winner.
"

I think it is commenting on the fact that I didn't have a Canadian flag at the event (most of the other competitors brought flags). As for my quote "I do not know that my code is code is a Canadian" I have a feeling that much of its original meaning has been lost in the English->German->English translation. I have no idea what my original statement was, so I'm not sure if the German translation is accurate ^_^

Trip Summary

I have posted some pictures and videos of the trip. Here is a summary:

June 26th:
My desktop stopped working right as I was about to start packing. It is definitely a hardware problem but I am not sure which components are broken. I can't boot into my normal operating systems and I can sometimes boot into Linux live CDs. Running fsck detects errors in the file system but crashes when attempting to fix the problems. Running a memtest succeeds. It is more than just a hard disk failure since there are also problems reading from CDs and using the network card. Given that so many problems occurred simultaneously, it is most likely a problem with the motherboard or power supply :'(

June 27th:
There were a total of seven Thunderbots team members leaving from Vancouver. We were meeting another two members in Frankfurt and the tenth member in Graz. We left for Frankfurt in the evening. The plane ride was kind of boring since everyone went to sleep and the seats did not have personal screens. My ticket to Frankfurt was extremely cheap; $350 including tax. There was a crazy guy sitting across the aisle from me who was acting really weird. He spent almost the entire flight constantly staring at me. Since I was sitting further back than him, he was sitting completely sideways in his seat with his head always turned towards me. He would also mumble very random sentences occasionally.

June 28th:
After flying to Frankfurt we rented three cars and drove to Graz. We used walkie-talkies to communicate during the drive. Immediately after leaving the airport we managed to lose each other and get out of walkie-talkie range. We eventually found each other again with some luck in a small village. After driving all night on the Autobahn we arrived in Graz early the next morning.

June 29th:
In Graz we stayed at a really nice guest house. The first floor of the house was for the owner's family but the second and third floors were entirely for us. The house was next to a forested area and had a nice view. After the sun came up a few of us decided to take a small hike in the forest. Later in the morning we all headed to the RoboCup contest site. There were two huge halls dedicated to the different RoboCup leagues. The halls were filled with a huge variety of robots. Definitely the place to be for robot enthusiasts. We immediately got to work getting set up for the contest. We brought a desktop computer to hook up to our cameras and run the AI. When we plugged the desktop into a transformer it made a loud bang and started smoking. Without a computer there was no way we could compete in the contest. We couldn't use our laptops because they didn't have the right firewire ports to plug in the cameras. We don't know why the computer exploded when we plugged it in since we used the transformer correctly. This was definitely the low point of the trip. Not only were we all completely exhausted from a lack of sleep but it seemed like we might not even get to compete after working so hard the last couple of months. Our first match was scheduled in two days.

June 30th:
We attempted to fix the desktop by replacing a variety of components (including the power supply, motherboard, CPU and memory). We got the computer booting but it would randomly shutdown after being run for a while. We had no idea why it kept shutting down (its possible that the new power supply we purchased was faulty). Before coming to Austria the greatest number of robots we ever had working at a single time was three. Since teams typically have five robots you can imagine that the AI was lacking proper testing. We brought a total of seven robots but at least one did not work at all and we only had four working gyros (a component that is important for robot movement).

July 1st:
We decided to compete in the first match even though it was likely that the desktop would shut down, instantly turning all our robots into bricks. The game was absolute chaos but surprisingly the computer managed to remain powered on throughout the game. There were a variety of problems in our first match. One problem with the AI was that our robots repeatedly went close to the ball when it was against the rules (when the opposing team had a free kick). This resulted in four of our robots getting yellow cards. When a robot gets a yellow card it is removed from the field for a few minutes. It was just our goalie versus five enemy robots. Luckily the opposing team also seemed to be having some problems and they only managed to score one goal. When the yellow carded robots were put back into play they had some mechanical problems. The referee made us take one of the robots out since it started smoking. Occasionally our robots would randomly start going crazy and spinning at ridiculously fast speeds. We actually had a few really good opportunities to score. If this wasn't our first match I think we could have beaten the opposing team. Throughout the game we were all screaming at each other to fix various problems, so we also had some communication problems. Whenever we lifted a robot off the field its wheels would start spinning up to max speed, making a lot of noise and making handling the robot difficult. One of our team members' hand was bleeding after the match. It must have been quite entertaining for anyone watching the game ^_^

July 2nd:
Our second match was much less chaotic. Once again the computer managed to stay on throughout the match. The team we were playing against was much better than us though, so we lost 10 to 0. During the day we purchased some laptop components which allowed us to plug our two cameras into two laptops. The laptops shared data over a network and one of the laptops ran the AI. We knew that the desktop would not suffice for future matches. That afternoon we had our third match. This match we were clearly better than the opposing team. Some of their robots appeared to move around almost completely randomly. Despite this fact we didn't make a single goal in the first half. Part of the problem is that the AI would sometimes assign an important task (such as chasing/shooting the ball) to a robot which was not capable of moving correctly (perhaps due to a lack of gyro, low batteries, or some other mechanical problem). During half time I decided to switch to a new strategy. Instead of playing with a partially functional team of five robots, I thought it would be better to play with two robots which we knew worked well. One robot would be the goalie and the other robot would be in charge of shooting goals. This strategy seemed to work well and we scored three goals in the second half. Here is a video of one of our goals. Given how hard everyone had been working up to this point, winning a game was a great experience. After the game we finally had a chance to relax and visit a cool mountain castle in Graz.

July 3rd:
I left Graz on a train at six in the morning. I really enjoyed the train ride since there was some beautiful scenery between Graz and Munich. Half way through I had to switch trains. The amount of time I had to switch trains was originally supposed to be five minutes. However, since the train was running seven minutes behind schedule I was forced to switch trains in negative two minutes. That evening I flew from Munich to Cairo.

July 4th:
The robotics & algorithm competition started in the morning. The contest was to program the AI for simulated sumo robots. We could also get one bonus point for programming a "dance" for a physical robot and three bonus points for programming the robot to do some sort of image processing task in addition to the dance. We got 24 hours to do the coding. I finished programming most of the AI within the first couple of hours. The only changes I made after that were tweaking parameters. In order to tweak the parameters I ran a huge number of simulated matches. Since the matches run in real-time, it took many hours to run enough games in order properly test if one set of parameters was superior to another. While I was waiting for the simulated matches to run I programmed the physical robot in order to get the bonus points. I got the robot to recognize different colored pieces of paper to perform six different types of movement. Two of us got three bonus points and the other four competitors got one bonus point. I eventually tuned the AI's parameters to a point where I couldn't see any way to improve it further. My robot could fairly consistently defeat the sample AI that was provided. Since the contest still had about eight hours left, I decided to get some sleep in my hotel room. At least three of the competitors worked the full 24 hours.

July 5th:
After the round-robin contest I had the highest number of points. Watching the matches was pretty fun. Here is a video of the final game. I got to keep one of the robots as a prize!

July 6th:
Microsoft organized a tour of the pyramids during the day. Immediately after leaving the bus one of the locals approached me insisting to take my picture (using my camera) in front of the pyramids. I reluctantly agreed. He also put a scarf on my head. Next he insisted that he take my picture while I was on top of a camel. At this point I was getting irritated by him so I refused (instead he took a picture of me next to the camel). When I tried to get my camera back he started demanding money from me for taking the pictures. I offered a bit of change and he refused and demanded bigger currency. At this point I just wrestled the camera out of his hand. He continued pestering me for money until eventually one of the Microsoft staff came over when he noticed the situation. After that I was more cautious around the locals. Merchants kept trying shove "free" products into my hands and offering to take pictures. One amusing thing I noticed is that whenever someone asked where I was from and I said "Canada", 100% of them immediately responded "Canada Dry". In confusion I later looked it up online and realized that they were referring to the drink (which is apparently very popular in Egypt). I was impressed by the pyramids but the greed of the merchants there was annoying.

July 7th:
During the day some of the teams in different Imagine Cup categories presented their projects. In the evening was the award ceremony. Microsoft set up a cool stage in the middle of the desert for the awards. It had a great view of the pyramids. The award ceremony went much longer than I was expecting so I almost missed my flight out of Cairo. I got to the airport less than an hour before my flight left. The check-in counter had already closed but they eventually agreed to let me board the plane.

Results

Our RoboCup team won one out of five games. We won with a score of three to zero against RoboPets. The results are posted here.

I came in second place in the Imagine Cup Robotics & Algorithm competition. We had a round-robin competition to determine which two players would compete in the final match. I had the highest score in the round-robin contest but I lost the final round.

RoboCup Press Releases

There was a clip about our RoboCup team on CBC news:



There is also a video on the Vancouver Sun website, an article on the UBC Engineering website, and a couple of articles in the local newspapers.

RoboCup

Today we got obstacle avoidance working for the robots. I have taken a couple pictures/videos:

Press Release

Here is an article about the BattleCode tournament results posted on the UBC CS website.

Planes, Trains & Automobiles

I have finalized my travel plans for later this month. I will be competing in both RoboCup and ImagineCup. Our RoboCup team "Thunderbots" is competing in the small size league. Ten of our team members will be attending the competition. On the 27th we will fly into Frankfurt, Germany and rent cars to drive to Graz, Austria. On the 3rd I will have to leave the RoboCup contest early in order to attend ImagineCup. I will take a train to Munich, Germany and fly to Cairo. On the 8th I will fly back to Vancouver through Paris.

For RoboCup we will be competing against some incredibly good teams, so I am skeptical how well we will do. Last year I was working on the AI for the team. Earlier this month we finally got a robot that can move so that I can begin testing the AI. Without actual robots it is pretty difficult to implement the AI since almost everything depends on their mechanical capabilities. I am really impressed by the final robot design the engineers created. It is capable of moving around the field at ridiculously fast speeds. The only potential flaw with the design is the fact that the robot's dribbler easily loses control of the ball whenever it changes direction. Unfortunately I predict that the AI will be our team's weak point. Not that I think that there is anything fundamentally wrong with the AI's design but in order to be effective it really needs more testing with physical robots. As of today we have two working robots. I will start working on RoboCup everyday until the finals to help improve the AI.

The finals for ImagineCup will be a robot sumo wrestling contest. This will probably be similar to the setup for round 1 of the contest except this time we will be working with physical robots instead of a simulation. We will get a total of 24 hours to code the AI.

Wolfram|Alpha Fail

I was playing with the sequence continuation feature in Wolfram|Alpha because of its similarity to my pattern recognition tool. Surprisingly, one of the sequences I entered consistently causes Wolfram|Alpha to throw an error message:

"I'm sorry Dave, I'm afraid I can't do that..."
Wolfram|Alpha has temporarily exceeded its current maximum load. Please try again soon.

The sequence which causes this is 0,1,1,0,1,...

Other variations of the sequence do not throw an error:

0,1,1,0,1,1,...
1,1,0,1,1,...
1,0,1,1,0,1,...

I tried doing some Googling to see if any other queries have been found which consistently throw an error, but didn't find any. It would be neat if I am the first one to find such a query. I wonder if every time I submit that query I am actually crashing one of their servers...

Irony

Cairo

I am a finalist for the Robotics & Algorithm category of Imagine Cup! I will be going to Cairo. I am going to check with Imagine Cup whether the tickets they buy have to be roundtrip. If not, that will enable me to attend RoboCup in Austria as well. The contest dates overlap, so if I am attending both I will need to leave RoboCup early.

Wolfram|Alpha

Wolfram|Alpha is awesome.

Update

See previous post.

• Imagine Cup: I submitted my entry and got a perfect score. Whether or not I get to go to Cairo now depends on how they break ties. Since it wasn't difficult to get a perfect score there will probably be many people competing for the top six positions.


• AIspace video: Video is finished! We are competing in the one minute category.


• Temporal neural networks: New version released at http://byronknoll.com/pattern.html. I haven't set up the database to collect pattern data yet. The neural network is initialized randomly when it loads.


• I migrated my webpage from Google Pages to UBC CS hosting and bought a domain name from Go Daddy.

Hotmail/Gmail/Google Pages

After having used Hotmail for the last several years, I am finally trying to switch to Gmail. I found this useful guide that shows how Gmail can automatically import all old emails from Hotmail and forward incoming messages. I started the process over a day ago but the import process is only about half finished (apparently it takes a long time to import ~10,000 emails).

Google Pages is shutting down. Their new web hosting service is called Google Sites. Google Pages has been a perfect host for my webpage, so I am pretty upset that they are stopping the service. Google Sites definitely does not have the features needed for my webpage. Can anyone recommend a new (preferably free) hosting service I can use?

Summer Projects

• RoboCup: Our team somehow managed to qualify in the small size league for RoboCup 2009. I have been working on the AI. We still have a ton of work to do before we are ready for the contest. Hopefully I will get to go to Austria for the event.


• Imagine Cup: I am in round two of the robotics and algorithm contest. There are over 200 people in round two and only six people advance to round three. The first round was a sumo simulation. The second round is a mars rover simulation. I can get a perfect score in the second round. Since I'm sure over six people will get a perfect score, the tie breaker for the top six spots is "Functional Completeness and Complexity" (bleh). If I make it to round three, I get a free trip to Cairo.


• Netflix prize: Now that I have actually taken a machine learning course, I have a few new ideas to try out. I think I will continue trying to use neural networks, mostly because I feel like I can't compete with the algorithms that the top contestants use.


• AIspace video: I am working on a short video of AIspace for the AAAI video competition.


• The Bootstrapped Learning Cup: an AI contest taking place later this summer.


• Physics based puzzle game: see previous posts.


• Temporal neural networks: I have made a new version of my pattern recognition program. The new version can predict patterns of arbitrary lengths (not constrained by the number of memory layers). I will post the new version on my website when I have some free time. I might also put a database on my computer that automatically collects data from the applet. This would allow the neural network to learn from patterns from all previous users. I got a network to successfully count from 0 to 100 in binary based entirely on pattern recognition (input: 011011100101110111100010011010...)

Theft Attempt #2

Once again somebody tried to steal my bike. This time the theft attempt completely mangled the bike lock so that it was impossible to open. I managed to convince housing that it was my bike and they opened it with a motorized saw.

Lock #1

Lock #2

Daily Life

[link]

Puzzle Games

Since my post about physics-based puzzle games, I have played a few other puzzle games which deserve mention. Right as exam period was starting I decided to buy a new PS3 game (which seemed like a good idea at the time). It is a physics-based puzzle platformer called LittleBigPlanet. The gameplay itself isn't revolutionary, but I found the multiplayer mode and online user-generated content to be extremely fun. The game has a level creator so anyone can publish their own content. I designed a puzzle which I consider to be fairly challenging. It involves constructing a staircase to get over a wall. There are a few tricks to constructing the staircase such as how to move/rotate blocks and how to make the staircase stable. So far only six people have played the level and only one person has solved it (me). It has a rating of 2 out of 5 :(.

Yesterday I got an amazing game called Braid. The puzzles in this game are brilliant. They are based on controlling the flow of time. I had a hard time following the story though, and the ending didn't make any sense to me. I think it was intentionally ambiguous.

Two other puzzle games I played recently I downloaded from the PlayStation Store on my PS3. The first is called Echochrome. It is based on the artwork of M. C. Escher and involves tricks of perspective. The second is a game called Flower. You control the movement of flower petals by tilting the PS3 controller to change the direction of the wind. The graphics in the game are beautiful.

All four of these games have incredible music that really enhance the gameplay experience. In general I am usually disappointed with the quality of music in video games. Two series in which the music made a lasting impression on me are Final Fantasy and Myst.

I am still planning on making my own puzzle game this summer. I have been keeping track of what aspects of the various puzzle games I have been playing work well. I will post updates on the game's development on this blog.

This semester I only have four exams (which is the fewest I have ever had). I think my first three exams went really well. My last exam is on Monday.

GTA

After I got back from an exam this morning I got a call from the residence front desk informing me that somebody broke into my jeep. Luckily there wasn't anything valuable inside. On the driver side door there are large dents near the locking mechanism. Apparently the thief couldn't get in through this door, so went to the passenger side door and completely removed the locking mechanism. I'm glad that the entire jeep wasn't stolen. The battery is dead, so any attempt at hotwiring would have failed. The damage should be completely covered by insurance. The theft attempt might have been due to the boxes I keep in the back of my jeep. Although they are empty, I'm sure the thief was motivated by the hope of getting computer+monitor+PS3+printer. In the future I will be more cautious on where I put empty boxes.

ACM World Finals

The results for the ACM-ICPC contest have just been released. UBC came in 34th, solving four problems. MIT did the best out of North America, coming in 7th (solving seven problems). Waterloo did really well, coming in 10th. Last year UBC came in 30th.

Grad School

I have finally decided where I will be going for grad school. I will be staying at UBC for my master's degree. I was accepted at four out of the nine places I applied. I was hoping to be able to try a new university for my master's degree, but UBC is one of the best out of the places I have been accepted for AI/machine learning. My first choice in Canada was Toronto, but unfortunately I got rejected there. Hopefully during my master's degree I will be able to strengthen my application so that I can get accepted into a good school in the US for my PhD.

The entire process of applying to grad school took a lot of time (and money). It involved taking the GRE, researching schools, applying for scholarships, getting references, etc. The process should be much easier when I apply for my PhD two years from now since I have already done the majority of the work. The application process was cheaper than I was expecting because luckily I didn't have to pay any application fee for Alberta (scholarship) and Berkeley (unknown reason). For my PhD applications I'll probably apply to fewer universities to reduce the time/cost requirement.

BattleCode Tournament Results

A few minutes ago the results from the BattleCode Open Tournament were released:

Top Teams

* 1st place: I for one welcome our new Team 207 overlords
* 2nd place: We'll do it live
* 3rd place: gtg ice skating lessons
* 4th place: My other language is english
* 5th place: Little
* 6th place: JIT In My Pants
* 7th place: When you wish upon Astar
* 8th place: Yellow Submarine

Non-MIT Teams

* 1st place: Bad Meme
* 2nd place: KeepItSimple
* 3rd place: Villanova

Notable Non-MIT Universities

* 1st place: University of British Columbia
* 2nd place: Villanova
* 3rd place: University of North Carolina (Wilmington)

I was a member of KeepItSimple. As expected, MIT teams completely dominated the contest. Bad Meme and KeepItSimple are both UBC teams, so I am proud that UBC is the next best university. I know that our team could have done much better if we had more time to work on it. I am planning on competing again next year, so hopefully next time we can challenge some of the top MIT teams!

Math Teacher

[link]

Physics Puzzle Games

For the last couple of weeks I have been obsessed with physics-based puzzle games. Physics simulators allow the creation of complex puzzles which can involve the interaction of many simple components. There are often a variety of ways to solve a given puzzle. I have tried out a large number of games in this genre (both good and bad). Some of my favorites include:

- Crayon Physics
- Zany Doodle
- Gish
- Armadillo Run
- Fantastic Contraption
- World of Goo
- Switchball

Another great thing about this genre is that it doesn't require a large development team to make a successful game. Most of the games that I listed above were made by a single developer. I have decided that this summer I will try making my own physics-based puzzle game. There are already a variety of open source projects I can use to help development. For the physics engine, I can use Box2D or Chipmunk. For the graphics I can use OpenGL or Cairo. The game will use 2D vector graphics. One idea that I had for the gameplay is the creation of elaborate deathtraps to kill superheroes. "Deathtrap" seems like an appropriate title for the game. I plan on making it open source.

Storm the Wall

UBC has an intramural sports event called "Storm the Wall". It is a five person team relay which includes a swim, sprint, cycle, and run. At the end of the event the entire team climbs over a 12 foot wall. I joined a team of Computer Science students doing the event. I did the cycling portion of the race. Due to a mistake in our team registration, we competed in the "CoRec" category which requires two females in order to compete. On Tuesday we had our first race and came in fourth with a time of 17:16. Despite the fact that we competed with five males, nobody disqualified us and we advanced to the semi-finals. Today we finished the race in third place with a time of 16:36. In today's race we had one female, but this time they noticed and we were disqualified.

PS3 Audio

Today I finally figured out a way to improve the audio output of my PS3. I have been struggling since January trying to accomplish the simple task of listening to PS3 audio on my headphones. The problem comes in trying to convert the RCA stereo signal into TRS for my headphones. The local dollar store has a great selection of cheap (about three to four dollars) audio connectors and converters. Its a good thing these components are cheap because I have encountered basically every combination of audio problems imaginable. The most common problem is that I can only get a single channel of audio output in the left channel of my headphones. With some additional components, I can convert the stereo signal into a mono signal, so that both channels play in only the left channel of my headphones. For the last two months I have been using the mic and headphone jack of my computer to convert the mono signal so that it plays on both channels of my headphones. The problem with this solution is that the conversion process results in a large reduction in sound quality. Surprisingly, in Windows the sound quality is noticeably better than in Linux.

My new solution bypasses the need for a computer. I'll explain my setup in case anyone else has this problem. I first convert the two RCA channels into a single TRS stereo connection using a 2 female RCA to 1 male TRS converter. The real trick comes here: using a normal female TRS to female TRS connector to plug in my headphones does not work since this results in audio only in the left channel of my headphones. Instead, I am using a 2 female TRS to 1 male TRS connector, except leaving the male TRS unconnected. Perhaps using cheap components has been the cause of all the problems I have been having, but I am thrilled to finally have high quality stereo audio.

In other news, this summer I will be working in a bioinformatics research lab on campus. It is called the Tria Project and studies mountain pine beetles. Should be fun!

Pinocchio Paradox

"My nose will grow now"

Erdős Number

Thanks to Jackie for pointing out that I have an Erdős number of at most four:

Byron Knoll -> David Poole -> Kellogg Booth -> Maria Klawe -> Paul Erdős

Robotics

I was at an interesting presentation today by Andrew Ng about the STanford Artificial Intelligence Robot (STAIR) project. STAIR is a robot which integrates many fields of AI in an attempt to accomplish tasks which require a broad range of skills and intelligence. It is currently capable of fetching items in an office environment based on spoken commands. Although this may sound like a simple task, it requires integration of recent advancements in fields such as computer vision/object recognition, machine learning, planning, speech recognition, etc. The robot needs to be able to understand speech commands, navigate through offices, open doors, recognize objects, and pick up objects, none of which are easy to accomplish for an AI. One of the themes of the talk was that we are on the threshold of robots being capable of accomplishing tasks which may actually be useful for the average person. We were shown a video of a robot (teleoperated by a human) performing tasks such as unloading a dishwasher, vacuuming and cleaning a room. Robots are mechanically capable of performing useful tasks. All that remains is making them automated.

Andrew emphasized that in order to make progress in robotics we need to focus on lower level tasks in order to make robots less specialized for a single domain. While I definitely agree with this, he was referring to lower level tasks such as recognizing/grabbing objects and navigating. I think even these are still at a level much higher than what we should be focusing on. For example, take the task of trying to get depth information from a monocular image (see: http://make3d.stanford.edu). Understanding the 3-dimensional structure of the world is important for robots. Humans can use a variety of cues in order to get this information such as texture, color, haze, defocus, etc. In theory, all of these cues could be entirely learned from patterns in visual experience. Instead of manually implementing these cues, robots should be learning about the world themselves. Predicting and recognizing patterns in data is a fundamental task which can be applied to any AI problem. If we could design an AI which is capable of performing this one task well, all of the other higher level problems will be solved.

Robot Sumo

Yesterday I submitted an entry for the first round of Imagine Cup: Robotics & Algorithm. The first round involves programming the AI for a simulated sumo match between two iRobot Creates. Each robot has a webcam, two bumper sensors, and four IR sensors on the bottom to detect when it is over the outer circle. Here is a simulation of a match in Microsoft Robotics Developer Studio (my AI controls the blue robot):



One thing I dislike about this contest is the fact that the physics engine makes designing a more advanced AI almost completely pointless since when two robots are pushing against each other it is about a 50-50 chance that one will end up below the other and able to push it outside the ring. I tried creating a more advanced strategy to avoid this problem by ramming the other robot and backing away repeatedly, but this just gave the other robot an advantage. The strategy that I ended up submitting has a few tricks such as avoiding repetitive behaviors and randomly choosing between possible actions. However, modifying the AI didn't seem to have any affect on its performance during the matches. Since the matches happen in real-time simulation, it is impossible to simulate a large enough sample size to determine if one strategy is actually superior to another.

I have registered in a team to compete in BattleCode, a programming competition hosted by MIT to design a computer game AI. We haven't started working on it yet, but it looks like it should be a fun project.

Data Compression and Machine Learning

There is an interesting relationship between data compression and machine learning. Any data compression algorithm can be used to perform pattern recognition. This can be done by simply comparing the file size of two independently compressed files to the file size of compressing them together. In other words, compare the size of (compression(A)+compression(B)) to compression(A+B). If the two files contain common patterns, then compression(A+B) will be smaller than (compression(A)+compression(B)). By comparing the relative file size difference using solid compression, it is possible to rank the similarity of different data sets.

In my machine learning course last semester we had an optional project to do binary classification on a dataset with thousands of features. We were given data in a training set which were classified into one of two categories (positive/negative). We needed to write an algorithm to classify test data. To compare the quality of our solution, we were given an implementation of AdaBoost with the following error rates:

false negative rate = 0.1429 (over 350 positive data)
false positive rate = 0.1429 (over 350 negative data)
sum: 0.2858

I used a neural network to achieve a lower error rate:

false negative rate = 0.14 (over 350 positive data)
false positive rate = 0.12285714285714286 (over 350 negative data)
sum: 0.2628571428571429

This morning I tried comparing some different data compression algorithms to see how well they are at binary classification. Using 7z I got the following error rates:

false negative rate = 0.31142857142857144 (over 350 positive data)
false positive rate = 0.2542857142857143 (over 350 negative data)

I also tried using gzip and paq8p. gzip was fast but had a terrible error rate. I think paq8p would have done much better than 7z, but it is extremely slow so I couldn't finish running it on the test set. I assume that in general better (slower) compression algorithms will have a lower error rate.

Existentialism

[link]