Tetris AI

I don't really understand, because in Tetris there really isn't any AI. You simply need to randomly create a piece with a random color and have that piece displayed on the screen. I have a Tetris clone on my webpage you can look at to see how I did it.

www.adamwlarson.com

To create a simple (but fairly effective) tetris player just test the places where the brick would fit and put it in the lowest place. If it doesn't fit anywhere rotate the brick once and try again.

To create a very good tetris player you could use the minimax algorithm.
This works by creating a tree of all possible moves and selecting the path that would result in the destruction of the most bricks. ~Assuming you can see one brick ahead the tree would only be two layers deep.

Sorry, I misunderstood the question :(

Yes, I meant an AI player for Tetris. I forgot to mention that :P

Thanks for the help. I was thinking about that solution, to search for every possible move until I can make it fit somewhere. But it seem too far-fetched.

I think I'll try with the minimax algorithm you suggested. So I need to store each possible move into the tree. Do I have to store the amount of blocks in a row that particular move affect, and then pick the move where the most blocks in a row is? Or something like that?

Hi,

I already made some replies in a similar topic on Tetris AI: view

Tetris AI Topic
You might want to read this first...If you have any questions afterwards, I'll be happy to reply..

Edo

Thanks alot edotorpedo, I'll try to implement your method.

But I don't know if I understand your method correctly. My AI for the moment, weights the number of holes it makes and the lowest position possible. But that tends to make alot of I holes that only the I-block can save.

Could you make a very simple example on one block that is dropped, so I can see how the numbers are retrieved and calculated?

Quote:

Original post by delbogun Thanks alot edotorpedo, I'll try to implement your method. But I don't know if I understand your method correctly. My AI for the moment, weights the number of holes it makes and the lowest position possible. But that tends to make alot of I holes that only the I-block can save. Could you make a very simple example on one block that is dropped, so I can see how the numbers are retrieved and calculated?

Try placing the the block in each position, and then evaluate the board afterwards, rather than the position. What I mean is say you have a blank board, and the first piece is a square, then just put it in the very left and check the board. Things you could check are total pile height, holes, wells, 'flatness/bumpiness', etc (my implementation was based initially on Colin Fahey's work). So for this example height would be 2, holes would be 0, and bumpiness (depending on how you felt like checking this, I just walk along and sum all the height differences) would be 2, wells would be 0, etc.

Now just add up the score with weights for each feature. Say you don't want pile height, so the weight could be -10 or something, everything else is 1 (for this example), so total score would be -18.

Now check the next position and do the same, and keep track of the highest score. Notice there's no reward for lines, this is implicit in the pile height. Basically this method finds the 'least-worst place' for a piece, then just have the AI try to put it there.

The only hard part is finding the weights, as I mentioned in my post in edotorpedo's link a friend and I used a GA to find the weights, but that's not necessary. You can get pretty decent results this way, certainly good enough if you wanted an AI playing along side a player or something.

Does that help?

Thanks Rixter, I understand it now. I was also trying to check the number of lines a certain position will destroy and place the block there, but that ended up with several holes instead. Your version is much better. Thanks again all :D

I saw this thread a while ago and decided to try making some tetris AI just for fun. I get most of the ideas presented, but I am having difficulty finding what moves should be searched. Right now I create my possible moves by rotating the block and then moving it either left or right and then dropping it straight down. This is how most moves in tetris are exectuted and it works ok, but I'd also like the AI to recognize when it could slide a block under another block and I'm not sure how to find the move sequences. I could try searching every possible move, but I'd like a more effecient way of doing it.

That's a tricky one...

I guess it depends how complicated you want the 'moving under other pieces' to be.

At the most simplistic level, you can search X spaces left and right from any point during the descent (or rather, any point in the descent where the bottom of your block is <= the top of the highest block in play). Any of these which don't end up with a 'finish' state can be disregarded as valid moves. This will capture probably 90% of all the possible 'putting pieces under each other' moves you could make, and the overhead on your move calculation routine should not be too great.

e.g

   #  ###                    @@      @@@@@@@@

            #@@   ###@@@@@@@@

What it will miss, is any move which requires more than one rotation of the piece in question during the descent, e.g rotating a L piece to vertical in order to fit it down a 2 space wide gap, and once through the gap, then rotating it to horizontal to slide it under another piece. This would be rather more complex, and I can't think of a simple way to calculate it, short of generating a huge number of moves.

e.g, you won't be able to do this....    #  ###  @@@  @@@    @@@     @@@@@@@@

 @@@  @@@   #@@@  ###@@@@@@@@

Quote:

Original post by SlyKnight e.g, you won't be able to do this.... # ### @@@ @@@ @@@ @@@@@@@@ @@@ @@@ #@@@ ###@@@@@@@@

That's and interesting problem (when I did this we didn't allow sliding (which I believe isn't part of the 'official original tetris rules'), so we didn't have to worry about it). For this particular case, I would think you would amost have to look for valid spots backwards, that is, start from the bottom row and check all positions and rotations and then go up a row. You'd get a lot of positions that have collisions, but that's easy to check for.

Once you found a spot you liked, say the one you have in that bottom picture, I guess you'd have to do some sort of backwards search, like A* your way to the top of the screen and see if you can get it out.

Or if you could detect small enclosures like that one, get it in there sideways and then recursively pretend that's just a small tetris board and see what happens.

If someone does write a Tetris AI that solves this I'd be interested to hear how you do it, and how well it works. Or maybe if I find I have extra time in the next few months I may give it a try myself, cause now it sounds like fun :).

I guess the obvious way to do it would be essentially to expand on the idea I outlined above - instead of just sliding horizontally from each possble height level, generate all rotations *and* slide from each possible height level.

This of course means you are searching the entire tetris move space, so I would think you're going to want to do some pretty heavy pruning, since for any given piece you're otherwise going to have a massively exponential search space. With a sensible pruning algorithm, this could be feasable. The vast majority of moves can plainly be ignored, many will converge into each other and become equivalent, etc.


A better idea though, might be more along the lines of what you've suggested. I'd approach it like this:
1) Search the board for all valid positions where your block fits (i.e no collision), which are also finishing states.
2) Order this list of positions by 'score' according to your board evaluation metric
3) Starting from the best position, run A* search to your starting position
4) If successful, use this move. If unsuccessful, remove this position from your moves list and goto 3.


It's overkill for most situations, so maybe you might also want to improve it by running a quick board scan for suitable board subsection 'holes' like in my example, and only applying the search for moves ending in those areas.


You could perhaps refine this further by noting that you only need to do this when an area of the board is restricted by a certain width (1-3 quares) *and* your piece exceeds this width when in certain orientations.

I've just been making a little terris game myself, so perhaps I'll have a go at this AI sometime...

I never did get my blocks to slide under each other, but I did get a pretty decent tetris AI without that. It's in a java applet that can be viewed here. If anyone is interested the source is also up here.

I usually get between 2k and 5k lines broken before it loses on a 10x20 board, but I have seen it break over 100k on a nonstandard 10x30 board(left it running over night and it was still playing when I got up for class). I've found that rating the board based on holes(amount of empty spaces directly under blocks)=-3, sides=+1, and height(height+=each blocks height, so my height was actually about the mean of the squres of the heights of each row)=-1 works pretty good. My implementation is all in one class but it's broken up into several nearly self explanatory methods and it's mildy commented so it shouldn't be impossible to read.

hm as I read the first post I got the same idea as SlyKnight. that must be a good omen *g*

to get the parameters of the evaluation function of the score of the position of the block is the "magic" behind getting a good AI

and if the AI should be simulating a human, I would add something to not only use the best position. human make errors ;)

and another thing is taking into consideration that you know the next piece coming after this, so try to add both for getting a good score (I know it's more difficult then, but the AI should be better then too). at least all tetris' I played showed the next piece and as a human you would plan with it

Quote:

Original post by LeChuckIsBack It's quite strange how my own creation kicks my ass from time to time - LOL

Heh, at least you know you wrote a good AI when that happens :). I wrote a bridge playing one and it beats me fairly regularly, though I don't claim to be a very good player.