Appendix B: The subject of an "estimator"
We use estimators everyday but probably don't think a lot about them.
For example, consider your speedometer on your car. You look at it
and it says "55" and so you think that you are going 55 mph. Well, actually this is an estimate of your speed because something
in your car is counting how many times your axle is turning and then "estimates" your speed by considering the diameter of
your tires. If you change the size of your tires your speedometer will not be accurate. Or if you are spinning your tires
in the snow it may say "30 mph" when you are not even moving.
Consider a thermometer. It is an "estimate" of the room temperature
that is based on a little bit of mercury in a glass tube. If you see a display of thermometers in a store they all will read
different values.
Now consider a chess engine. It "estimates" the winnability of a position
by "looking at" thousands or millions of positions and "scoring" them based on a set of scoring rules. Each chess engine will
score a position different, much like the collection of thermometers in a store display. The engine follows a set of rules
to "stop looking at" future positions when it thinks that the possibility is low that play will follow that path.
But which is correct? Well, an engine produces an "estimate" of the
winnability of the game, and so it could be wrong.
How do you go about estimating the winnability of a game? You do 2
things:
1. You come up with a set of "scoring" rules to precisely define "good"
and "bad" positions and
2. You come up with a set of rules for "stopping" your search for
the best position. Consider hunting for easter eggs. First you determine the "possible" spots for eggs, then you look in the
"likely" spots, and then you give up when you are tired or out of time. There are likely eggs that you missed, but you probably
got most of them. You probably used "cues" in your search for eggs, such as the location of eggs last year, looking in places
that are hidden from direct view, looking in places that require crawling, climbing, stretching, etc.
In fact, you probably decide that you are going to base your search
along the lines that maximize your chance for finding an egg. You develop simple rules for locating eggs, based on your ability
to search, the likely locations, possibly even the hiding 'techniques' of those that are hiding the eggs.
The clock on the wall "estimates" the time. Your car's gas gage "estimates"
how much gas is in your gas tank.
Now an estimator seems to involve 3 things - there is a "counting"
part, there is a "calculating" part, and there is a "display" part. Your car's speedometer counts how many times your axle
revolves in one second and then calculates your speed based on what it thinks is the diameter of your tires. Your car then
moves a dial on your dashboard a certain amount to indicate speed. A police officer's radar gun measures the frequency shift
in radio waves bouncing off your car and calculates the speed your car must be going from a formula. It then displays the
answer as a number he can read. The Nielsen company conducts telephone polls and mounts devices to TV sets to "estimate" the
number of households that are watching TV programs. Millions of dollars in advertising revenue trade hands based on these
estimates. TV sets are counted that are in use. Calculations are done based on the statistical distribution of people in cities.
The results are displayed on web pages.
Estimators usually take many years to develop, and go through a refinement
process. People keep estimators that are accurate and do not use estimators that are not accurate. People keep estimators
that are cheap and simple to operate and use. They do not use estimators that are complicated, inaccurate or expensive. Estimators
use information cues that are present in the environment or that can be calculated from these cues with a reasonable amount
of effort.
Now a chess program also has a counting part, a calculating part,
and a display part. A chess program represents a chess board and pieces using numbers in a way that it understands. There
is a counting exercise where the position of pieces on the board are translated into numbers using a process invented
or refined by the author of the program. These numbers are added up into a score.
But humans don't want to know the scores of the millions of possible
positions. They want to know how "winnable" the position is for white or black. This would be the score of the position that
is most likely to result after several moves have passed, with each side playing the best they can.
A chess program will look at certain move sequences, and stop
looking further when it decides that play is not likely to proceed down those lines.
After a period of time a decision is made on the best move, and the
score of the most likely to happen position is displayed to the operator, as well as the piece and the move associated with
it. It is an estimate, a guess, that resulted from a counting exercise, a calculating exercise, and a searching exercise.
Continuing our discussion on estimators, and finally getting to how
a chess engine determines the score of a position.
First, they are all different, but many share similarities.
This is how the chess program "crafty", written by Dr. Bob Hyatt, "evaluates"
a bishop:
Give a bonus for what square it is on, and add another bonus based on how many moves it can make. Reward the
piece for being close to the enemy's king. Handle unusual cases where bishops are blocking pawns or are filling voids near
our own king.
actual "king tropism" code:
tree->w_tropism -= king_tropism_b[Distance(square,
BlackKingSQ)];
Here is the actual table that is used to compute the square bonus.
Imagine this superimposed over the chessboard.
int bval_w[64] =
-16,-16, -8, -8, -8, -8,-16,-16,
-16,
2, 0, 0, 0, 0, 2,-16,
-4, 2, 2, 2, 2, 2, 2, -4,
-4, 2, 4, 4, 4, 4, 2, -4,
-4, 2, 6, 6, 6,
6, 2, -4,
-4, 2, 6, 6, 6, 6, 2, -4,
-16, 2, 4, 4,
4, 4, 2,-16,
-16,-16, 0, 0, 0, 0,-16,-16
;
So, once again, we see evidence that traditional chess programs
are not overly concerned with the exact number of moves it would take to attack or defend pieces. They generally reward pieces
for being "close" to the enemy's king, being "near" the center of the board, and being able to move freely 1 move into the
future.
A traditional chess program considers each piece, giving points
for things we generally want this piece to do. To save time we use look-up tables instead of counting things. For example,
we might give a rook a bonus for sitting on an open file - regardless if the piece can actually do anything
if they moved down that file.
We now add up all the components of our "evaluation function" to get
the total score for the position under consideration. Sometimes this score is accurate, and sometimes it is not. That's ok.
It's an estimate of the value of the position. We will order our moves based on the estimated score and search a
large number of them. The "bad" moves we will "prune" from our search tree.
Now, this type of estimator has worked well in the past. But can we
do better?
How do you build an estimator?
Well, there is no rule to build an estimator. They are usually constructed
by people who study an effect for a long period of time.
If you want to build an estimator to evaluate the value of a chess
position, you need to begin by looking for things to count that have value, and then figure out a way to scale the value of
these "countable" things that results in a precise "evaluation".
Here is a quick and dirty estimator for the value of a chess position:
Look at the pieces on the board. Give 900 points for a Queen, 500
points for each rook, 300 points for each Knight and Bishop, 100 points for each pawn.
For a Bishop and knight, give a bonus based on the distance it is
from the center of the board. Give a bonus for being close to the enemy's king.
For each Rook, give a bonus for sitting on an open or half-open file.
Give a bonus for sitting on the 7th rank (regardless of what other piece is near it).
For a queen rook and Bishop, give a bonus for each potential move
we can make. Give a bonus for being close to the enemy's king.
For each King, determine the King safety. This can be as simple as
a bonus for sitting on a corner square such as h1, g1, g2 or h2. Take into account the pawn structure around the king.
For pawns, give a bonus for advancing, and give a large bonus if there
is no pawn blocking a direct advancement to the last rank. For these "passed" pawns, take away points if our opponent can
block the advancement with a piece. Give a penalty for doubled pawns or isolated pawns.
Now, we need to do certain other things, such as "extend" our search
if captures are possible (which might change the material balance).
This simple evaluation function (or variations on it) can be found
in most chess engines. It works surprisingly well. It can be calculated quickly.
Notice that we are not counting the precise attacking, defensive or
collaborative value of the piece. Being near the center of the board "roughly" translates into a good offensive, defensive
and collaborative potential.
Now what if we actually calculated,
for each piece, the number of moves it would take to attack the enemy pieces? What if we calculated the number of moves it would take to defend our own pieces? Wouldn't this be a more precise "estimate"
of the value of the piece? We could give a small bonus if an enemy piece could be attacked in 3 moves. We could give a larger
bonus if the piece can be attacked in 2 moves. An even larger bonus if we can attack it in 1 move.
This will encourage our computer, which is rather dumb, to move
its pieces to squares where they are "fully engaged" in the battle to outmaneuver the opponent. We will have maximized the
offensive, defensive and collaborative potential of the piece.
We do not have to use look up tables in our evaluation function -
we can measure or estimate the positional pressure produced by the chess pieces using other means. Look-up tables can often be an inexact estimator. There might be performance
limitations to this approach.
We should be able to derive the same information by counting "cues" present
in the position of pieces on the board.
However, we can now drastically cut back the search tree
(search fewer positions) because we can now be sure that we are not missing good moves.
