Tetris Attack AI - Java-Games

In article <1106262367.917943.91050@f14g2000cwb.googlegroups.com>,
<swanofnever@gmail.com> wrote:
>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

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

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


Nathan Mates wrote:
> In article <1106262367.917943.91050@f14g2000cwb.googlegroups.com>,
> <swanofnever@gmail.com> wrote:
> >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
>
> 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

In article <1106280326.742773.268570@c13g2000cwb.googlegroups.com>,
<swanofnever@gmail.com> wrote:
>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

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

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

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

<swanofnever@gmail.com> schrieb im Newsbeitrag
news:1106321284.065599.223240@z14g2000cwz.googlegroups.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.


>
> 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



> 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
>

In article <1106283798.306590.181880@c13g2000cwb.googlegroups.com>,
<swanofnever@gmail.com> wrote:
>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

In article <1106321284.065599.223240@z14g2000cwz.googlegroups.com>,
<swanofnever@gmail.com> wrote:
>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