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]
