So the past few weeks have been quite hectic, having to relocate from the far East (Singapore) to the far West (California) along with starting my internship at TellApart.

Within a span of eight days, I surfed through six cities in five flights over four continents. Here’s the timeline:

• May 7, 2011: Singapore, Singapore ✈ Dubai, UAE ✈ Cairo, Egypt
• May 14, 2011: Cairo, Egypt ✈ Paris, France ✈ New York, USA
• May 15, 2011: New York, USA ✈ San Fransisco, USA

My one week visit to Egypt marks my first visit after the January 25th revolution. Traces of the revolution are certainly visible everywhere you go – stickers on street carts saying “January 25″, spray painting on walls and bridges denouncing Mubarak and his regime and barbed wires around the Maspiro Television building. There was also a protest to express solidarity with Palestine in Tahrir square on Friday, May 13th. Hopefully political and economical improvement would be as visible in the near future.

For the first ten days in California I stayed at USA Hostels near the Civic Center in San Francisco. The commute time to work was around 75 minutes. One of the weekends the hostel was fully booked and didn’t have room to accommodate me. Thankfully, Stan Chen, my workmate, let me stay over at his place then. I have now settled in a house a few blocks away from work.

I am really enjoying my work at TellApart so far. In many ways it was exactly what I was aiming for this work term. It’s a great mixture of really smart people to work with, a startup environment, and serious scalability issues to deal with.

Aside from that, I really don’t know what else to say. In fact, I have no idea why I am writing this post right now. Off to bed.

Update: Full source code and implementation now available here!

This algorithm is part of a project I was working on last term as part of my Artificial Intelligence class. This algorithm, which I will be referring to as “El-Tetris”, is an algorithm for playing Tetris by inspecting only one piece at a time (as opposed to two or three pieces in some variations of the game). It is based on Pierre Delacherie’s Tetris algorithm, which is known as one of the best one-piece Tetris playing algorithms.

Before discussing the details of the algorithm, let’s briefly look into how you, a human player, would play tetris.

When you play tetris, you are faced with two decisions every time you are given a tetris piece:

1. Where to position the piece
2. Which orientation of the piece to play

Naturally, you want to eliminate as many rows as possible and maximize your score. To accomplish that, you would (subconsciously) be doing the following:

while the game is not over:
  examine piece given
  find the best move possible (an orientation and a position)
  play piece
repeat

What would be the best possible move then? You would usually try to eyeball certain features to help you determine that. You might, for example, ask yourself these questions:

• If I were to play the move, would that create holes in the game board?
• If I were to play the move, how many rows would I clear?
• If I were to play the move, what would be the height of the highest column?
• … and so on

That’s exactly what El-Tetris does. For every given piece, it evaluates every possible orientation and position against a set of features. The move with the best evaluation is the one that is played.

Read more