For school we have a final project coming up that''s due roughly a month from now in C++. I''m more of a Java person, though, and we haven''t learned anything in class about graphics or any API that would allow us to make anything remotely "cool" in nature for our project. So my ideas were kinda limited. However, over spring break, one of the crazier kids in our class worked freelance on a Tetris-clone and is going to pass it off as his final project. And so the whole class period, this one other kid is playing the game, half the class is watching, and me, my friends, and the teacher are asking him various things about his game. One thing that came to my mind was doing my project on Neural Nets. I asked if I could use his game as a basis for evolving some digitial Tetris players using the little I know about Neural Nets and Genetic Algorithms. I''ve been thinking of different ways to structure the NNs so they''d learn quickly and run quickly enough to play the game. My original thought was to have one simple polar-based input for each square on the game board. Then I got the thought of including a simple integeral input in addition for each row that represented the number of filled blocks in that row. Lastly, I thought of giving my NN a short one-cycle memory that would hold the data of the previous game state in a two dimensional vector and I would also feed that through each time. I was worried though, that a "memory" might cause the NN to work too slowly for the game to handle. I estimated that there''d be about 200 inputs if I were to do that. Then as my outputs, I''d have a simple +1/0/-1 to represent pressing the left or right key (or none) and then another +1/0/-1 output to represent block rotation. Does this sound very practical at all? I''m relatively new to AI, but I think I know enough to get them to play the game and then splice the higher scoring ones together. Any questions, suggestions, comments, et cetera would be much appriciated.

1 month? you crazy!

You simply wont get it done in 1 month!

If you DID decide to go ahead with it, I would suggest that you simplify the game representation to generate a simple AI agent. It''s a class project and trust me, if you got ANYTHING working along these lines, your teacher would be very impressed! It wouldn''t have to be a great Tetris player, just one that could play the first level!

You could represent the current game state with the following pieces of information:

A representation of the current edge of the game board. The easiest way I can think of at the moment to do this is an integer (ranged from 0 to GAME_WINDOW_HEIGHT) that tells where the top of the block structure is in each column of the game board.

A representation of the current piece. Simply a piece number and orientation would be sufficient.

These give a fixed length input string, which is very important for many learning implementations.

Your output might consist of 2 numbers: column to move piece to and final orientation.

Whatever method you use to learn a mapping from inputs to outputs, you have the difficulty of providing payoff to intermediary moves. This is the credit assignment problem and it''s non-trivial. Basically, how do you decide how each move should be valued, given that it isn''t the final move in competing the game; or in this case, the level.

Personally, I think you are biting off way more than most people could chew in 1 month, but then I don''t know you and maybe you can do this!

Whatever you choose to do, good luck!

Cheers,

Timkin

Hehe, I guess I am trying to too much in a short amount of time. I really don''t need it to be any good at Tetris =-) As long as it can play and does more than randomly move around the board (even if it just stacks up all the blocks aimlessly to either side, that''s better than random).

I like the ideas of the NN i/o better than my method. I''ll tinker with it though. I''ll have plenty of time to think about how I can get this to work (since we don''t really *learn* anything in our class).

Other than that, the only major task I can think of is getting the GA to learn them good automatically and how to serialize the NN''s so I can show my teacher (I wonder how he''d like a bianary representation of a C++ class object for a final project... it''s kinda like a program =-)

Anywayz, thanks for the reply.

I've had another thought that I'd like people comments on please... it's with regard to the credit assignment problem I alluded to earlier for Tetris.

Essentially the problem is how to value the moves that lead to the final state of the game (finishing the level); in other words, all moves bar the last one.

My thoughts ran along this line...

...one simple strategy in playing Tetris is to remove the top row of blocks and to repeat this until no more rows remain. (I said SIMPLE!)

Using the edge representation I described above, a continuous row of blocks would have the same integer values (depending on the height of the row above the bottom of the game window) and the variance in these values would be zero. For any other configuration, the edge representation would have an average height and a finite variance (sum of the squares of the deviations of each integer value from the average). If you followed that above simple strategy, then any piece placement that reduced the variance in the edge representation would take you closer to removing a row of blocks (with the exception that you didn't create a situation that made it impossible to complete the row without first completing n rows above it).

Hence, you could value any move using a function of the change in variance and the final variance after the piece was placed.

What are peoples thoughts on this? There is a lot more depth I could go into about other strategies - like maximising points for the level - but I just want to keep it very simple for the moment.

I'm particularly interested to know if someone can find a flaw in this reasoning that would prevent it from working.

Cheers,

Timkin

[edited by - Timkin on April 9, 2002 1:30:18 AM]

here are some random thoughts on the matter:

1) I dont go for stacking blocks up. This is just for scoring high, and ide rather see how far i cant get. If i can get a line i will.

2) try hard not to create gaps, but sometimes you need to. maybe if you can get rid of a line but it will cause a gap, look at the next block and if that block can get rid of the gap or come close to getting rid of it, then do it.

3) a way to evaluate how bad a gap will be, and compare that against how many lines it can get you would be a good idea.

4) would a tree approach like chess work? there are 7 different blocks, so it branches by 7 each time. this isnt that much (compared to somthing like chess), you could probobly search at least 4 or 5 deep.

5) try to avoid creating pits. try not to let them get past 3, and then try to avoid letting them grow as much as possible. the 3 is because there are a lot of piece that can get you out of

XX XX
XX XX
XXXXX

but only one that can get out of

XX XX
XX XX
XX XX
XXXXX
without creating a gap.

i guess these are more or less just ideas for evaluating weather a move is good or not. good luck and i hope i helped.

An overly simplified weighing algorithm might be this:

The value of the destination is the sum of the values for each blocks resting place where:

the value of the resting place is it''s depth below your current highest block.

What i mean is ... look at an empty field ... and a line piece ... all possible outcomes would either lay the peice on it''s side ... giving you four blocks at level 1, for a value of -4, or a block each at levels 1, 2, 3, 4, for a value of -10 ... so flat is safer than strait.

This algorithm only really helps avoid the piles of pieces you might get in the middle ... but it could form a basis for a better algorithm latter. For one, the pure level based value could be changed to a slope field, where the sides had better values than the middle (by just a little) ... because you know they don''t prevent you from crossing over them ...

And this could lead to it picking to go down the side with the deepest fillable hole (once you had a tower in the middle) ...

now of course ... I didn''t try to make it go for tetris''s ..which is ok ... BUT I ALSO didn''t penilize it for gaps ... which is bad ... but I haven''t figured out a simply method to do so ... that doesn''t have strange behaviors.

If the goal of the AI is to survive as long as possible, there should be one guideline. Do not create gaps. If you do, fill them in or uncover them. The rest of tetris'' gameplay will manifest itself from there. I am assuming that when everyone else agrees with me on not making gaps, they exclude the case where you make a temporary gap to complete a line, which goes away as soon as the piece settles.

cyn

quote: Original post by cyn
If the goal of the AI is to survive as long as possible, there should be one guideline. Do not create gaps. If you do, fill them in or uncover them. The rest of tetris'' gameplay will manifest itself from there.

Actually, I would disagree with this. While it serves as a good strategy, I personally think that not making gaps should be a by-product of the real strategy.

Earlier I posted a simple strategy and an idea for a value function for that strategy, based on a Tetris agent that had to learn how to play the game.

Personally, I wouldn''t implement a Tetris agent via learning, but rather by piece placement search. I worked on solving the Eternity puzzle with the online Eternity community for some time and we came up with some VERY fast methods of testing edge placements of pieces. The Tetris blocks correspond to a very simple class of pieces for which placement tests are trivial.

This leads to a different strategy, IMHO: clearing as many lines at a time (Max 4) as is possible with each piece placement. For each Tetris block there is a maximum number of rows that can be cleared. Each placement can be assessed as to how many rows it clears. If it clears zero rows, then a secondary assessment rule would try to maximise the number of rows that can be cleared with the next piece, which is of course chosen randomly from all... so the probability model for this is fairly trivial to compute. You could extend this lookahead horizon further for better gameplay.

Just my opinions...

Timkin