Computer Playing Tetris

Most likely it's because the numbers you are using to score with work well with one set of pieces and not with another. The scoring function is, naturally, dependent on the specifics of the game you are playing, and a game with different pieces is a different game.

Finding the correct weighting for all the different elements of your score is a search problem, and one that is classically solved by a GA (although other methods probably work as well). Use the weights as the string to be evolved, and calculate fitness based on how well the algorithm plays.

Also, I noticed that there was no measure of highest point in your scoring algorithm. Isn't that usually taken into account (having a high point is usually bad, and so would be given a negative score)? I don't really remember all the elements that go into scoring, though, so maybe it's not needed.

While we're on the subject, although this isn't how you're designing your AI, I wonder if anyone has created a Tetris-playing AI that can think ahead? Human players often make solid blocks with one thin piece missing, say, so that when the straight piece comes they can get the bonuses for destroying multiple lines. It would be interesting to do.

Quote:

Original post by Asbestos Finding the correct weighting for all the different elements of your score is a search problem, and one that is classically solved by a GA (although other methods probably work as well). Use the weights as the string to be evolved, and calculate fitness based on how well the algorithm plays.

What does GA stand for? How do I find out what methods I could try to solve the problem?

Quote:

Original post by Asbestos Also, I noticed that there was no measure of highest point in your scoring algorithm.

Sounds like a good idea, I'll add that too.


Thanks for your help!

Quote:

Original post by quarity2 What does GA stand for? How do I find out what methods I could try to solve the problem?

GA stands for Genetic Algorithm. Wikipedia would probably have a description of it.

Quote:

Original post by juanpaco GA stands for Genetic Algorithm. Wikipedia would probably have a description of it.

Right. Look up Genetic Algorithms with these ideas in mind:

Say you are using the number of rows, number of holes and number of edges as the only values in your scoring algorithm. Each of those has an associated weight, right? In your example above, the weights were

RowWeight = 100
HolesWeight = -6
EdgesWeight = 3

The string that you are evolving (also called the chromosome) is therefore (100, -6, 3).

The "fitness" of each chromosome is simply how well an algorithm with those weights plays the game.

By the way, once you have gotten the general idea of GAs, there are some open source libraries at the AI Tools toolbox. It might be more useful, though, to try and code one from scratch (it's really pretty easy).

The scoring for a placement should be based on the board that results rather than the piece's individual statistics. That way you can look at placing two pieces at a time and get an accurate measure of how good a move is with respect to the next piece available(look one move ahead like players do). Then you just need a function to measure how good a board is and a good method of finding what moves to search and you have a decent tetris playing AI. There have been a few threads about tetris AI to go through this forum I believe this is the most recent: http://www.gamedev.net/community/forums/topic.asp?topic_id=410594&whichpage=1

Hmm, seems Rixter explained it better than I could:

Quote:

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.

Check out my tetris AI applet at: http://alrecenk.cjb.net:7790/Java/Show/tetris/

Alright, thanks. That will get me started.

Quote:

Original post by Alrecenk The scoring for a placement should be based on the board that results rather than the piece's individual statistics.

Hmm... I might try that instead. Looks much easier to find a good location.

But I was thinking... what exactly are wells? Is that how many deep holes there are on the board. How deep should a well be?

[Edited by - quarity2 on December 20, 2006 7:15:15 AM]

Quote:

Original post by quarity2 Hmm... I might try that instead. Looks much easier to find a good location.

Indeed, although as the guy says, he still used a GA to find the weights.

You may still find an OK solution via trial-and-error, though. It might not be the best one, however.

Looks like Colin Fahey's site is back up: Tetris AI
Interesting stuff on there.

If you look down to section 10, the best 1-piece algorithm (no information on the next piece comming), was hand tuned by that guy. So you can get good results without a GA.

Section 6.9 talks about the evaluation metrics.

Wells are just holes one space wide and aren't blocked on top, so like where you'd put the straight piece.

Good luck

Thanks for all the help.

I think my code have some bug or something. Because I'm getting strange results. For example if I check only the pile height, then the piece will sometimes choose the highest pile. I need to walk thru my entire code step by step to find out where the bug is. It will probably take some time :(

But I'm not after the best possible AI, only a good enough AI to play with against a human player. So I'm going to use trial-and-error. Might try the GA at some point, but for the moment I'm just after a simple AI.