El-Tetris – An Improvement on Pierre Dellacherie’s Algorithm

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.

Continue reading "El-Tetris – An Improvement on Pierre Dellacherie’s Algorithm"

Terima Kasih Indonesia

As my exchange term here in Singapore is approaching its end, I thought it might be worth backpacking just one more time before getting sucked into the funnel of final exams. This time I went on a five day trip to Indonesia with Zhang Jing, my neighbour here in Kent Ridge Hall, and Nick Yang.

We were trying to see as much of Indonesia as possible within these five days so our schedule was really tight. Knowing how much I love bullet points, these are some of the places that we visited (in chronological order):

  • Mount Bromo, an active volcano in east Java
  • Surabaya, Indonesia's second largest city
  • Sampoerna's Tobacco Factory
  • Borobudur, the largest Buddhist temple in the world
  • Yogyakarta City
  • Kraton, the palace of the Yogyakarta Sultanate
  • Jakarta, Indonesia's capital and largest city
  • University of Indonesia
  • Masjid Istiqlal, the world's third largest mosque
  • National Museum

Other "side accomplishments":

  • Took four flights in five days with four different budget airlines (Jetstar, Batavia, Air Asia and Tiger Airways)
  • Hiked up a mountain peak across from Mount Bromo to see the volcano at sunrise
  • Horseback rode up to the crater of Mount Bromo (lots of ash)
  • Rented motor bikes and drove around the villages in Borobudur
  • Attended a lecture on sequential circuits at the University of Indonesia (taught in Indonesian)
  • BONUS 1: Did not get pickpocketed!
  • BONUS 2: Stayed within budget!

During the trip, I only managed to learn the Indonesian word "terima kasih" meaning thank you. For all the great adventures that you offered me, terima kasih Indonesia.

Done Chinese 1!

After spending six hours every week in Chinese lectures for the past twelve weeks, today the course has - sadly - come to an end. I was fortunate to have both a lovely teacher, Ms. Lin Chiung Yao, and awesome classmates. I definitely learned a lot from both Lin Laoshi (Laoshi is Chinese for "teacher") and from my classmates. Throughout the term we learned approximately 180 chinese characters and 150 phrases to communicate in simple daily situations. Will try to practice whenever I can!

Learning Chinese is an eye opener for me in many ways. Besides the obvious intent of learning Chinese for the purpose of communicating with Chinese people, there are some insights that I can see. Let me give you some examples:

1. Tones

Being both an Arabic and an English speaker, the concept of tones was very new, and very strange, when it was first introduced to me. It turns out that the pitch in which you pronounce a syllable determines the word that you intend to say. To see what I mean, listen to the audio clips in the table below. The four rows in this table refer to the four tones/pitches that are found in Mandarin Chinese. They are all pronouncing the same syllable, but the pitch in which it's pronounced determines which of the four words below you mean.

 

Pinyin Chinese Character Meaning Sound Clip
mā 妈 mother [audio:http://ielashi.com/wp-content/uploads/2011/04/1.mp3|titles=First Tone]
má 麻 hemp [audio:http://ielashi.com/wp-content/uploads/2011/04/2.mp3|titles=Second Tone]
mǎ 马 horse [audio:http://ielashi.com/wp-content/uploads/2011/04/3.mp3|titles=Third Tone]
mà 骂 scold [audio:http://ielashi.com/wp-content/uploads/2011/04/4.mp3|titles=Fourth Tone]

 

Weird, huh?

2. Culture and Society

In case you didn't know, Chinese doesn't have an alphabet. It is, more or less, a set of characters, the majority of which are based off of pictures. Consider the Chinese character for the word "home" (pronounced "Jiā") and how it evolved over time:

Current Chinese Character In 259 B.C. In 1046 B.C.

Looking at the origin of the character, it is a picture of a house with a pig inside. This gives an insight in what the Chinese consider to be a home (shelter, roof and live stock) at least at the time the character began to be used.

Another example is 外婆 (pronounced "wàipó"), which means grandmother on mother's side. This word consists of two characters. The first character ("wài") means outside, indicating that the grandmother is considered an "outsider" in the Chinese family.

In Arabic we have the saying "من تعلم لغة قوم أمن مكرهم", which roughly translates to "He who has learned the language of people is safe from their mischief". Looking back, I couldn't agree more with this statement. When you learn a language you are not just learning how people communicate with each other, but also how they think.

Sources:

  • http://www.foreigners-in-china.com/chinese-symbol-history.html
  • http://mandarin.about.com/od/pronunciation/a/tones.htm

Acting in Chinese? I think so!

As our Chinese course is nearly coming to an end, we were asked to spice things up a bit by creating our very own short film in Chinese! We had to find a native Chinese speaker and interview him with at least ten questions from the vocabulary we had learnt. Check it out!

While you're at it, checkout the full blog and the making of below (just so you know what we've been through) 😀

I Want That Arabic T-Shirt

A few days ago I attended the TEDxKRP 2011 conference hosted here at the National University of Singapore. The conference was heavily geared towards social entrepreneurship and featured some really interesting talks by well respected speakers from all over the world.

Needless to say, all the talks were very beneficial and enlightening. However, there was one particular talk that caught my attention. Before I dig into that though, let me first give a brief prelude so that you would understand why I became interested in that particular talk.

If there's one thing you should know about me, then it would probably be my obsession with the Arabic language. I immensely enjoy reading Arabic poetry and literature and I am compelled to admire Arabic's beauty and descriptive power. The way the characters are designed and how they are conjoined leaves a lot of room for very artistic works of calligraphy.

Descriptive power and calligraphy are not the main reasons of my obsession with Arabic, however. The main reason is the strong connection binding Arabic, the language, to Arabs, the people. As fractured and divided the Arab world is today be it on the political, economical or racial level, Arabic is one of the very few common denominators that are left.

If Arabic is one of the very few denominators that portray an Arab's identity, then why is it the case that Arabs try to run away from it? Continue reading "I Want That Arabic T-Shirt"

Back from India

I just made it back to Singapore a few days ago after one week of backpacking around India with Jackson Tse and Katie Morehead. I never expected to ever go to India but, nonetheless, it was an amazing opportunity to learn more about the appealing Indian society, culture and history. I am very happy with what we have accomplished during our little trip!

To mention a few of the places we visited:

  • Trivandrum and Cochin in the state of Kerala
  • Mysore and Bangalore in the state of Karnataka
  • Maharaja’s Palace in Mysore (stunning!)
  • Chamundi Temple in Mysore
  • Padmanabhaswamy Temple in Trivandrum
  • Trivandrum Zoo
  • Kathakali Dance Concert
  • Kovalam Beach
  • Bangalore University
  • Psmup Public School in Trivandrum and another public school in Cochin
  • A Muslim Orphanage in Cochin
  • A technology park in Bangalore (where the Google office is located)

Some “side accomplishments":

  • Bathed some elephants with a coconut.
  • Bought and distributed pens and biscuits to students at Psmup Public School.
  • Tried some street food - I can’t remember the name of the dish but it was, more or less, fried chicken skin.
  • Rode an overnight train from Trivandrum to Cochin (had a great conversation with a few Indians on the train).
  • Rode a sleeper class train from Mysore to Bangalore! This is the lowest and cheapest class in Indian trains.
  • Took two domestic flights (from Cochin to Bangalore and from Bangalore to Trivandrum).
  • BONUS - Got pickpocketed!

It was quite interesting to compare and contrast India, Egypt and other places I have seen. Hopefully I’ll have the time to write about some of this in the near future.

Hello World from Singapore

So it’s been quite a while since I posted anything here. The past few months were crazy busy. I am now in Singapore on exchange at the National University of Singapore. I arrived here last Saturday and so far my impressions are very positive. The country is very well organized, well kept and I fell in love with the tropical weather.

I am living in one of the residence halls on campus called Kent Ridge Hall. People here are super friendly and I am learning a lot about Asian culture from them.

I am staying in Singapore for four months. During this period I am hoping to:

  • Become familiar with Asian culture.
  • Learn about the factors contributing to the success and progress of Asian countries and how we can apply this to the Middle East.
  • Explore Singapore and neighboring countries.
  • Learn some Chinese!

I am hoping I’ll have the time to do all this. Especially since I am taking some heavy CS courses including Operating Systems, AI and Algorithms. Will keep you updated on how it goes!

Live Notes

For the past few months I have been involved with the project BigBlueButton, an open-source web conferencing system. That, along with looking into Etherpad's source code, really ignited my interest in real-time collaboration technologies.

I started an open-source project to extend BigBlueButton with real-time document collaboration to the conference's participants. The project is still at a very early stage, but will be out for beta testing in the next release of BigBlueButton.

Before I start ranting about the project, which I am tentatively and temporarily calling it "Live Notes", let me first show you a demo. Continue reading "Live Notes"

Etherpad on Debian/Ubuntu

Since the release of Etherpad's source code last month and I have been really interested in studying the code and algorithm behind Etherpad's realtime editing.

Etherpad's backend is mostly written in Scala. Seeing how Scala is starting to be adopted by many popular online services, it's also worth looking into.

I thought I'd start off by installing my own instance of Etherpad. Unfortunately, the installations didn't quite work for me straight out of the box. After a few quirks, and with the help of this guide, I finally got Etherpad running. I am using Ubuntu 9.10, but the instructions should also work for Debian.

  1. Install Sun Java JDK
    apt-get install sun-java6-jdk

    Note: You need to have Sun's Java as your default. You can verify this by the following:
    java -version
    Java(TM) SE Runtime Environment (build X.X)
    Java HotSpot(TM) Client VM (build 14.3-b01, mixed mode, sharing)

    If you see anything other than what's above (for example, OpenJDK). You need to set Sun's Java as the default JDK. To do so, use the following command and follow the prompt.

    sudo update-alternatives --config java

  2. Install remaining prerequisites:
    apt-get install scala mysql-server libmysql-java mercurial
  3. Paste the following to /etc/profile, and be sure to replace X.X.X with the version of mysql connector that you have installed.
    export PATH
    export JAVA_HOME="/usr/lib/jvm/java-6-sun"
    export SCALA_HOME="/usr/share/java"
    export JAVA="/usr/bin/java"
    export SCALA="/usr/bin/scala"
    export PATH="/usr/bin:/usr/bin:/usr/local/mysql/bin:$PATH"
    export MYSQL_CONNECTOR_JAR="/usr/share/java/mysql-connector-java-X.X.X.jar"
    export JAVA_HOME SCALA_HOME JAVA SCALA MYSQL_CONNECTOR_JAR PATH
    umask 022
  4. Download the etherpad source to /usr/local/etherpad
    hg clone https://etherpad.googlecode.com/hg/ /usr/local/etherpad
  5. Set the environment variables: Again, remember to replace X.X.X with the corresponding version on your machine.
    export JAVA_HOME="/usr/lib/jvm/java-6-sun"
    export SCALA_HOME="/usr/share/java"
    export JAVA="/usr/bin/java"
    export SCALA="/usr/bin/scala"
    export PATH="/usr/bin:/usr/bin:/usr/local/mysql/bin:$PATH"
    export MYSQL_CONNECTOR_JAR="/usr/share/java/mysql-connector-java-X.X.X.jar"
  6. Add your domain to the superdomain section in /usr/local/etherpad/trunk/etherpad/src/etherpad/globals.js. If you will only be accessing it locally (through localhost), you don't need to do this.
  7. Create the etherpad mysql db and privileges:
    mysql -u root -p
    # enter your password when prompted
    create database etherpad;
    grant all privileges on etherpad.* to 'etherpad'@'localhost' identified by 'password';
    quit
  8. Compile the JARs:
    cd /usr/local/etherpad/trunk/etherpad/
    ln -s /usr/share/java /usr/share/java/lib
    bin/rebuildjar.sh

    Edit: As Mihira pointed out in comment #2, you may come across this error when compiling with the bin/rebuildjar.sh:
    Unable to establish connection to compilation daemon. Compilation failed.

    The problem maybe that the server’s hostname doesn't have a entry for 127.0.0.1 in the /etc/hosts file. In that case, add 127.0.0.1 to the /etc/hosts file and run bin/rebuildjar.sh again.

  9. Run the web server:
    bin/run-local.sh
    Note: If you are running a machine or a VM with little RAM, you might encounter this message:
    Error occurred during initialization of VM
    Could not reserve enough space for object heap

    If you see this error when you try to run the web server, it can be resolved by decreasing the size of the needed heap. Edit bin/run-local.sh and change the variable MXRAM from 1G to something smaller (256m should do the trick), then try running bin/run-local.sh again.

    10. That's it! You can access Etherpad locally on http://localhost:9000