Tetr.js

Just after starting. The algorithm is playing through the first, randomly generated, generation of bots.
Generation 3. It's getting better!

What it does

I don't like playing Tetris. The game is dull, monotonous, and ultimately self defeating. And to add insult to injury, I'm not even particularly good at it.

So, like any good aspiring engineer, I decided to take the lazy approach, and built a JavaScript-based AI to play it for me. Tetr.js uses a machine learning algorithm to continuously refine the weightings of the parameters which define a good move.

Animated tetris gif

So, Machine Learning?

I knew nothing about machine learning, so I based the design off what I knew about real-world evolution of organisms. The genetic algorithm contains 3 key features:

Inheritance

Each candidate algorithm inherits each of its properties from one of its two parents, with a slightly higher probability of inheriting from the higher-scoring parent.

Scarcity

After each generation, the lower performing half (5 / 10) of the candidates is killed off. The remaining 5 candidates "reproduce" in every possible combination, for a total of 4 + 3 + 2 + 1 = 10 new candidates for the succeeding generation.

Random Mutation

When a trait is inherited, it has a small chance of the trait being randomly adjusted higher or lower by a small amount. Also, there's a very small chance of the trait being randomly adjusted by a large amount. The idea it that positive mutations tend to persist and survive, and the negative ones die off.

How It's Built

It's all Javascript and jQuery, and runs on the client side, in the browser. That means you get a blank canvas every time you refresh the page, and get to watch your optimal Tetris algorithm being evolved from scratch.

Challenges

The biggest problem is that the better the algorithm gets, the longer it takes to test, and so more time passes between generations. Also, there's no good way to tell if a candidate is truly immortal, except by waiting around to see what happens. Still, seeing as a standard game of Tetris involves clearing 40 rows, and the bot's record is going on 80,000 rows, it's good enough to demonstrate the concept.

What I learned

Machine learning, or at least, my own best stab at it. But other than the challenges of implementing such a complex program using client-side JavaScript, probably the most valuable thing I learned was how, if stuck on how to implement something, it's usually best to model it off of some kind of physical analogue; in this case, biological evolution.