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...

Hey, you can check out my AI tetris player right here (source included):
Logic Impact Arena 2005
It plays better then many people I know! [smile]

I realy learned to play serious tetris while making this game, you know? It's quite strange how my own creation kicks my ass from time to time - LOL

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.