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]

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

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.

Flight Cancelled

To save money I booked a bizarre flight path to India:

Seattle -> Vancouver -> Hong Kong -> Chennai

This means I had to take a bus from Vancouver to Seattle in order to fly back to Vancouver. In addition, the flight leaves in the morning so I had to stay in a hotel overnight. I couldn't just cancel the flight because that would cancel the connecting flights as well.

The flight from Seattle to Vancouver was cancelled this morning due to mechanical problems. There were no other flights to Vancouver in time for my connecting flight, and taking a taxi/bus probably wouldn't have made it in time either (especially with the snow). The only option was book a completely different flight path which leaves tomorrow:

Seattle -> Paris -> Chennai

Projects

Now that exams are finished and I have submitted most of my grad school applications, I should finally have time to work on some projects I have been planning:

• Vectorization using stochastic local search: I read a cool blog entry about evolving a picture of the Mona Lisa using only 50 polygons. Inspired by the results, I think it would be cool to use stochastic local search to convert an arbitrary image to vector graphics. I will add a parameter to choose the number of polygons. I will try to animate it to show the progress of the algorithm as it optimizes the image representation in real-time.
  
  
• A new version of Arlisy: A generic neural network framework which can be applied to a variety of problems. It will have the ability to detect temporal patterns. I also plan on implementing an attention control mechanism which allows the framework to focus on a subset of its input, similar to the role that attention plays in biological perception by concentrating the use of mental resources on a particular aspect of the environment.
  
  
• Netflix prize: I haven't made much progress since last summer. I am going to try implementing singular value decomposition to combine with my neural network approach.
  
  
• A better version of Swarm: I know the algorithm I used for finding nearest neighbors in the old version can be made much more efficient. This will allow larger swarms to be simulated in real-time. I'll try adding some more advanced behavior rules as well.
  
  
• I am considering competing in the Robotics & Algorithm category of Imagine Cup 2009.
  

Exams!

Once again it is exam period, so if you are in need of some distraction here are two neat flash games I've found:

Auditorium: awesome concept for a puzzle game. Its a shame there are so few levels in the demo.

99 Bricks: my record is slightly over 700.

I have two exams tomorrow. I should really be studying right now.

Sudoku Fail

This was printed recently in the local newspaper.

Pie Chart

Mmm... π!

2008 ACM-ICPC Pacific Northwest Contest

Yesterday I competed in the regional ACM programming contest. There were 85 teams competing in our region. Here is the final ranking for the top five places:

1) Stanford
2) Stanford
3) University of California, Berkeley
4) UBC ^
5) UBC *

This was really frustrating because only two teams advance from a region to the world final (which is in Sweden this year). Since only one team can advance per university, UBC was only one spot away from advancing. There is actually still a chance that UBC might get to advance however, since there is a wildcard slot. I was on the UBC * team. We were ridiculously close to solving another problem in the last few minutes. If we had solved it, we would have jumped to 2nd place. We made a submission with about two minutes left which failed because it took too long to execute. However, with a minor modification to the code (just one or two lines) our solution probably would have run under the time limit. Both of my teammates were doing really well during the contest and did the majority of the work. They will both be at UBC next year, so I'm sure that their team will do really well at the next regional. Here were the results from last year's regional:

1) UBC ^
2) UBC *
3) Stanford
4) Simon Fraser University
5) University of California, Berkeley

Grad School Applications

I have finally decided on a list of schools I will be applying to:

University of California, Berkeley
Carnegie Mellon University
University of Washington
University of Illinois at Urbana-Champaign
University of Waterloo
McGill University
University of Alberta
University of British Columbia
University of Toronto

Most of the applications are due mid-December. I have a ridiculous amount of work due in the next two weeks, followed by final exams (which are all within 7 days). Hopefully I'll manage to submit the applications without having to sacrifice studying time. I will be so happy once finals are finished, instantly switching between having an overwhelming amount of work to having absolutely no work at all. Over Christmas vacation I will be traveling around southern India.

World of Goo

My new favorite game. [link]

Hotmail

A few hours ago I was automatically "upgraded" to a new version of Hotmail. I am not picky about what additional features an email client has or how stylish the interface is as long as I can conveniently read/send emails. I have had my Hotmail account for about five years. When Gmail came out I decided not to switch since I didn't want to go through the hassle of changing my contact information. With the newest version of Hotmail I am finally considering making the switch.

When logging into Hotmail I am greeted with this page:
It tells me to upgrade my browser despite the fact that I am using Firefox version 3.0.3, the latest version for Linux. After logging in it takes me two clicks to reach my inbox (which is two clicks too many in my opinion).

This is what happens when I try to compose an email:
Notice that the text formatting buttons are grayed out. I tried clicking on the whitespace below that panel to find that there is no text box. That's right, there is absolutely no way for me to send emails because I don't have any way to enter text. I am probably not the only person with this problem. With the most critical functionality of Hotmail broken, I have no choice but to switch providers.