Monday, December 21, 2009

Wednesday, December 16, 2009

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.

Sunday, December 13, 2009

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.

Tuesday, December 01, 2009

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]

Thursday, November 19, 2009

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.

Tuesday, November 10, 2009

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.

Sunday, November 08, 2009

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.

Saturday, November 07, 2009

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 :(.

Friday, November 06, 2009

Nort

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

Sunday, November 01, 2009

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.

Monday, August 10, 2009

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!

Wednesday, August 05, 2009

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.

Wednesday, July 29, 2009

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 :'(

Sunday, July 26, 2009

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).

Sunday, July 19, 2009

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.

Wednesday, July 15, 2009

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.

Tuesday, July 14, 2009

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).

Friday, July 10, 2009

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 ^_^

Thursday, July 09, 2009

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.

Sunday, July 05, 2009

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.

Wednesday, June 24, 2009

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.

Saturday, June 13, 2009

RoboCup

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



Wednesday, June 10, 2009

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.

Monday, June 08, 2009

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...

Wednesday, June 03, 2009

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.

Tuesday, May 19, 2009

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.

Tuesday, May 05, 2009

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...)

Saturday, May 02, 2009

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

Sunday, April 26, 2009

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.

Wednesday, April 22, 2009

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.

Tuesday, April 21, 2009

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.

Tuesday, April 14, 2009

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.

Monday, April 13, 2009

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!

Wednesday, April 08, 2009

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.

Thursday, April 02, 2009

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.

Tuesday, March 17, 2009

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!

Thursday, February 19, 2009

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

Monday, February 16, 2009

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.

Tuesday, January 06, 2009

PS3

I installed Yellow Dog Linux on my PS3. I tried running my vectorization program on it and was pleased to see that it runs about 50% faster than on my desktop. Here was the output (with 250 triangles and 200 iterations):

Monday, January 05, 2009

India Trip

I got back from my trip to India yesterday. Overall I had a great time. I had some problems trying to get into the country however. In ignorance, I assumed that I could get a tourist visa on arrival. This was not the case. When they discovered that I did not have a visa, they immediately tried to deport me. I was given two options: either fly to Sri Lanka in an attempt to get an Indian visa, or fly back to France. I was leaning towards the Sri Lanka option, but after lengthy negotiation I discovered a hidden third option. Several hours later I was issued a temporary landing permit. This allowed me to stay in India for three days. In those three days I visited the Bureau of Immigration and got an extended exit endorsement until the end of my trip.

I spent most of vacation relaxing at my parent's house by the beach. We did some exploring along the coast between Chennai and Mahabalipuram. We found a cool place with a network of pools surrounded by rock cliffs. After Christmas we took trip to Kerala for a few days. We stayed in Kumarakom and explored the backwaters, lake Vembanad, and a bird sanctuary. I was hoping to spend a few days on a house boat, but unfortunately we were visiting at the peak of tourist season so it was impossible to reserve one for a decent price. We took several boat rides and even rented our own canoe. Kerala is an incredibly beautiful place so I made sure to take plenty of pictures.

For Christmas I got a PS3. I managed to get video output to my monitor after buying an expensive HDMI to DVI cable. I have been having trouble trying to get the audio working. There are three audio output options: RCA, TOSLINK, and HDMI. I have a cable which converts RCA to a male TRS connector. If I want to get audio to my speakers/headphones, I need a female connector. Using the audio in/out ports of my computer would do the trick, but unfortunately I am having sound card driver issues in Ubuntu. If I fail at fixing the driver problems I'll need to buy another cable.

On my way to India I worked on a new version of Swarm. On the way back I worked on a vectorization program (see this blog entry). Neither of the projects turned out as well as I was hoping. I have now abandoned releasing the new version of Swarm since it isn't much of an improvement. The vectorization program is slow and does not seem to do a very good job. Here is the Mona Lisa with 100 triangles:

Original image:Iteration 10:Iteration 50:Iteration 150:It took about one hour to get to iteration 150 and its rate of improvement seemed to have leveled off. I assume that 100 triangles can represent the Mona Lisa much better than this solution, so I am going to work on improving both the efficiency and the effectiveness of the program.

I have finally finished reading Anathem. Overall I thought it was a great book, although I got really bored by some of the long philosophical discussions. Since I didn't bring GEB to India, I have started reading A Game of Thrones.