**The Evaluation Function**

For the shallow search, each leaf node in the
tree (at depth 3) corresponds to two
playing field states – b_{1} and b_{1}’. For the deep search, each
leaf node (at depth 7) corresponds to two playing field states – b_{2}
and b_{2}’. The various states are defined below in the order of
occurrence:

b |
Current playing field (at the root of the tree). |

b |
Playing field with the current (first)
tetrad in a final resting position |

b |
Playing field b |

b |
Playing field with the next (second) tetrad
in a final resting position |

b |
Playing field b |

The evaluation function used is (given states
b and b’) a weighted sum of eight functions that return nonnegative values:

**E(b, b’) = w _{1}F_{1}(b) + w_{2}F_{2}(b)
+ w_{3}F_{3}(b) + w_{4}F_{4}(b’) + w_{5}F_{5}(b’)
+ w_{6}F_{6}(b’) + w_{7}F_{7}(b’) + w_{8}F_{8}(b’)**

The goal of the shallow search is to maximize
E(b_{1},b_{1}’). The goal of the deep search is to maximize E(b_{2},b_{2}’).

Notes: |
·
The first 3 functions
operate on state b rather than b’ because they evaluate the final placement
of the tetrad. If lines are completed, then all four tetrad squares no longer
exist in state b’. The remainder of the functions operate on state b’ because
it is the ·
If no lines are
completed by the placement of the tetrad, then b = b’. ·
For the deep search,
the first 3 functions act only on the second tetrad, and F |

The eight functions compute features of the
playing field state. I selected eight features that I felt were important to
evaluate when deciding where to place a tetrad. I originally had many detailed
features in mind, but the eight general features seem to be sufficient for
exhibiting much better playing ability than I had expected (see Results). Below are the definitions of the
eight functions:

F_{1} = Maximum Depth of
Tetrad Squares

This value is the
height of the deepest (lowest) of the tetrad’s four squares when it lands in
its final position (prior to possible line completion). The value corresponds
to the row number, where 1 is the top row and 20 is the bottom row.

F_{2} = Minimum Depth of
Tetrad Squares

This value is the
height of the shallowest (highest) of the tetrad’s four squares when it lands
in its final position (prior to possible line completion). The value
corresponds to the row number, where 1 is the top row and 20 is the bottom row.

F_{3} = Average Depth of
Tetrad Squares

This value is the
average height of the tetrad’s four squares when it lands in its final position
(prior to possible line completion). The value for each of the four squares
corresponds to the row number, where 1 is the top row and 20 is the bottom row.
The sum of these four values is divided by four to obtain the average depth of
the tetrad.

F_{4} = **Ø**** **(Number of Holes)

This value is the
"negation" of the number of holes on the playing field after the
tetrad has landed and *after* possible line completion. (A hole is a blank
square that has at least one filled square above it in the same column.) In
order to have F_{4} evaluate to a nonnegative number, the number of
holes is "negated" by subtracting the value from 200 (the total
number of squares on the playing field – 10 x 20). Thus, this
value is the number of non-hole squares on the playing field.

F_{5} = Number of Lines
Completed

This value is the
number of lines (if any) that become completed (and disappear) during the
transition from b_{0} to the final state (b_{1}’ or b_{2}’).
This number ranges from 0 to 4 for the shallow search, or 0 to 8 for the deep
search.

F_{6} = Surface
Smoothness

The hole prevention
encouraged by F_{4} may lead to high stacks of filled squares with deep
canyons that can only be filled by red tetrads. The goal of keeping a smooth
"surface" (the topmost filled block in each column) is to counteract
this (which normally involves creating some holes), as well as providing smooth
landing spots for tetrads that may create holes if placed on a "rough"
surface. Thus, the optimal TETRIS player must find the right balance between
hole prevention and surface smoothness. The value for this feature is the
"negation" of surface roughness (200 – surface roughness), where
surface roughness is the sum of surface height differences in adjacent columns.
More specifically,

Surface roughness =

(h_{2} – h_{1})
+ |h_{2} – h_{3}| + |h_{3} – h_{4}| + |h_{4}
– h_{5}| + |h_{5} – h_{6}| + |h_{6} – h_{7}|
+ |h_{7} – h_{8}| + |h_{8} – h_{9}| + (h_{9}
– h_{10})

Where h_{i}
is the height (row number, from 1 at the top to 20 at the bottom) of column i,
1 £ i £ 10, h_{1} is the
leftmost column and h_{10} is the rightmost column. Note that the
definition encourages height to accumulate against the walls of the playing
field. This is intentional, because high stacks of squares along the walls do
not break up the playing field as stacks elsewhere do.

F_{7} = **Ø**** **(Squares Above Holes)

For each column
that has a hole, calculate (height of lowest space – height of topmost hole),
where height is the row number, from 1 at the top to 20 at the bottom. (A space
is a blank square that is not a hole.) Sum these values and "negate"
by subtracting it from 200. This is the value for F_{7}.

F_{8} = Spaces Adjacent
to Holes

This feature is
intended to make it more possible to slide tetrads into holes and can be
thought of as "avoidance of hole trapping." Its value is the sum of
the number of consecutive spaces (blank squares that aren’t holes) to the
immediate left and right for each hole on the playing field. Because of its
definition, however, terrible play can result if this feature is weighted too
heavily – the more holes on the playing field, the higher F_{8} is
likely to be.