Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Telamon

Thorny AI Problem: TetrisAttack

This topic is 5236 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

This post is about algorithms for programming a computer player for the SNES game Tetris Attack. If you are interested, a good source for info on this game is http://www.tetrisattack.net. For those that don''t know about this game and don''t have the time to investigate, I''ll give a short description of the problem... The game is *kind of* like Tetris. But writing a Tetris AI is easy (http://www.stanford.edu/~jjshed/tetris). This is a much mroe difficult problem. There is a screen of blocks. Blocks can be one of five colors. Blocks are manipulated by swapping them horizontally. When three blocks of the same color are placed next to each other, they disappear. Four or more blocks disappearing at the same time results in bonus points. Now the tricky part: If blocks disappearing cause other blocks to fall and disappear (as a result of landing next to a group of the same-color blocks), this forms a "chain". Good players can create huge chains of blocks causing other blocks to disappear. I have constructed a single-player version of Tetris Attack in C# (http://www.stanford.edu/~jjshed/tetrisattack). I now want to build an AI that can play it. The AI that comes with the SNES game is not very good, and I can easily beat it. I want to write an AI that can chain an entire screen of blocks and otherwise play like a god. I''m not sure how to go about this - I suspect there is no general purpose algorithm that could be applied here. The real problem is figuring out how to let the computer look ahead and figure out what block swaps will result in chains. I''m going to try to invent some kind of pattern matching scheme from scratch, but if someone has any ideas I would love to hear them. PS - My description of the problem is not good, and it''s hard to know what I''m talking about without having played the game. If you have time, look at a screenshot and you should get a good idea from that. ---------------------------------------- Let be be finale of seem, seems to me. ---------------------------------------- Coding: http://www.stanford.edu/~jjshed/coding Miscellany: http://www.stanford.edu/~jjshed

Share this post


Link to post
Share on other sites
Advertisement
Well, one way of doing it would be a VERY hefty planning algorithm that took each piece it knew was coming (not just the current one) and covered all the possible combinations of locations they could go and then max out the score. That would be cumbersome but it''s the only thing I could think of right away.

Dave Mark - President and Lead Designer
Intrinsic Algorithm -
"Reducing the world to mathematical equations!"

Share this post


Link to post
Share on other sites
Try looking up classic AI state based tree searches. You have a start state (the position and color of all the blocks at the moment), a goal state (perhaps getting the most points possible in a set time or getting rid of as many blocks as possible) and operators that transform between states (swapping blocks around). You then have to find an appropriate strategy to search through the permutations of applying operators. You could apply heuristics which spot good patterns for starting chains.

Share this post


Link to post
Share on other sites
A tree search was my first instinct, but I don''t think it will work in this case, for two reasons...

1. The necessary tree depth is huge. There are only five actions you could take per think cycle, but to find the largest chain on the board, you would have to search to very high depths, maybe on the order of 50. Even with some smart alpha/beta pruning you''re not going to improve this enough to make it feasible.

2. The game is not turn-based. It is realtime. Blocks have animations for falling, swapping, and disappearing - each taking different amounts of time to complete (milliseconds). There is no turn structure to iterate through.

These are the reasons why this is a thorny problem. I''m not sure that finding the largest possible chain given a screenful of blocks is even computationally tractable. :-(

----------------------------------------
Let be be finale of seem, seems to me.
----------------------------------------

Coding:
http://www.stanford.edu/~jjshed/coding

Miscellany:
http://www.stanford.edu/~jjshed

Share this post


Link to post
Share on other sites
Skill chains might hold the key...
Then the computer doesn''t have to set up the whole chain at once: it can set up part of the chain, and then try to improvise the rest based on its agility and what blocks it is still allowed to move. That''s how I play so I see no reason not to try it with a computer (My brain is just not wired to set up long chains. My longest chains have been skill chains). The computer could set off a five chain and while the blocks are being cleared, look to see if it can add one more to that chain - if it set up the chain it must have predicted where the blocks would end up so it shouldn''t be too hard to program this search. Then it tries to add even one more to that...

The Pokemon Puzzle Challenge AI was particularly good, so maybe observing it will give some ideas...

Share this post


Link to post
Share on other sites
The AI that comes with the SNES game is not very good, and I can easily beat it.

You sure? Have you tried going into the options and setting the CPU on the highest level and turning it on for 2Player mode? I can usually only win, at most, 50% of the time in that mode, and each match has my heart racing like crazy by the end of it.

I also made a single player version and tried to figure out how to build an A.I. for the computer, but I couldn''t figure out anything that worked. Good luck to you. I hope you do figure it out.

Share this post


Link to post
Share on other sites
I used to find the computer hard to beat, but I''ve gotten rediculously good at this game.

I start a game by scrolling the blocks all the way up to the top, and then I chain them all into a 15 chain. The computer is very bad at finding breaks, especially if it has an uneven stack. It usually dies in 30 seconds. In this situation it doesn''t matter what difficulty it is set to.

I''ve spent a long time watching the computer play against itself, and I still don''t have any idea what logic it is following. I know the algorithm must be relatively simple, since I think the entire ROM is less than 400kb, most of which is probably graphics. I think I am going to try writing an AI that just tries to group blocks in sets of three and see if that gives me any insights...

----------------------------------------
Let be be finale of seem, seems to me.
----------------------------------------

Shedletsky''s Code Library:

Open source projects and demos

Share this post


Link to post
Share on other sites
I have just finished watching the computer play endless mode for 90 minutes (fast forward on most of it :-).

I noticed that when it is chaining, it averages 3-4 chains. I think the longest chain it did in 90 minutes is a 10 chain - once.

I also noticed that it makes a lot of superfluous 3-combos. Probably it is making the combo and them hoping to be able to find a skill chain. This probably wouldn''t be too hard of a behaviour to emulate.

It seems that it only knows a small number of skill chain patterns and it only ever uses blocks close to where the chain is happening to continue the chain. This implies that maybe some kind of pattern mask is being laid over the area around the chain to see if it is of a known pattern that could result in a skill chain. I''m less sure about this one.

There is a TON of room for improvement, though. It took the computer 48 minutes to max its score out at 99,999. The top human players can do this in under 3 minutes and 30 seconds. (http://www.tetrisattack.net - they have a video of this), an order of magnitude faster.

Maybe this is the kind of problem that can be solved by finding an ok solution and then throwing CPU cycles at it. I dunno.

----------------------------------------
Let be be finale of seem, seems to me.
----------------------------------------

Shedletsky''s Code Library:

Open source projects and demos

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
The tree method would work but maybe kind of slow because of the search depth. The turns that you would be looking at are the final positions of the blocks. You would need a different ai to do the path planning for the block to get it there.

Share this post


Link to post
Share on other sites
I would use a b-tree and an up pointer with some sort of huerstic to keep the number of moves per level small. Then store the score after making that move in the node itself. That way all you have to do is generate all the moves across the bottom add the score they make to the score of their parent, search for the one with the largest score then climb the tree. When you hit the root the last node visted before hitting the root was the move that should be made. Most of the work is done generating the orginal tree but it can be done before the game starts.

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!