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).
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.
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.
Thursday, July 16, 2009
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.
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 ^_^
"
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.
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.
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.
Subscribe to:
Posts (Atom)