recording chess games in very few bits per move
toby robison
EFFICIENT NOTATION OF CHESS GAMES, IDEAL SOLUTIONS
This article is Copyright (C) Tobias D. Robison, 1993, Princeton, NJ, USA.
Please acknowledge the author when quoting the article.
A few days ago, I proposed the following problem:
Using ordinal move generation, it is possible to record chess moves
in considerably less than one byte per move (on the average). This
is particularly true if one accepts methods of compressing a game
that are possible but rather impractical. For example, to get nearly
ideal solutions, I shall allow methods that could require many hours
to record or play back a game, and methods in which an error of a
single bit would make it very difficult to reconstruct the actual
game.
My thanks to the following:
- Roger Fry, who in 1974 helped me work out the basics of these
solutions.
- Mike Keith and Bryan Astle, who suggested a lot about the
effective use of compression on these solutions.
- Roland Hubscher (rol...@tigger.cs.colorado.edu) and
Dean Inada (d...@questrel.questrel.COM), who responded to my
original posting, identifying ideal solutions and suggesting
further considerations.
- Edward Maillet (mai...@skye.usmcs.maine.edu), who posted my
original posting for me.
Here are some approaches toward ideal solutions:
(BACKGROUND: ordinal move generation is some method of ordering all
the legal moves in a chess position. If the recorder and game player
share the same algorithm, a move can be notated simply as the
ordinal number. For example, we might agree to consider the leftmost
piece on the lowest numbered rank first, and consider its
southernmost move first, and so on. In a position with 40 legal
moves, the moves will be notated as 0,1,2,3,...39. In this way, a
White first move of N-QR3 might be notated by 0, while P-KR4 would
be 19. (The special problem of notating the end of the game is
discussed below.)
It was previously observed that in legal positions, There are never
more than 256 possible moves. Therefore we could use ordinal notation to
record each move of a game in a single byte, allowing 256
possibilities per move (more than enough). HOWEVER as most people
are aware, positions with more than 32 moves are common,
but positions with more than 64 moves are rare.
Therefore using one full byte per move is wasteful.
IMPROVMENT #1:
When recording a move or playing back the game, our algorithm will
first determine just how many legal moves there are on the board.
(Unfortunately, this means our algorithm will not handle games with
illegal moves, which unfortunately exist and are even published for one's
reading pleasure.) Suppose in a given position we determine that there
are 40 legal moves. Then we will record this move as an ordinal number
IN SIX BITS, which suffices to record the values from 0 through 39.
When playing back the game, our algorithm would reason as follows:
In the current position there are 40 legal moves. Therefore we read the
next 6 bits from the game data, and treat it as an ordinal number.
This approach probably averages about 5.5 bits per move, maybe a
little less. (In all the average bit values that I claim here, I'm
making reasonable guesses).
IMPROVMENT #2:
The above approach clearly wastes about 1/2 bit per move. For
example, in the COMMON middle game cases of slightly more than 32
possible moves, we use 6 bits when 5 bits would ALMOST suffice. We
can recover this waste space by using a kind of modular arithmetic.
The simplest way to explain this approach is to explain how to play
back the game. Given this information, you should have little
trouble figuring out how to record it.
First, we regard the moves of the game as recorded in a single giant
integer value. For a 40 move game, the number is probably about
400 bits large. To record and play the game, we need the ability to
perform integer arithmetic upon numbers this size. Obviously we
have to record how many bits there are in the total game number.
To play back a move, we first determine how many legal moves there
are in the current position. For example, on the first move, white
has 20 possibilities. So we take the number 20 and divide it into
the number that represents the game.
From this division we get a quotient and a remainder. The remainder
is the ordinal number of the move. The quotient is the new game number
that we similarly process to determine the next move of the game, and so on.
When the quotient is zero, we process the remainder and the game is over.
This approach recovers the half-bit (or so) that we are wasting. I
think it yields just below 5 bits per move. This approach is even
moderately practical; but note that since there is almost no
redundancy in the game data, a small mistake in recording the game
would make it very difficult to correct the error.
IMPROVMENT #3:
We now leave the realm of practicality altogether, to record moves
in 3 bits or less, on the average.
We introduce a new method of ordinal move generation. For both the
recording and playback of a game, we agree to share a program that
will analyze the position at each move and order the moves according
to the likelihood that a player would make them. Thus, if we
record a move as 5, we mean that the payer played the 6th most
likely move (the move possibilities are recorded as 0,1,2,... n-1).
This program would play games rather slowly, using today's fastest
computers. It has to do more than pick a best move; it has to decide
which is second best, third, etc., for every position.
To work really well, the program would need information about the
player's approximate strengths and the date the game was played.
This information requires some bits, and would wipe out some of the
savings we will otherwise achieve. For the fun of it, let's concentrate on
20th century games played at the master level and above, for which
just a few bits of strength and date data might suffice.
In order to see how a "preference" nominal ordering saves space,
consider the following simpleminded compression algorithm: If a
player makes one of the seven most likely moves, we will use just 3
bits to record the choice, using codes 0,...6. But on the rare cases
where a player makes some other move, we will record this choice as
a 3-bit code of 7, followed by a code using the IMPROVEMENT #2
algorithm for the remaining possibilities. We hope that MOST moves
will thus require only three bits. (Some will require even less, in
forcing positions.) A few "bizarre" moves, and some moves in the
opening, will require 7 or 8 bits. The average will be close to 3
bits!
Suppose we are even more optimistic -- we could notate the 3 most
likely possibilities as 0,1,2 and use the code of 3 to specify that
a less likely move follows. A really good predictor program would
now average almost 2 bits per move. I'M JUST BEING INTUITIVE, but I
don't believe in this level of predictability; people are just not
that predictable, in my experience.
Dean Inada suggests a fascinating refinement to this approach: the
program that orders moves according to their likelihood of being
played should not concentrate on finding the "best possible moves"
(unless one of the game players is a computer!). Rather, it should
try to imitate the process humans use to select moves. Although this
would result in occasional whopping errors, the errors would not be
significant as long as the program were usually correct. Such a
program might concentrate on looking at the 8 most likely moves that
a human might pick, to analyze a few ply deep, selecting only a few
moves per ply.
IMPROVEMENT #4:
There are however types of positions in which there are few
reasonable moves. Our algorithm could "score" each position on its
"reasonability complexity" and use 2, 3 or 4 bits for the
"unbizzarre" move choices, rather than always using 3 (or 2). This
approach could get the average down a little below three bits!
IMPROVMENT #5:
Approaches 3 and 4 above can be improved slightly by using really
good compression schemes, such as Huffman encoding. Some compression
schemes can take into account the PROBABILITY (Dean Inada's
suggestion) of making each move as well as the ordinal numbering, to
compress even better. Unfortunately I'm technically over my head
here so I can't give specific examples of how to do this.
Intuitively, I still think the best possible result for high level
(and thus more predictable) games is close to three bits, perhaps
something like 2.75.
IN SUMMARY, most "good" chess games can be recorded in less than 250
bits (a 40-move game), perhaps as little as 200 bits. In the early
1970's, I felt that this would allow all worthwhile games ever
played to be recorded on one floppy disk. Today I think this is
still true, since floppy disks can record a lot more data. Now
that's amazing!
THE "GAME-END NOTATION" PROBLEM:
Any notation scheme must make it possible to figure out when the game
is over. This can be done in two ways:
(1) We precede the game data with a count of the number of bits
in the game.
(2) Every move includes the notation of one additional legal
possibility, that the game ends.
The most efficient AVERAGE approach might be to include a single bit
at the beginning of the game that indicates WHICH of these two
approaches is used. One approach, for a specific game, will save
several bits over the other.
You might think that a position with only a single forced move can
be notated in zero bits! However this creates an ambiguity at the
end of the game. Suppose we are using approach 1 and a game ends
during a series of forced moves. We must use one bit per move to
show how many forced moves were made before the game ended. (Yes,
there are even positions in which BOTH players are forced to make a
series of moves!)
We can still use these single bits somewhat efficiently. Let's say
that a zero means a single forced move follows, and a 1 means that
both players make a forced move. A game that ends after three forced
moves would have its last two bits as: 1 0.
OPEN ISSUES FOR FURTHER DISCUSSION:
(a) How many different ways can a game end, that are worth notating?
After the game is over, perhaps there would be a fixed code of 6
bits to denote how the game ended. Would anyone care to try to
suggest a canonical list of different terminations that are worth
notating? Avoiding the trivial (player was hit with a meteor
instead of a truck), there are still many cases of interest to chess
players. I've been maintaining a list, to which I had never until
recently thought to add this case:
Player to move, being advised by the promoter that the match better
end soon, resigns.
(b) What is the most efficient way to notate chess POSITIONS? The
fascinating thing here is that most legal positions can be
CONSTRUCTED by making up a game that achieves the position. Such a
game would not consist of "likely" moves, but we can certainly
notate it in about 5 bits per move, or perhaps 300 bits in a fake
30-move (by each player) game to achieve the position. Interesting
middle game positions, the kind most often published, can be notated
by simply providing the game score up to that point, at 2.75 bits
per move (perhaps 25*2*2.75 = 137 bits for an interesting position).
COULD IT BE THAT THE TIGHTEST WAY TO NOTATE A POSITION IS TO NOTATE
THE ENTIRE GAME LEADING UP TO IT?
The problem of notating positions is actually much more complex than
notating games. I shall discuss this problem soon, probably next week.
Dean Inada states the upper bound ideal solution as:
lg(64!/(32!*15!*15!)*6^30) = 176 bits
I have been presented in the past with wildly different solutions to
this problem. I doubt there is a way to "prove" which is ideal.
Solutions would simply have to be tested on thousands of positions
to see how they compare.
-- toby robison, not robinson.