Tetris and AI

I have been something of an avid tetris fan ever since I bought an old nes cartridge of tetris at some point during junior high. I have spent whole days doing nothing but playing the classic nes version. A couple years ago I bought a ps2 version of tetris (tetris worlds) and it has quite a number of different modes of play but still doesn't hold a candle to the nes version due to certain horrible choices on the part of the game designers.

At any rate the pacman competition has given me a certain amount of perspective on how hard game playing can be as a computational problem.

At any rate although a straightforward search algorithm might be the easiest way to get at least middling results I'm sure it collapses if you want to try and get at truly great long term behavior. Just like most games the tetris search tree is definitely exponential and if you really want to be a good tetris player you have to shape your pieces in ways that are conducive to future building. For even mediocre it would be desirable to be able to look ahead 3 moves at least since you need at least 3 pieces to fill a line to clear.

For the moment lets consider the branching factor of tetris. For a long white piece there are 2 possible rotational positions and 10 possible horizontal positions for one rotational configuration and 7 horizontal positions for the other. giving at least 17 different possible positions for a long piece. For each of the 2 L shaped pieces all 4 rotational positions are different from each other and there are 9 horizontal positions for 2 of the 4 rotational configurations and 8 horizontal positions for the other 2. So each of the L shapes has at least 34 possible placements. The T shape has a similar analysis and has at least 34 placements as well, and so do both of the S pieces. Finally the square has only 1 unique rotational configuration and has 9 possible horizontal positions and so has 9 possible placements.

So we get a branching factor of 34^5*17*9 = 6951619872

So from a straightforward perspective as a search problem tetris is much much much more difficult than say chess which has a branching factor of somewhere around 35 or so (or actually 35^2 since each player has about 35 degrees of freedom on average). So why is it that chess is hard to play and tetris easy? the answer is that in chess most of the time only 3 or 4 of those 35 moves is any good whereas in tetris most of the time no matter how bad a move is the game can be salvaged. So in chess there are a few good paths to winning which are very difficult to find and in tetris there are a vast number of good solutions. Relatedly the reward schedule is much shorter in tetris than in chess. A good move will be rewarded and a bad move punished generally in a much shorter number of steps in tetris than in chess making it easier to discern what moves were good and what moves were bad.

This reminds me of the n-queens problem. The n-queens problem is where you try to position n queens on an n by n chess board so that none of the queens has any other queen on its lines of attack. Solving the n-queens problem can be fairly complex but actually the application of greedy search with a good heuristic and a random starting point is pretty likely to give you a solution. The reason is that the solutions of the n-queens problem are "dense" in the space of all possible n-queens board positions. If you start at any random board position it is pretty decently likely that there is a solution board position fairly close by in the state space.

I think tetris is kind of like a simpler version of go which isn't adversarial (another reason chess is harder than tetris) Perhaps a good intermediate challenge for the AI community before we get a computerized go world class player would be to get a world class tetris player.