So how
does it work ? The main structure of the algorithm acts as a BFS. The idea is the following: given the current playfield state and the
tetrominos to come, we have to explore the tree of possible moves,
evaluate their relevancy and keep the best to play.

But what
is a move in Tetris ? Is a tetromino rotation or shifting considered
as a move ? The answer is no. A move in Tetris is the action to lock
a tetromino in a stable position on the playfield. It is relevant to
think a move in this way, because it is only when a tetromino is
locked that important events occur (lines collapse, game over) and as
a result we can evaluate if the situation is good or not for us.

Then, we
need to fix a limit to the depth of search. As a Tetris game can
simply be infinite, and also because we want to limit the time the
machine spend in this task. For pratical considerations, we will
assume here the depth of search being at maximum the number of
tetrominos that are previewed. Sometimes, the depth can simply be 1
(we consider only the current tetromino).

An exemple of partial game tree of depth 2, starting with the empty playfield

Last clarification: there is no perfect situation evaluation, simply because our
information of the future is limited (by the arbitrary depth of
search). That's why we will talk about heuristics for situation
evaluation.
Now that
we have some relevant concepts, we can look at the process more
precisely. Given a playfield state (empty at start), the current
tetromino to play and the next tetrominos in preview, the algorithm
does the following:

1 : construction
of the game tree of the chosen depth:

Depth 0:
the current playfield state.

Depth 1:
the generation of all the playfield states given by all possible
locked positions of the current tetromino from the current playfield.

Depth 2:
the generation of all the playfield states given by all possible
locked positions of the next tetromino from all the payfields built
at depth 1.

...

Consider
here that for a playfield of width 10, your tree has an average total of
30^n nodes, where n is your chosen depth of search.

2 : utilization
of an appropriate heuristic to score all the terminal nodes of the
game tree previously generated.

3 : selection
of the node with the better score, then going up through the branch of
the game tree until the node of depth 1 is reached. It gives the move
for the current tetromino that could potentialy leads to the best
playfield state.

4 : generation
of the relevant inputs (rotation, shifting...) in order to play
correctly the current tetromino regarding the move previously found.

Some
relevant remarks at this point. At first, this process is very time
consuming, so if the AI has to played in real time, it is reasonable
to keep your depth of search at maximum 2. Then, the inputs
generation is an interesting part of the algorithm ; by tweaking it you can add
some personnality to your virtual player in versus games. For example
by allowing or not the quick fall and the hard drop, you can give the
illusion of playing against a beginner or an expert.

Now
let's talk about the more interesting part: the heuristic. It is
where every developer can lead to different results. As previously
said, there exists no perfect heuristic. What you need is to
translate your own experience in playing the game into an algorithm.
Here is the list of components I used to build mine:

- h0
= the number of holes in the playfield
- h1
= the altitude of the higher full cell in the playfield
- h2 = the
number of full cells in the playfield
- h3 = the
value of the higher slope in the playfield
- h4 = the
roughness
- h5 = the
number of full cells in the playfield weighted by their altitude

Notice that for each component, higher the value is, worse is the playfield
state. Then we just need to combine them in order to finely express
the balancing between them. The simplest way to do it is by using a
linear form :

score =
c0*h0 + c1*h1 + c2*h2 + c3*h3 + c4*h4 + c5*h5

with c0,
c1, c2, c3, c4, c5 fixed numeric values

Of
course it is possible to use more generic polynomial formulas,
regarding the strategy you want to express. Actually I use a very
simple version, where I set that holes in the playfield is the worse
thing, by applying a coefficient of value 20 :

score =
20*h0 + h1 + h2 + h3 + h4 + h5

And surprisely, it works very well even with value 1 as depth of search.

Hoping
it can inspire you.

Inspired... Great post! As a recently self-taught programmer, I've been curious as to how the AI logic would work for such a thing and while I've found code in languages I'm not good with, your breakdown, gave me a ton of ideas as to how I can achieve my own.

ReplyDeleteThanks ! =D

I'm glad you liked it :)

ReplyDeleteYou like mazes and you like tetris - you might find this interesting: https://scratch.mit.edu/projects/72678284/ (the associated links probably more so than the demo project)

ReplyDelete