Tetris Attack AI

[s***@gmail.com]

hi,
i've started working on a clone of the SNES game "Tetris Attack"
(released as "panel de pon" in japan and reskinned as "Pokemon Puzzle
League" for n64). (if you haven't heard of the game, it's _nothing_
like tetris and you probably won't be able to help.. it's a very unique
game).

i've figured out the game mechanics, however i'm totally stuck on the
AI.

the two parts of the AI, as far as i can tell, are:
a) decomposing a goal such as "match these 4 blocks" into a sequence of
moves to execute.
b) determining all of the possible goals and choosing one to persue

obviously some sort of pattern searching/matching is required for (b).
my main problem, i think, is figuring out the best structure to
describe the search space. i have no idea how to appraoch (a) because
the game field is an awkward "1.5D": it's very hard to guarantee that
piece X can be moved to position Y without affecting other pieces
negatively.

in general it seems like a very tricky problem because of how dynamic
the game is. then again, it was released on the SNES so the solution
can't be that complex.

anyway, if anyone has any ideas or experience with this, please let me
know.
thanks,
raigan

[Nathan Mates]

Post by s***@gmail.com
a) decomposing a goal such as "match these 4 blocks" into a sequence of
moves to execute.
b) determining all of the possible goals and choosing one to persue

Look up a minmax tree. Basically, you do a quick evaluation of the
board state after each move, with some kind of score associated with
it. You could work on the scoring (heuristic) function right now--
make something that returns a score of 0 for a board with no possible
moves, and a score of 100 for the best possible board (empty?). Then,
just try all possible moves, and run the scoring on the board after
that move was tried. Pick the best move of the lot.

For some randomness, maybe make it pick one of the top 3 moves
(maybe top-10 if on super-easy), or the like.

Nathan Mates
--
<*> Nathan Mates - personal webpage http://www.visi.com/~nathan/
# Programmer at Pandemic Studios -- http://www.pandemicstudios.com/
# NOT speaking for Pandemic Studios. "Care not what the neighbors
# think. What are the facts, and to how many decimal places?" -R.A. Heinlein

[s***@gmail.com]

hi,
thanks for the reply; i'll certainly look into it.

are you familiar with the game? my main problem is that i'd like to
know how the original AI works.. it's running on an SNES!

it just seems like a much more dynamic problem than chess or tetris
where there are rules limitting the possible number and type of moves.

thanks again,
raigan

Post by Nathan Mates

Post by s***@gmail.com
a) decomposing a goal such as "match these 4 blocks" into a sequence of
moves to execute.
b) determining all of the possible goals and choosing one to persue

Look up a minmax tree. Basically, you do a quick evaluation of the
board state after each move, with some kind of score associated with
it. You could work on the scoring (heuristic) function right now--
make something that returns a score of 0 for a board with no possible
moves, and a score of 100 for the best possible board (empty?). Then,
just try all possible moves, and run the scoring on the board after
that move was tried. Pick the best move of the lot.
For some randomness, maybe make it pick one of the top 3 moves
(maybe top-10 if on super-easy), or the like.
Nathan Mates
--
<*> Nathan Mates - personal webpage http://www.visi.com/~nathan/
# Programmer at Pandemic Studios -- http://www.pandemicstudios.com/
# NOT speaking for Pandemic Studios. "Care not what the neighbors
# think. What are the facts, and to how many decimal places?" -R.A. Heinlein

[Nathan Mates]

Post by s***@gmail.com
are you familiar with the game? my main problem is that i'd like to
know how the original AI works.. it's running on an SNES!

No, never played it. If you're trying to know exactly how it works,
you'd likely have to (1) find an interview with the authors explaining
that (unlikely to exist), (2) get very good with 65816 assembly and
SNES hardware, disassembling the binary code on the cart, or (3)
videotape/videocapture a lot of games, and study the AI until you have
a good mental picture of how it works.

65816 assembly isn't that hard to pick up (or at least it was for
me when I had a bit more free time on my hands 14-15 years ago), but
learning the SNES at the same time might take a while.

Nathan Mates
--
<*> Nathan Mates - personal webpage http://www.visi.com/~nathan/
# Programmer at Pandemic Studios -- http://www.pandemicstudios.com/
# NOT speaking for Pandemic Studios. "Care not what the neighbors
# think. What are the facts, and to how many decimal places?" -R.A. Heinlein

[s***@gmail.com]

hi,
i'm hoping that i'll only have to do that as a last resort ;)

my main concern was that it's quite different from other "puzzle" games
in that the potential moves are virtually unlimitted.

in games like tetris or puyo puyo you only have to decide where/how to
place the currently falling block. this means that a game tree of
possible future game states isn't very large.

in tetris attack you're presented with a grid where you can swap the
positions of any two pieces, and you can perform any swap you want
(unlike bejeweled which limits you to swaps that lead to a match). by
swapping, moving the cursor left/right, and swapping again, you can
move a block to any other location on its current row. if there's an
empty space on a lower row, you can move it to any space on that row
too, by dropping it down the space.

in this case it seems like building a tree of all possible game states
isn't the best approach, because it would be huge. (the grid is 6x12)

i guess what i meant was, there _must_ be a simpler solution, since it
runs on such slow hardware where an exhaustive seach probably wouldn't
work.

i was hoping that someone actually knew about this specific problem --
but i guess this might be the reason why there aren't any clones with
working AI ;)

thanks though,
raigan

[Nathan Mates]

Post by s***@gmail.com
in this case it seems like building a tree of all possible game states
isn't the best approach, because it would be huge. (the grid is 6x12)
i guess what i meant was, there _must_ be a simpler solution, since it
runs on such slow hardware where an exhaustive seach probably wouldn't
work.

There's probably a few ways to trivially reject some moves as not
worth pursuing. Or, it may prioritize some rows to look at first--
those with the worst-case, or those with the most chances of
success. Also, it may only examine a row at a time for
possibilities. Splitting up the workload over lots of frames gives
even slower CPUs (the SNES's 3.5Mhz 65816, probably equivalent to
about a 15Mhz 286) a chance at doing a decent amount of work.

Nathan Mates
--
<*> Nathan Mates - personal webpage http://www.visi.com/~nathan/
# Programmer at Pandemic Studios -- http://www.pandemicstudios.com/
# NOT speaking for Pandemic Studios. "Care not what the neighbors
# think. What are the facts, and to how many decimal places?" -R.A. Heinlein

[Gernot Frisch]

http://www.tetrisattack.net/

Nathan has already explained perfectly how it works. It's should be
easy to write:


get_best(depth, byref bestswitch)
{
if depth < max_AI_depth
for each switch in possible_switches
save_for_undo()
score = perform(switch)
score = score + get_best(newswitch, depth+1)
if score>bestscore
bestscore=score
bestswitch=newswitch
endif
undo()
next
endif

return bestscore
}

I've not tested it, but it should work pretty good. The perform()
function would do a switch, then all chain reactions and scoring, and
return the score for this switch. The save_for_undo and undo push/pop
the current playfield on a stack and restore it for later. Do not make
max_AI_depth any deeper than 3-5 or you will get very slow results, a
very bad enemy or propably a stack overflow error.

HTH,
Gernot

[s***@gmail.com]

hi,
i understand the basics of the method, i just don't think that it's an
appropriate solution.

once you play the game, you'll understand: the computer opponent will
often make 6-8 or more switches BEFORE any matches happen, just to get
things aligned so that when a match does occur, it triggers a huge
chain reaction. in this case, the score for the board would be the same
no matter which 3-5 switches happen, since no matches are likely to
occur after such a small number of switches; looking 3-5 moves ahead is
almost useless, since making 3-5 switches usually doesn't do much.

i think this approach might be useful if, as part of the scoring
heuristic, i detect the patterns which can easily be turned into chains
in one or two moves, or consider "move block A from (x0,y0) to (x1,y1)"
to be a single move -- in this case, looking 3-5 moves ahead _would_ be
useful. but this would square the number of possible moves at each
iteration, so it's probably not feasible.

anyway, i _will_ try implementing this, hopefully my scepticism will be
proven wrong.

the main thing is: at each iteration there are (at most) 60 possible
switches. typically i'd say there would be ~40 possible switches (since
the playing feild is usually empty at the top).

this means that each search will result in perform() being called
64k-100M times (if we're using 3-5 depth). even spread across many
frames, this seems a bit much, especially since
(a) 3 switches very often accomplishes nothing; it takes 5 switches to
move a block from one side of the screen to the other.. since you often
have to move multiple blocks to create a good pattern, 5 seems like the
minimum required -- not to mention that the current AI is fond of
performing 10+ switches without any matches being made, just to
reposition pieces.
(b) again, on an SNES this approach seems unlikely.

since this is the best i've got, i suppose i'll have to try it. it
simply seems that the real solution is a simpler procedural set of
rules with a bit of searching/pattern matching thrown in, instead of an
exhaustive search through all possible moves.

thanks,
raigan

[Gernot Frisch]

Post by s***@gmail.com
hi,
i understand the basics of the method, i just don't think that it's an
appropriate solution.
once you play the game, you'll understand: the computer opponent will
often make 6-8 or more switches BEFORE any matches happen, just to get
things aligned so that when a match does occur, it triggers a huge
chain reaction. in this case, the score for the board would be the same
no matter which 3-5 switches happen, since no matches are likely to
occur after such a small number of switches; looking 3-5 moves ahead is
almost useless, since making 3-5 switches usually doesn't do much.

of course: You will look 5 steps ahead _all_ possible 5 steps, and
take the best.

Post by s***@gmail.com
i think this approach might be useful if, as part of the scoring
heuristic, i detect the patterns which can easily be turned into chains
in one or two moves, or consider "move block A from (x0,y0) to
(x1,y1)"
to be a single move -- in this case, looking 3-5 moves ahead _would_ be
useful. but this would square the number of possible moves at each
iteration, so it's probably not feasible.
anyway, i _will_ try implementing this, hopefully my scepticism will be
proven wrong.

sure

Post by s***@gmail.com
the main thing is: at each iteration there are (at most) 60 possible
switches. typically i'd say there would be ~40 possible switches (since
the playing feild is usually empty at the top).
this means that each search will result in perform() being called
64k-100M times (if we're using 3-5 depth). even spread across many
frames, this seems a bit much, especially since
(a) 3 switches very often accomplishes nothing; it takes 5 switches to
move a block from one side of the screen to the other.. since you often
have to move multiple blocks to create a good pattern, 5 seems like the
minimum required -- not to mention that the current AI is fond of
performing 10+ switches without any matches being made, just to
reposition pieces.
(b) again, on an SNES this approach seems unlikely.
since this is the best i've got, i suppose i'll have to try it. it
simply seems that the real solution is a simpler procedural set of
rules with a bit of searching/pattern matching thrown in, instead of an
exhaustive search through all possible moves.
thanks,
raigan

[Nathan Mates]

Post by s***@gmail.com
the main thing is: at each iteration there are (at most) 60 possible
switches. typically i'd say there would be ~40 possible switches (since
the playing feild is usually empty at the top).
this means that each search will result in perform() being called
64k-100M times (if we're using 3-5 depth).

I don't think you fully read my first response to you. You *really
need to look up MinMax trees*. I repeat that: go to
http://www.google.com/ and look that up. They're directly related to
this exact problem. I mean it.

Chess has far more possibilities, yet it's been done on computers
simpler than a SNES. Minmax makes it possible. Let me give you a hint:
you don't have to investigate all the possibilities. Remember that
scoring (heuristic) function I mentioned in my first response? Once
again, it's a very useful component. Go re-read my response, and spend
some quality time with http://www.google.com researching the
algorithms I mentioned. You'll learn far more from that than just
giving you an answer outright.

Nathan Mates

--
<*> Nathan Mates - personal webpage http://www.visi.com/~nathan/
# Programmer at Pandemic Studios -- http://www.pandemicstudios.com/
# NOT speaking for Pandemic Studios. "Care not what the neighbors
# think. What are the facts, and to how many decimal places?" -R.A. Heinlein

[s***@gmail.com]

i'll let you know when i've got it up and running ;)

it still seems like an overwhelming number of "calculate heuristic
score for a given board configuration" operations are going to be
needed. then again, i won't know till i try.
anyway, thanks very much.
raigan

[Raghar]

In article

Post by s***@gmail.com
the main thing is: at each iteration there are (at most) 60
possible switches.

With how many positions?

I don't think you fully read my first response to you. You
*really
need to look up MinMax trees*. I repeat that: go to
http://www.google.com/ and look that up. They're directly
related to this exact problem. I mean it.

I hope you looked at "alpha beta".
It's not useable for my current game bacause it has branching
factor over 200, but it might work better for you.

[w***@users.cidermail.com]

Post by Raghar

In article

Post by s***@gmail.com
the main thing is: at each iteration there are (at most) 60
possible switches.

With how many positions?

I don't think you fully read my first response to you. You
*really
need to look up MinMax trees*. I repeat that: go to
http://www.google.com/ and look that up. They're directly
related to this exact problem. I mean it.

I hope you looked at "alpha beta".
It's not useable for my current game bacause it has branching
factor over 200, but it might work better for you.

Thanks!

***@users.cidermail.com

[T]

Post by Nathan Mates
I don't think you fully read my first response to you. You *really
need to look up MinMax trees*. I repeat that: go to
http://www.google.com/ and look that up. They're directly related to
this exact problem. I mean it.
Chess has far more possibilities, yet it's been done on computers
simpler than a SNES. Minmax makes it possible.

Um...the difference between Chess and Tetris Attack being that chess
moves are made alternately by opposing players and in Tetris Attack you
make all the moves...?

The whole concept of MinMax relies on opposition maximizing their
advantage for every move.

How do you apply that to Tetris Attack where you don't have opposing
moves and the mini-max principle does not apply very clearly?


If I understand Tetris Attack correctly it looks like you could get a
pretty good AI by just grouping tokens equal to the token dropping
around the impact area. Your target should be the 7 squares around the
impact point. The 8th square is right above it and obviously it is
empty.

Now make a list of all the tokens equal to the one dropping. Calculate
how many "swaps"/"moves" it would take to get each of them into the
target 7 squares. Keep moving the tokens to the 7 sqaures until they
hit a target square or an equal token until you have impact. Reapeat
for new token.

T
PS: I might be confused about how Tetris Attack works, never played it.