entropy of chess positions
John Tromp
of possible chess games and/or positions. This led to the question of
how many bits are needed in order to describe a position.
If we take into account the likelihood of a position occuring in actual
play then we arrive at the concept of `the entropy of chess'.
Let's imagine there is some fixed probability distribution over
all chess positions, and say that the information (number of bits)
in a particular chess position is the negative 2-logarithm of the
probability of that position. Then entropy is the expected information
in a position, or formally, the summation over all positions x
of P(x) times -log P(x).
The nice thing about all this is that we can actually approximate this
`entropy' by playing a guessing game, where one player has chosen
chess position at random and the other sets out to determine what it is
by asking multiple choice questions. This approach was described in
an article by prof. Jurg Nievergelt, who arrived at an estimate
of 70 +-10 bits.
I persuaded him to redo this experiment and we both tried to guess
the other's position, by asking questions like:
- are there 0, 1 or 2 white rooks on a1-f1?
- is the (number of white doubled pawns, #black doubled pawns) equal to
(0,0) (1,0) (1,1), other?
- Does Wh have exactly 1P on each of the files f, g, h?
or more typically:
- Wh Q on d1, d2, e2, other?
- Wh Q-B on diagonal c1-h6?
It turns out that asking the `right' questions is quite an art,
and I often found that I could have saved a couple of questions if had
just asked them in a different order.
The end result was 75.7 bits for one and 82.6 bits for the other,
which conforms reasonably well with above estimate.
A complete record of both guessing games is available by email upon request.
While all of this seems to be of little practical interest,
it is nice to think about the following:
For all those chess database programs such as ChessBase and Nicbase,
it might be important to either transmit or store positions as compactly
as possible (ignoring the fact that these programs handle games instead
of positions!).
If an algorithm can be made that plays the position guessing game
at a reasonable level, then it would be profitable to represent games
as the sequence of answers to the questions posed by this algorithm.
just dreaming...
John Tromp (tr...@cwi.nl)
jo...@ohstpy.mps.ohio-state.edu
>
> While all of this seems to be of little practical interest,
> it is nice to think about the following:
> For all those chess database programs such as ChessBase and Nicbase,
> it might be important to either transmit or store positions as compactly
> as possible (ignoring the fact that these programs handle games instead
> of positions!).
> If an algorithm can be made that plays the position guessing game
> at a reasonable level, then it would be profitable to represent games
> as the sequence of answers to the questions posed by this algorithm.
>
> just dreaming...
>
> John Tromp (tr...@cwi.nl)
Hi. I have no real answers, only more questions and dreams. :-)
I am serious however. I am not a great chess player or chess programmer.
But read on if interested.
Consider all the (legal and possible) configurations of pieces as
forming points in a space. [I am not a mathematician either :-)]
The legal moves then form directed lines between these points thus
defining a connectivity rule. [The rules are complicated because
there are two types because of W or B moving but that is only
technical.] Also, `history' dependent moves must be excluded. In
this space there are boundary points (for respective W or B)
corresponding to `the game is over'.
Picture a game of chess as a sequence of moves starting at a
specified point in the space with a specified player W (for
definiteness) moving first. The `move' is simply a travel to an
adjacent point (as defined by the connectivity rule). Thus after W
moves, B moves by selecting a new point connected to the point W
selected. The drive for each player is to reach a winning boundary
point as quickly as possible while preventing his opponent from
doing the same OR to try to hold off a loss - if the loss in
inevitable. Still another favorable situation - if a win is not
possible and a loss is not inevitable is to try for a stalemate or
draw.
There is a well defined algorithm to `integrate' in from the
boundary points to the interior points. (Interior points are points
that are not boundary points.:-) I can write the algorithm here but
I want you (everyone who cares) to think about it. Think Minimax.
Part of the answer will be that for every point there is a
pair of numbers - one for B leaving the point and the other for W.
The number for W (for example) will indicate to her the minimum
number of moves to a win OR a maximum number of moves to a
loss OR neither of these (draw). The number will not lie if both
players perform optimally. If W makes a mistake, then B may do
better than he originally was told. Etc...
The other part of the solution is the optimal (set of) move(s)
each player needs to take starting from any point.
Quite obviously, there is no room for statistics here, however,
the number of points is VERY large. Only for the simplest end games
can this algorithm be practically applied. [E.g. K, Q, k, n, b on
a 6X6 board is somewhat hard to handle (but not impossible) on my
computer.]
The practical use of such an algorithm is to compare it with
imperfect and much more practical algorithms to see how good they
really may be - at least as far as the herin severe restrictions let
them solve the same game.
O /
-------------------------------- X --- cut here -----------------------------
bob jones O \
Disclaimer: "I just said what?"
internet: jo...@ohstpy.mps.ohio-state.edu
US mail: robert jones, POBox 3194, Columbus, OH, 43210
telephone: (614)-447-0214 (home) and (614)-292-1648 (school)
pi: 3.14159265358979323846264338327950288419716939937510582097494459230781...
e: 2.71828182845904523536028747135266249775724709369995957496696762772407...
=============================================================================