Tetris AI Algorithms

Hi,

I once developed a tetris playing 'ai'. I'm quoting it on purpose, because it actually was a relatively simple algorithm. On average, it would die after ~50k lines made. Here's how it works:

- your playing field has a number edges. The ground and sides are edges too.
- your current tetris block has edges.
- each edge is one (1) tetris unit wide and long. Normal tetris blocks consist of 4 blocks, but this algo also works with random tetris blocks.
- for any given rotation and position of your block, drop it downwards
- when dropped, count the number of edges on your block that are touching the edges of block already dropped or those which are touching the wall or ground.

If you implement this algo, you will see it will start building in 'V' shaped formations of blocks. To avoid it building too much formations on the sides, penalize height. So for any given rotation and position of blocks, the score is this:

(number of edges touching) - (average block heigth / total height).

This algo is by no means perfect, but believe it or not, that's an advantage. Because it makes 'mistakes', you will also get some gaps in your formation. This will promote dropping blocks that eliminate several lines at once, resulting in more points.

Hope this helps,

Edo

BTW: if you want something more advanced, you could come up with some scoring criteria for your blocks, like

- height
- number of edges touching
- width
- number of empty gaps made
- number of edges touching a wall

Your overall score for dropping a block at a given rotation and position will then be:

score =
(weight1 * height) +
(weight2 * number of edges touching) +
(weight3 * width) +
(weight4 * number of empty gaps made) +
(weight5 * number edges touching a wall);

All weights are floating points between -1 and 1.

You can encode these weights in a genome (or was it chromosome?), and have a GA evolve these weights by letting a pool of chromosomes play against eachother for 10 games or so. The 'least' strong chromosomes will be killed, while the stronger weights will cross-over and mutate.

just some thoughts,

Edo

Quote:

Original post by edotorpedo - number of edges touching Edo

We were using this one and this one only and it was working very good for us.

this is one of those problems that you can create the AI strategy to use the same strategy you use. when i play tetris i use the strategy of building up (and fitting) blocks on the left side first. they reach rather dangerously high. but i work my way to the right when i can, fitting the blocks in the blocks as high as necessary to the far left trying to leave no gaps. so after a while the whole area looks similar to a somewhat straight hill sloping steeply to the right, leaving me several areas to fit almost any piece given to me without leaving more than even a couple of gaps. this strategy really works great, until the speed of the falling blocks increases, which is just plain hard anyway.

i would almost suggest representing the playing field as a 2D matrix full of 0's and 1's. in my case, i would start off building up blocks to the left with a general rule to minimize unreachable gaps. and then when the AI was given a new piece it would identify its shape and identify which one of the surfaces below (and preferrably to the left side) would minimize gaps for each of the 4 rotations.

this is just peusado of what i would do. i could come up with some math formulas that i would use that properly weighs height of heightest block, potential for clearing a certain row, best fit position, etc. but i think it would be better for you to approach this using your own strategy. if you just happen to play tetris like i do then i'll be happy to help you. but like i initially suggested, this is one of those simplified problems that you could just make the AI do exactly what you would do in that situation. if it comes to it, write down the steps of how you would play tetris, convert it to how an AI would come to those conclusions of each step, and write the code.

or if all of this is too complex for your liking, i'm sure there are simpler algo's out there.

This would be an interesting problem for a neural network... it is overkill if you're just creating a single AI, but if you had it learn from 50 different players it would adapt each person's style... :)

You know you've written a good AI when it can win at Bastard Tetris!

http://www.happypenguin.org/show?bastet (Somewhere out there theres a Windows port too)

Thanks for your advices. You really gave me some clever ideas.
My current bot uses this formula:

merit = rowsEliminated;
merit += -1*cellsOccupied;
merit += -5*holesShadowed;
merit += -4*pileHeight;

There are some minor issues with it but overal it does
fine. The NN ideas seems interesting. Bastard Tetris
looks promising :).

My project is open source. After I release it
I hope there will be enough people willing to write
their own Tetris AI.

[Edited by - dimovich on May 5, 2006 3:10:12 AM]

Couldn't you develop a recursive possibilities-exploring algorithm similar to the algorithm used to look ahead n number of chess moves?

Well, not similar to a chess algo, as that is a turn based game. And you only know the next tetris block that is going to fall, not the one after that.

So you can only recurse 2-deep (one for the current block, one for the next block). But by using my algo and recursing, I think you can achieve reasonably decent results, say ~100k lines.

Let me know if you finish your clone.

Edo

Quote:

Original post by edotorpedo You can encode these weights in a genome (or was it chromosome?), and have a GA evolve these weights by letting a pool of chromosomes play against eachother for 10 games or so. The 'least' strong chromosomes will be killed, while the stronger weights will cross-over and mutate.

A friend and I did this for a project in one of our AI classes. We built a simple Tetris repesentation (I say representation because it wasn't a game, you couldn't play, or even watch, but we could spit out the board when we wanted to in ASCII form :) ), and the used a GA to weight an evaluation, much like you described.

Our work was motivated by Colin Fahey... who's site seems to be down right now, but if you google for him you'll find all kinds of stuff. Using 3 or 4 features we got an agent that could play up to 100K lines, but on average much less than that.

We didn't spend a lot of time hand modifying the weights, but my point is that an evaluation function like that works pretty well for Tetris, and you can have some fun with learning algorithms with it too :).

Quote:

Original post by edotorpedo Well, not similar to a chess algo, as that is a turn based game. And you only know the next tetris block that is going to fall, not the one after that. So you can only recurse 2-deep (one for the current block, one for the next block). [...]

Actually, you can do better than that. You define whatever your utility function is (a combination of height and holes, for instance). Let's call the current block block0, the next block (known) block1, the one after that (not known) block2, etc. The algorithm goes:

Loop over each position where you can place the block0 {  Loop over the 7 possible shapes for block2 {    Find the best utility you can get by placing block1 and block2.  }  Take the average of those 7 utilities, and that's the utility of placing block0 in that position.  Keep the position that has the maximum utility so far}

This way, you are thinking 3 moves ahead. This can be extended using a recursive formulation to think even further ahead, although the branching factor of 7 is going to kill you quickly.

An interesting place to use neural networks would be in the utility function. You can try to define a bunch of things that might be relevant for the utility function, like maximum height, minimum height of a column, number of gaps, number of blocks on top of gaps... Then you build a neural network that tries to predict, using those numbers, how long you are likely to survive, or how many more points you are likely to score, or whatever else is what you really want to maximize. Now that you have a smart playing bot, you can generate plenty of data points to train your network. So start with a simple hand-made utility function and gather training data for the network with it. After a while, you can train the network, replace your utility function with the new network and start all over again. After a few iterations of this process you should have a really good player.

Too bad I don't have time these days to try this type of thing myself!

[Edited by - alvaro on May 8, 2006 11:26:27 PM]

I'll take my chance and show you what I've done so far.
The game is ~60% complete. I haven't written any manual
on the built-in scripting language... I'll do this later.

I hope this is helpful.

Here is the link: http://p4p.skynet.md/files/359/netrix_gd.zip

Damn, what a great feeling :)...

My bot managed to score 80k completed lines. And it is a simple, 1-piece algorithm, whith no advanced stuff in it.