Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

estimated number of chesspositions

525 views
Skip to first unread message

Vincent Diepeveen

unread,
Oct 27, 1995, 3:00:00 AM10/27/95
to
The number of possible chesspositions is less then 2^164, as
it is possible to store easily a chessposition in 164 bits.
Just build a huffman tree out of the pieces, and include
neutral as an element (coded with 1 bit).

I'm currently looking how much bits you need to encode a
position using arithmetic coding.

Vincent Diepeveen
vdie...@cs.ruu.nl
--
+--------------------------------------+
|| email : vdie...@cs.ruu.nl ||
|| Vincent Diepeveen ||
+======================================+

Joe Stella

unread,
Oct 28, 1995, 3:00:00 AM10/28/95
to

jocu...@ix.netcom.com (Jeffrey O. Curtis) writes:

>It is my understanding that the Chess Assistant team found a way of
>encoding a chess position into 64 bits.


I am having trouble with this one. 64 bits is one bit per square, and
one bit is not enough information to tell which piece in on a square.

If somebody is claiming this, they must be talking about some kind of
*average* number of bits per position. I mean that the original
position is represented by much more than 64 bits, but all the
positions that are derived from the original position can be represented
by just the move(s) it took to get to the derived position from the
original. The move (or moves) can be represented in less than 64
bits, resulting in an average of 64 bits/position.

Joe S.

Abraham S. Mantell

unread,
Oct 28, 1995, 3:00:00 AM10/28/95
to
vdie...@cs.ruu.nl (Vincent Diepeveen) writes:

>The number of possible chesspositions is less then 2^164, as
>it is possible to store easily a chessposition in 164 bits.
>Just build a huffman tree out of the pieces, and include
>neutral as an element (coded with 1 bit).

>I'm currently looking how much bits you need to encode a
>position using arithmetic coding.

>Vincent Diepeveen
>vdie...@cs.ruu.nl

Hmm...the estimate I recall having read was something like 10^60, whereas
2^164 is "only" about 10^49. This 10^60 figure appeared in Science News
a while back.

Abe

man...@rpi.edu


Jeffrey O. Curtis

unread,
Oct 28, 1995, 3:00:00 AM10/28/95
to
vdie...@cs.ruu.nl (Vincent Diepeveen) wrote:

>The number of possible chesspositions is less then 2^164, as
>it is possible to store easily a chessposition in 164 bits.
>Just build a huffman tree out of the pieces, and include
>neutral as an element (coded with 1 bit).

>I'm currently looking how much bits you need to encode a
>position using arithmetic coding.

Vincent,

It is my understanding that the Chess Assistant team found a way of

encoding a chess position into 64 bits. Can you or anyone else out
there confirm this? If so how did they do it??

Jeff Curtis


Robert Hyatt

unread,
Oct 30, 1995, 3:00:00 AM10/30/95
to
In article <471ncq$4...@ixnews2.ix.netcom.com>,
Jeffrey O. Curtis <jocu...@ix.netcom.com> wrote:
-->man...@alum01.its.rpi.edu (Abraham S. Mantell) wrote:
-->
-->>vdie...@cs.ruu.nl (Vincent Diepeveen) writes:
-->
-->>>The number of possible chesspositions is less then 2^164, as
-->>>it is possible to store easily a chessposition in 164 bits.
-->>>Just build a huffman tree out of the pieces, and include
-->>>neutral as an element (coded with 1 bit).
-->
-->>>I'm currently looking how much bits you need to encode a
-->>>position using arithmetic coding.
-->
-->>>Vincent Diepeveen
-->>>vdie...@cs.ruu.nl
-->
-->>Hmm...the estimate I recall having read was something like 10^60, whereas
-->>2^164 is "only" about 10^49. This 10^60 figure appeared in Science News
-->>a while back.
-->
-->>Abe
-->
-->>man...@rpi.edu
-->
-->Abe And Vince,
-->
-->There are 13 possible "values" for a square accounting for all the
-->different types of pieces plus an empty square. Since values can be
-->repeated, a simple upper bound for the number of chess positions is
-->13^64 or let's say 10^72 positions. This estimate is ridiculously
-->high, of course, since it allows up to 64 copies of each piece and it
-->also includes the empty board! Nevertheless, I don't think anyone
-->will argue that it is an upper bound.
-->
-->Vincent,
-->
-->The upper bound above is significantly higher than your 2^164 or
-->10^50, and I like your Huffman tree idea but I get a different answer
-->for some reason. Does your Huffman tree account for pawn promotions?
-->For example, games with 3 white Knights or 4 Queens, etc.? since
-->these are also legal positions? My data structure skills are weak but
-->I get significantly more than 164 bits when I try to take into account
-->the kinds of piece combinations that may result from pawn promotions.
-->Just a little confused about how you constructed your tree. [?]
-->
-->Jeffrey O. Curtis
-->
-->
-->


We need Burt Wendroff's input here as I don't have his ICCA article on
hashing close by, but somewhere around 160 bits is enough to accurately
and unambiguously store a complete chess position. The trivial case
would be to use 3 bits/square, 6 bits to id each square. max would be
9x32 (32 occupied squares, 9 bits to identify each) plus (say) a couple
of bits for castling/enpasant status. This produces a very large key,
but Burt then explained how it can be "losslessly compressed" to (I think)
something around 160 bits. We don't use it because computing such a hash
key is expensive and (so) far unnecessary.
--
Robert Hyatt Computer and Information Sciences
hy...@cis.uab.edu University of Alabama at Birmingham
(205) 934-2213 115A Campbell Hall, UAB Station
(205) 934-5473 FAX Birmingham, AL 35294-1170

Robert Hyatt

unread,
Oct 30, 1995, 3:00:00 AM10/30/95
to
In article <471jmd$1...@ixnews5.ix.netcom.com>,

Jeffrey O. Curtis <jocu...@ix.netcom.com> wrote:
-->j
-->jo...@ultranet.com (Joe Stella) wrote:
-->
-->
-->> jocu...@ix.netcom.com (Jeffrey O. Curtis) writes:
-->
-->>>It is my understanding that the Chess Assistant team found a way of
-->>>encoding a chess position into 64 bits.
-->
-->
-->>I am having trouble with this one. 64 bits is one bit per square, and
-->>one bit is not enough information to tell which piece in on a square.
-->
-->>If somebody is claiming this, they must be talking about some kind of
-->>*average* number of bits per position. I mean that the original
-->>position is represented by much more than 64 bits, but all the
-->>positions that are derived from the original position can be represented
-->>by just the move(s) it took to get to the derived position from the
-->>original. The move (or moves) can be represented in less than 64
-->>bits, resulting in an average of 64 bits/position.
-->
-->> Joe S.
-->
-->
-->I was suspicious of the claim also Joe, though I don't want to
-->attribute it to the Chess Assistant team itself, nor do I want to
-->completely trust my memory at this point. I worked for about a week
-->on the problem of "The Minimal Structure to Store any Possible Legal
-->Chess Postion" over a year ago and didn't make much progress. However,
-->as chess-playing programs and programs which implement databases of
-->position trees blend into one, it seems to me this problem is becoming
-->more significant.
-->
-->One rather exotic (read "probably useless") method of storing a chess
-->position would be as a sequence of "words" in the letters
-->R,N,B,Q,K,P,r,n,b,q,k,p,s (s is for a blank square) where each
-->sequence is mapped to a bit sequence of a specified length sufficient
-->to account for all possible "words" in the "chess vocabulary". A
-->chess position is then a series of such words. A chess sentence, if
-->you will.
-->
-->If I use 4 letter words for example, the initial position is described
-->by 64/4 or 16 words and the number of bits required is 16n + 1 where n
-->is the bit length for one four-letter word and the extra bit specifies
-->whose move it is. The question then becomes how many 4-letter words
-->are there in the chess vocabulary since this determines the minimum
-->number of bits necessary to specify all 4-letter words. RNBQ for
-->example occurs in the initial position and is therefore "in the
-->vocabulary", but BNBQ is highly unlikely, and rKrQ, or rKqs, or sKks,
-->or pkpk are impossible. I only mention these examples since someone
-->will tell me there are 13^4 4-letter words which can be constructed
-->from the 13-letter alphabet described above. And this would require
-->at least ln(13^4)/ln(2), or 15 bits! A chess sentence is then 241
-->bits long; not very efficient. I claim that many of these words can
-->be tossed out.
-->
-->There are many variations on this theme. One could increase the word
-->length for example. Or one could read the chess words in different
-->ways, right-to-left/top-to-bottom; top-to-bottom/right-to-left; or in
-->blocks, i.e., a8/b8/a7/b7 followed by c8/d8/c7/d7, etc. Each method
-->of "reading" has its own grammar and some would be more efficient than
-->others. Presumably there is even a minimalist grammar but don't ask
-->me what it is!
-->
-->I am not suggesting that there is anything to be gained from this
-->particular line of thinking; and, since I have not even begun to write
-->a chess program, my credibility on these matters is zilch. I merely
-->offer these thoughts to show that there are other ways of thinking
-->about a "chess position" mapped to bits other than (3 bits for piece +
-->1 bit for color) x (64 squares) + 1 for color on-move = 257 bits per
-->position which is also a very inefficient method.

-->
-->Jeffrey O. Curtis
-->
-->
-->
-->


They are probably using the "Zobrist" algorithm that most of us use to
hash a position for the transposition/refutation table. This does, in fact,
reduce a chess position to 64 bits, but not without potential errors. In
any case, I've used this approach since 1972 or so (although only 32 bits
until I moved to the Cray machines in 1980) with good results. I also use
it in Crafty's opening book, which (currently) contains 120,000 games. A
year or two ago, we had a long thread about hashing and errors; I ran some
tests where I searched several billion positions, looking for such errors,
without encountering a single one, and concluded that the 64bit hashing was
relatively safe. In any case, the idea is to produce a set of random numbers,
stored in an array "ran[64][12]" where the first subscript is the square
number, the second is the square contents if it is non-zero (not empty). You
simply exclusive-or these numbers which produces a 64-bit random hash-key that
is really nicely distributed over the 2^64 possible keys.

Bob

Mike Leahy (BOOKUP)

unread,
Oct 30, 1995, 3:00:00 AM10/30/95
to
jo...@ultranet.com (Joe Stella) wrote:
>
> jocu...@ix.netcom.com (Jeffrey O. Curtis) writes:
>
>>It is my understanding that the Chess Assistant team found a way of
>>encoding a chess position into 64 bits.
>
>
>I am having trouble with this one. 64 bits is one bit per square, and
>one bit is not enough information to tell which piece in on a square.
>
>If somebody is claiming this, they must be talking about some kind of
>*average* number of bits per position. I mean that the original
>position is represented by much more than 64 bits, but all the
>positions that are derived from the original position can be represented
>by just the move(s) it took to get to the derived position from the
>original. The move (or moves) can be represented in less than 64
>bits, resulting in an average of 64 bits/position.
>
> Joe S.


Hey Joe,

The approach of deriving a position from the initial position is
handy -- but only in a game database. That approach would
completely fail to account for transpositions in a positional
product like BOOKUP.

Mike Leahy
"The Database Man!"


Vincent Diepeveen

unread,
Oct 31, 1995, 3:00:00 AM10/31/95
to
In <DHAG...@mv.mv.com> s...@mv.mv.com (Steven J. Edwards) writes:

>hy...@willis.cis.uab.edu (Robert Hyatt) writes:

>>We need Burt Wendroff's input here as I don't have his ICCA article on
>>hashing close by, but somewhere around 160 bits is enough to accurately
>>and unambiguously store a complete chess position. The trivial case
>>would be to use 3 bits/square, 6 bits to id each square. max would be
>>9x32 (32 occupied squares, 9 bits to identify each) plus (say) a couple
>>of bits for castling/enpasant status. This produces a very large key,
>>but Burt then explained how it can be "losslessly compressed" to (I think)
>>something around 160 bits. We don't use it because computing such a hash
>>key is expensive and (so) far unnecessary.

>160 bits sounds too low to me. Perhaps that is the average length for
>a variable representation scheme.

Not at all. It seems too high for me.

>Let's see one possibility:

>side to move: 1 bit
>castling availablility: 4 bits
>en passant target file: 4 bits (may be no en passant file)
>captured status: 30 bits: one per man, in order, kings not included
>pawn promotion type: 48 bits: three per pawn, in order
>piece location: 192 bits: six per man, in order

That is the uncompressed approach:
Read the bit stream from left to right:
1 = neutral square
So after reading 1 bit that is a 1 you know that next square is empty.
So 32 bits are needed for 32 squares.
Idem for the rest of the pieces (they all start with a 0).
That are 164 bits at maximum.

This is called huffman compression.

Using arithmetic coding you are able to use less then 1 bit for
a neutral square, or a pawn.

>Total: 1+4+4+30+48+192 = 279 bits = 9.7*10^83
164 bits are already <= 10^49
Not to mention arithmetic compression.

>However, since no two pieces can be on the same square, it is possible
>to do away with the "captured status" vector by assigning captured
>pieces to be on the king square of the same color:
>
>Total: 1+4+4+48+192 = 249 bits = 2.3*10^74
>
>En passant pawn targets could be placed on their first rank to get rid
>of the ep target file:
>
>Total: 1+4+48+192 = 245 bits = 1.4*10^73
>
>By taking advantage of the fact that two pieces can't be on the same
>square, the piece locations can be coded in log2(64!/32!) bits = 179
>bits. Adding back the 4 bits for the ep file:
>
>Total: 1+4+4+48+179 = 236 bits = 1.1*10^71
>
>The pawn promotion vector really encodes 5 values for each of 16
>pawns, so it can be represented in log2(5^16) = 38 bits:
>
>Total: 1+4+4+38+179 = 226 bits = 1.1*10^68
>
>Another try by square content:
>
>side to move: 1 bit
>castling availablility: 4 bits
>en passant target file: 4 bits (may be no en passant file)
>square contents: 256 (4 bits for each square)
>
>Total: 1+4+4+256 = 265 bits = 5.9*10^79
>
>So, 226 bits appears to be the least upper bound that can be easily
>computed. Perhaps others can do better.
>
>-- Steven (s...@mv.mv.com)

Steven J. Edwards

unread,
Oct 31, 1995, 3:00:00 AM10/31/95
to
hy...@willis.cis.uab.edu (Robert Hyatt) writes:

>We need Burt Wendroff's input here as I don't have his ICCA article on
>hashing close by, but somewhere around 160 bits is enough to accurately
>and unambiguously store a complete chess position. The trivial case
>would be to use 3 bits/square, 6 bits to id each square. max would be
>9x32 (32 occupied squares, 9 bits to identify each) plus (say) a couple
>of bits for castling/enpasant status. This produces a very large key,
>but Burt then explained how it can be "losslessly compressed" to (I think)
>something around 160 bits. We don't use it because computing such a hash
>key is expensive and (so) far unnecessary.

160 bits sounds too low to me. Perhaps that is the average length for
a variable representation scheme.

Let's see one possibility:

side to move: 1 bit
castling availablility: 4 bits
en passant target file: 4 bits (may be no en passant file)
captured status: 30 bits: one per man, in order, kings not included
pawn promotion type: 48 bits: three per pawn, in order
piece location: 192 bits: six per man, in order

Total: 1+4+4+30+48+192 = 279 bits = 9.7*10^83

However, since no two pieces can be on the same square, it is possible

Jeffrey O. Curtis

unread,
Oct 31, 1995, 3:00:00 AM10/31/95
to
vdie...@cs.ruu.nl (Vincent Diepeveen) wrote:

>In <46rufg$9...@ixnews2.ix.netcom.com> jocu...@ix.netcom.com (Jeffrey O. Curtis) writes:

>>vdie...@cs.ruu.nl (Vincent Diepeveen) wrote:
>>
>>>The number of possible chesspositions is less then 2^164, as

>>>it is possible to store easily a chessposition in 164 bits.

>>>Just build a huffman tree out of the pieces, and include

>>>neutral as an element (coded with 1 bit).
>>

>>>I'm currently looking how much bits you need to encode a

>>>position using arithmetic coding.
>>
>>Vincent,
>>

>>It is my understanding that the Chess Assistant team found a way of

>>encoding a chess position into 64 bits. Can you or anyone else out
>>there confirm this? If so how did they do it??
>>
>>Jeff Curtis
>>

>First you must not forget that there is a difference between
>storing a chessposition lossles and lossy. Lossy means losing information.
>I was talking about storing a chessposition in 164 bits lossles.

>Using 64 bits and for example Zobrist hashing (as most
>chess-hashtables use), take a 64 bits hashposition:
>this means that there are a lot of positions that would
>get the same 64 bits. However as the chance is very small that this
>happens, all chessprogrammers take that risk.

>Besides there is another problem in hashing:
>If you have a position, then you can make a 64 bits hashing of it.
>If you have a 64 bits hashing then it is quite hard to extract
>the chessposition out of it. In fact it is not very smart doing it.
>And IF you succeed, then you will have more then 1 position, in the
>worst case.

>Now about 164 bits lossles:
>I want to encode every piece on the board and decode it back.
>First observation is that there 64 squares on the board.
>Next observation is that there are more neutral squares then
>there are squares that contain a white king, for example.

>Using huffman:
>To encode a neutral square, we should use less number of bits then
>encoding a white king.

>Now huffman has given us a beautiful algorithm:
>next msg an example how it works.

>Vincent.

Vincent and Bob,

I look forward to a closer look at the Huffman algorithm. I am also
interested in doing some reading on this Zobrist hashing you both
speak of. Any references to get me started would be most appreciated.

Jeffrey O. Curtis

Urban Koistinen

unread,
Oct 31, 1995, 3:00:00 AM10/31/95
to
Steven J. Edwards (s...@mv.mv.com) wrote:
hy...@willis.cis.uab.edu (Robert Hyatt) writes that about 160 bits
is all that is needed to store a chess position.

: 160 bits sounds too low to me. Perhaps that is the average length for
: a variable representation scheme.

: Let's see one possibility:

: side to move: 1 bit
: castling availablility: 4 bits

Count to one or less if you use arithmetic coding.
Example:
Use one bit to say if there is any castling possibilities at all,
then if there is, you use four bits to tell which castling
possibilities are available. The four bits will be saved later
because you will know the position of at least one king and a rook.
Saving 6+

: en passant target file: 4 bits (may be no en passant file)

Again you use one bit to tell if there is an ep file, and if
there is, you encode it with 3 bits. Then you save later by
knowing the position of a pawn and an empty square.
Saving 3+1 bits.

Maybe there should be one bit that say if there is either
any castling possibilities or ep target file. That way
storing castling possibilities AND ep target file would use
one bit in total.

: captured status: 30 bits: one per man, in order, kings not included


: pawn promotion type: 48 bits: three per pawn, in order
: piece location: 192 bits: six per man, in order

: Total: 1+4+4+30+48+192 = 279 bits = 9.7*10^83

: However, since no two pieces can be on the same square, it is possible
: to do away with the "captured status" vector by assigning captured
: pieces to be on the king square of the same color:

: Total: 1+4+4+48+192 = 249 bits = 2.3*10^74

What of this then:

Position of kings: 12 bits
Occupied squares: 62 bits
Color of pieces: 30 bits
Pawns: 30 bits
Other pieces: 14*2 = 24 bits

Each two (rounded up) promoted pawns change the number of bits
as follows:

Other pieces: +4
Color of pieces: -1
Pawns: -1
There might be at most 10 promoted pawns as a pawn capturing a
piece is the same as capturing a promoted pawn when counting bits.
Promotions thus cost: 5*(4-1-1)=10 bits

1+1+12+62+30+30+24+10 = 170 bits

Further, you could save some more by knowing that pawns can not be
on the first and last rank:
Each piece that is on the first or last rank can be encoded using
1 bit less than otherwise.

Now use this to allow encoding of empty squares to use less than
one bit.

Problem: chose x to maximize min(x,2*(1-x))

x = 2/3

saving is log2((x^14)/((1/2)^14)) = log2((4/3)^14) bits approx 5.8 bits

So, now I have an upper bound of 165 bits.

By counting possibilities further I think a few more bits can be
saved.
--
Urban Koistinen - e...@algonet.se

Urban Koistinen

unread,
Nov 1, 1995, 3:00:00 AM11/1/95
to
Dennis Breuker (bre...@cs.rulimburg.nl) wrote:

: In the ICCA Journal (Vol.17, No.3) Balkenhol says that in general
: 136 bits is sufficient. He gives a reference to Nievergelt (1977):
: Information Content of Chess Positions. ACM SIGART Newsletter 62, pp. 13-14.
: I dug up this article, and Nievergelt states:
: "136 bits suffice to determine *any* legal chess position (of which
: there are about 10^40"
: However, he does not say how he calculated this number. (BTW 2^136 is
: about 8*10^40)

Maybe this is the number Shannon gave, passed on from one paper to
the next. He gave the approximation 10^43 but I don't think he
considered promoted pieces.
Have a look at 64!/(32!*8!^2*2!^6) in
"Programming a Computer for Playing Chess" reproduced in Computer Chess
Compendium by David Levy, first chapter in the book.

: And I remember to have read something about compressing a position in
: 140 bits. Unfortunately, I can't remember where. Anyone?

: I need this for my thesis.

I hope you verify your figures. I saw a paper from UCSD that was
very bad. Don't copy others work without understanding it.
Be careful.

I can be argued, as I have elsewhere, that you should include all
positions that have been seen since the last irreversible move when
you count the number of positions because it may cause a position
to be drawn that would otherwise have been won or lost.

Vincent Diepeveen

unread,
Nov 1, 1995, 3:00:00 AM11/1/95
to
In <473rav$8...@ixnews2.ix.netcom.com> jocu...@ix.netcom.com (Jeffrey O. Curtis) writes:


>>>vdie...@cs.ruu.nl (Vincent Diepeveen) wrote:

>>>>The number of possible chesspositions is less then 2^164, as
>>>>it is possible to store easily a chessposition in 164 bits.
>>>>Just build a huffman tree out of the pieces, and include
>>>>neutral as an element (coded with 1 bit).

>>>>I'm currently looking how much bits you need to encode a
>>>>position using arithmetic coding.

I guess this will take many weeks as i first am gonna play few
tournaments (Open Dutch computerchess champs and after that dutch
computerdraughts (10x10) rapid champs).

>>Using huffman:
>>To encode a neutral square, we should use less number of bits then
>>encoding a white king.

The way to build a huffman tree is described in all books claiming to
be an introduction in data compression. So for extended info open just
1 of these books.

The idea is simple: connect the 2 lowest frequencies together, assign
them 1 and 0 and create a root node from it. Repeat the connect step
until you have a tree.

I represent pieces by abbreviations, 'wk' means white king.
'__' means neutral square.

First a list of pieces and their frequency, then building the huffman tree.
to read the code needed to encode it: read the tree from under to above.
Consider it a tree. There are more ways to encode it, but that will
still give you 64 bits.

__ wp bp wr br wn bn wb bb wk bk wq bq (horizontal sum)
32 8 8 2 2 2 2 2 2 1 1 1 1
1 0 1 0 (2)
1 0 1 0 1 0 1 0 (4)
1 0 1 0 (8)
1 0 1 0 (16)
1 0 (32)
1 0

so:
__ = 1
wp = 011
bp = 010
wr = 00111
br = 00110
wn = 00101
bn = 00100
wb = 00011
bb = 00010
wk = 000011
bk = 000010
wq = 000001
bq = 000000

>I look forward to a closer look at the Huffman algorithm. I am also
>interested in doing some reading on this Zobrist hashing you both
>speak of. Any references to get me started would be most appreciated.

Zobrist hashing:
take a random number for every piece on every square.
To calculate the hashing of a position, so the mark of a position
do next: exclusif or every piece on every square with its number.

So King on a1 and black king on g8:

hashing = randomnumber[white][king][a1] ^ randomnumber[white][king][a1];
When you move the king from a1 to a2 you only need to update the
key by hashing

hashing = hashing ^ randomnumber[white][king][a1];
and
hashing = hashing ^ randomnumber[white][king][a2];

Very simple.
The problem is that you need really random numbers. SO DON'T USE THE
PC'S FUNCTION RAND FOR THAT, BECAUSE THIS FUNCTION DOESN'T GIVE RANDOM
NUMBERS, and gives you a lot of hashing faults.

Vincent.

Tim Mann

unread,
Nov 1, 1995, 3:00:00 AM11/1/95
to
OK, I can't resist jumping in here. Generally, the people who
understand how to compress positions best haven't fully explained
their schemes.

Here is a simple Huffman code that uses 164 bits to represent the
positions of all 32 pieces in the standard chess set. Additional bits
are required for side to move, castling availability, and en passant
availability. Fewer bits are required after a piece is captured, but
more are required if a pawn is promoted (something Vincent Diepeveen
and others haven't mentioned), so in the worst case more than 164 bits
can be required. Here are the details.

Read the chess board left-to-right, top-to-bottom, and represent each
square with a variable number of bits. The idea of Huffman coding is
to choose each bit so that it selects between alternatives that are
equally likely. For instance, in the initial position exactly half
the squares are empty, so the first bit says whether a square is
empty. Here is one possible choice for all the codes. (I put the
piece color bit last for a reason to be explained later.)

square code number initially total bits initially
----- ---- ---------------- --------------------
empty 0 32 32
wP 100 8 24
bP 101 8 24
wN 11000 2 10
bN 11001 2 10
wB 11010 2 10
bB 11011 2 10
wR 11100 2 10
bR 11101 2 10
wQ 111100 1 6
bQ 111101 1 6
wK 111110 1 6
bK 111111 1 6
------
164

In the worst case, both players might promote all their pawns to
queens without capturing anything. (Actually this isn't possible,
because the pawns can't get by each other without capturing something,
but it's certainly an upper bound.) In that case the 16 pawns would
each take 3 more bits to represent, bringing the number of bits up to
212. However, I doubt that a position needing more than 164 bits
would arise in real play, as usually several men have been captured
before any pawn is promoted, even in wild King's Gambit lines that
have promotion in the opening.

You can bum out 1 bit by observing that there must be two kings of
opposite color, so you can omit the color bit (the last bit) from the
second king's code.

There are lots of tricks for reducing the number of bits for castling
and en passant, at least in the average case. Urban Koistinen
sketched some of them. To be concrete, I'll just suggest these: If a
king or rook is not on its original square, you can simply omit the
availability bit for castling moves that involve it. This requires
putting those bits at the end, so you know what the board looks like
when you get to them, and thus know which ones will be there.
Similarly, if no pawn of the side to move is on its 5th rank with an
opposing pawn beside it, no en passant bits are needed. If only one
pawn of the side to move is in this situation, only 1 (yes/no) bit is
needed; if there are two or three, 2 bits suffice (with 00 meaning no
en passant, 01 the leftmost, etc.); if there are four or five, 3 bits
suffice. (There can be no more than five, or there would be no room
for opposing pawns beside all of them.)

So with this scheme, the initial position needs 164 - 1 + 4 + 0 = 167
bits. Most other positions require the same or fewer bits; some
unusual positions require more.

Other coding schemes could reduce this further, but this one has the
virtue of being easy to explain and understand.

Note that none of the schemes anyone has proposed deal with the
50-move rule or availability of a draw by repetition. The 50-move
rule wouldn't take many bits; it needs only a move count. But draw by
repetition requires some representation of the game history back to
the last irreversible move, which takes us beyond the realm of storing
just one position.

--Tim

Thomas R. Truscott

unread,
Nov 3, 1995, 3:00:00 AM11/3/95
to
I should have mentioned:
Huffman coding is described in most Data Structures textbooks,
and in any Data Compression textbook.
Also, a search on Lycos turned up an online description in PostScript:
http://cfatab.harvard.edu/nr/bookc/c20-4.ps

Tom Truscott

Thomas R. Truscott

unread,
Nov 3, 1995, 3:00:00 AM11/3/95
to
I cannot resist jumping in here, either. Eons ago I worked on a chess
program that actually did use Huffman coding of the chess positions
for the on-disk book. I think we convinced ourselves that
22 bytes (176 bits) was plenty, since e.g. to queen the first pawn
there has to be a capture.
I think we handled en-passant by swapping the en-prise pawn
with an impossible square
(for example if a pawn moved e2-e4 then we swapped e1 and e4.)

We were only concerned about minimizing the worst case.
But thinking back on it, we could have done a whole lot better
if we had wanted to minimize the average case.
Something like this: encode each of the 64 squares in turn
by estimating the probability that each piece type is on that square
(no fair peeking!), constructing a Huffman tree from the probabilities,
and then encoding the piece that is actually there.
Suppose the first square we encode is a1. Here is my estimate:
white rook 30%
blank 25%
white king 10%
...
Then we peek a see that a white rook really is on that square,
so we get it encode it in a single bit! (Or maybe 2, depending
on how the Huffman tree works out. We could use "arithmetic
coding" of the Huffman tree which can encode into fractions of a bit.)
Next we encode encode b1. We can take into account our knowledge
that a1 is a white rook, so e.g. the probability of a black piece
is quite low, and indeed if white is on move
the probability of a black king is 0.

This can get more elaborate, but that is the basic idea.

Tom Truscott

Robert Hyatt

unread,
Nov 7, 1995, 3:00:00 AM11/7/95
to
In article <RB1.95No...@uxa.liv.ac.uk>,
Dr R.E. Blundell <r...@uxa.liv.ac.uk> wrote:

-->In article <46qvhf$2...@krant.cs.ruu.nl> vdie...@cs.ruu.nl (Vincent Diepeveen) writes:
-->
-->> From: vdie...@cs.ruu.nl (Vincent Diepeveen)
-->> Newsgroups: rec.games.chess.computer
-->> Date: 27 Oct 1995 15:57:35 GMT
-->> Organization: Dept of Computer Science, Utrecht University, The Netherlands

-->>
-->> The number of possible chesspositions is less then 2^164, as
-->> it is possible to store easily a chessposition in 164 bits.
-->> Just build a huffman tree out of the pieces, and include
-->> neutral as an element (coded with 1 bit).
-->>
-->> I'm currently looking how much bits you need to encode a
-->> position using arithmetic coding.
-->>
-->> Vincent Diepeveen
-->> vdie...@cs.ruu.nl
-->> --
-->
-->Are you sure? I seem to require 177 bits this way - have you included en
-->passant capture and castling in this? Maybe my method isn't optimal as it
-->includes the representation of the possiblity of both moved rooks and moved
-->kings which is unnecessary, but the way I see it is:
-->
-->1 - empty square *32 = 32
-->010 or 011 - pawn *16 = 48
-->00xxxx pieces *16 = 96

This is an actual "shortfall" in your algorithm that will result in larger than
176 bits it would seem, using your algorithm: what about several promoted pieces,
which would save 3 bits per promotion since no pawn is present, bout would add 6
bits per promotion for additional 6-bit piece values. Of course, promotions mean
captures have happened, and I have *not* given much though to how many captures
can be done vs how many promotions are possible. I'll stick with 64bits and
save the headaches... :)


-->
-->total=176
-->
-->where the 16 possible pieces are: r,n,b,q,k R,N,B,Q,K rr,RR,kk,KK pL pR where
-->rr and kk are moved rook and moved king pieces. pL is pawn that may capture en
-->passant to the left, pR is for the right - the colour isn't needed as only the
-->current player could do this.
-->
-->1 for move.
-->
-->=177 bits.
-->
-->Rob
-->---
-->Dr R E Blundell (Email r...@liv.ac.uk),
-->Department of Electrical Engineering and Electronics,
-->University of Liverpool, Brownlow Hill, P.O. Box 147,
-->Liverpool L69 3BX
-->--
-->Dr R E Blundell (Email r...@liv.ac.uk),
-->Department of Electrical Engineering and Electronics,
-->University of Liverpool, Brownlow Hill, P.O. Box 147,
-->Liverpool L69 3BX

Urban Koistinen

unread,
Nov 9, 1995, 3:00:00 AM11/9/95
to
Paul McMahon 3131 (ukc...@serv04.world) wrote:
: Urban Koistinen writes:

: <snip>
: > Ouch! What a waste of codes.
: >
: > As I was wrong earlier, I'll add my improved coding scheme.
: > There might be 12 promoted pawns not only 10 as I wrote earlier.
: >
: > Here goes:
: >
: > Encode side to move in 1 bit
: > Encode the positions of the kings in 2*12 bits.
: > There are 404 impossible positions that I use as follows:
: > 16 gives 4 saved bits, ep file exist:
: > 3 bits to say which file
: > 1 bit to say what side an ep-capturing pawn is on
: > 2*6 bits to say where the kings are
: > save 2 bits later because of 2 known empty squares
: > save 2*3 bits later because of 2 known pawns
: > total saved: 4-3-1+12-2-6=4
: > 256 gives 8 saved bits, castling possibility exist
: > 2 bits to say first castling possibility
: > 6 bits to say where other king is
: > save 5 bits because of 1 known rook
: > 1 bit to say if there are more castling or ep possibilities.
: > then 2 bits to identify castling or ep
: > total saved: 4-2-6+5-1=4
: >
: > Use these codes to encode the remaining squares:
: > 1 empty *36 = 36 or *32 = 32
: > 01x Pp *0 = 0 or *16 = 48
: > 00xxx QRBNqrbn *26 = 130 or *14 = 70
: >
: > total: 1+12+36+130=179 or 1+12+32+48+70=163
: > first number with promotions, second without
: >
: <snip>

: It is possible to promote all 16 pawns if one really tries!
: White makes 4 captures to leave 4 pairs of doubled pawns on the a,c,e & g
: files. Similarly Black makes 4 captures with his pawns to put them on the
: b,d,f and h files. This will increase the number of bits necessary to encode
: the position using your scheme(Although castling and e.p will no longer be
: possible).

After 8 captures and 16 promotions there would be 14+16-8 = 22 pieces
left other than the kings. Less than in my example.

Use these codes to encode the remaining squares:
1 empty *40 = 40
01x Pp *0 = 0
00xxx QRBNqrbn *22 = 110
total: 1+12+40+110 = 163 bits

Vincent Diepeveen

unread,
Nov 9, 1995, 3:00:00 AM11/9/95
to
In <47nckn$m...@aristotle.algonet.se> e...@aristotle.algonet.se (Urban Koistinen) writes:

>Dr R.E. Blundell (r...@uxa.liv.ac.uk) wrote:
>: In article <46qvhf$2...@krant.cs.ruu.nl> vdie...@cs.ruu.nl (Vincent Diepeveen) writes:
>: > The number of possible chesspositions is less then 2^164, as
>: > it is possible to store easily a chessposition in 164 bits.
>: > Just build a huffman tree out of the pieces, and include
>: > neutral as an element (coded with 1 bit).

>: > I'm currently looking how much bits you need to encode a
>: > position using arithmetic coding.

>With 12 promoted pawns:
>1 - empty square *36 = 36
>010 or 011 - pawn *0 = 0
>00xxxx pieces *28 = 168

>total=204

If you promote then i can prove with simple induction
that for every pawn that is promoting a piece is captured.
This also means that there are more neutral squares, which
require only 1 bit at most to encode.

Besides: having more then 2 queens on the board is nonsens.

>: where the 16 possible pieces are: r,n,b,q,k R,N,B,Q,K rr,RR,kk,KK pL pR where
>: rr and kk are moved rook and moved king pieces. pL is pawn that may capture en
>: passant to the left, pR is for the right - the colour isn't needed as only the
>: current player could do this.
>
>: 1 for move.
>
>: =177 bits.
>
>= 205


>
>Ouch! What a waste of codes.

Yep.

>All this counting makes me wonder what the best published
>upper and lower bounds for the number of reachable positions are.
>
>It seem much easier to me to calculate a good upper bound than
>a good lower bound.
>
>To calculate a good upper bound I would first calculate all
>possible combinations of material without regard for position
>and then calculate the number of positions for each of those
>material combinations without regard for check.
>ep and castling I would handle by special pieces that can only
>be placed in one position.
>
>I expect the number of material combinations to be about 2^32
>or less so it should be manageable.
>
>To calculate a not so good lower bound I would place
>the kings in the corners with pieces that don't place the king
>in check around it. Then knights would have to be placed first,
>avoiding the two squares where they would attack the opposing
>king. I would not bother with castling. Positions with pawns
>would not be counted (maybe one pawn).


>--
>Urban Koistinen - e...@algonet.se

S.Read

unread,
Nov 9, 1995, 3:00:00 AM11/9/95
to
(I apologise if I've attributed the first of these quotes to the wrong
( person, but the common practice:
( "A" said:
( >"B" said:
( >>"C" said:
( >>>C-speak
( >>B-speak
( >A-speak
( makes it easy to make a mistake about who said what. I'm using a different
( method: )

UK: Urban Koistinen (e...@aristotle.algonet.se)
UK: In article <47nckn$m...@aristotle.algonet.se>
UK> As I was wrong earlier, I'll add my improved coding scheme.
UK> There might be 12 promoted pawns not only 10 as I wrote earlier.

VD: Vincent Diepeveen (vdie...@cs.ruu.nl) 9 Nov 1995 13:06:16 GMT
VD> If you promote then i can prove with simple induction
VD> that for every pawn that is promoting a piece is captured.
VD> This also means that there are more neutral squares, which
VD> require only 1 bit at most to encode.


I disagree. You can have 16 promotions with only 8 captures.
Consider this:

Pieces move such that two captures become possible:
White pawn captures exd
Black pawn captures dxe
Now there are two white pawns on the d file
Now there are two black pawns on the e file

If the pieces move out of the way, the 2 black pawns and the two white pawns
can promote. That's _TWO_ captures and _FOUR_ promotions.

Extend this and you get 16 promotions for only 8 captures.
someone does cxd then c- and d-pawns promote ( 1 capture)
someone does bxc then b- and c-pawns promote ( 1 capture)
etc.

Simon Read
s.r...@cranfield.ac.uk "lurk before you leap!" 9 NOV 1995 15:00 GMT


Urban Koistinen

unread,
Nov 9, 1995, 3:00:00 AM11/9/95
to
Vincent Diepeveen (vdie...@cs.ruu.nl) wrote:

: In <47nckn$m...@aristotle.algonet.se> e...@aristotle.algonet.se (Urban Koistinen) writes:

: >Dr R.E. Blundell (r...@uxa.liv.ac.uk) wrote:
: >: In article <46qvhf$2...@krant.cs.ruu.nl> vdie...@cs.ruu.nl (Vincent Diepeveen) writes:
: >: > The number of possible chesspositions is less then 2^164, as
: >: > it is possible to store easily a chessposition in 164 bits.
: >: > Just build a huffman tree out of the pieces, and include
: >: > neutral as an element (coded with 1 bit).

: >: > I'm currently looking how much bits you need to encode a
: >: > position using arithmetic coding.

: >With 12 promoted pawns:
: >1 - empty square *36 = 36
: >010 or 011 - pawn *0 = 0
: >00xxxx pieces *28 = 168

: >total=204

: If you promote then i can prove with simple induction
: that for every pawn that is promoting a piece is captured.
: This also means that there are more neutral squares, which
: require only 1 bit at most to encode.

Maybe you can but:
The captured piece might be the same for up to 3 promotions.
Consider the case where all pawns have moved two steps forward,
then the moves: axb5 cxd4, exf5 gxh4 are made.
Now all 12 remaining pawns can be promoted without a single
capture.

: Besides: having more then 2 queens on the board is nonsens.

Not when you are counting the number of legally reachable
positions.

Urban Koistinen

unread,
Nov 9, 1995, 3:00:00 AM11/9/95
to
Vincent Diepeveen (vdie...@cs.ruu.nl) wrote:
: In <47rf0k$f...@aristotle.algonet.se> e...@aristotle.algonet.se (Urban Koistinen) writes:

: >: > Encode side to move in 1 bit


: >: > Encode the positions of the kings in 2*12 bits.

: This is smart: 62 fields left and only 12 bits for the King!

It is a typo, I should have written 2*6=12

: >: > There are 404 impossible positions that I use as follows:


: >: > 16 gives 4 saved bits, ep file exist:
: >: > 3 bits to say which file
: >: > 1 bit to say what side an ep-capturing pawn is on
: >: > 2*6 bits to say where the kings are
: >: > save 2 bits later because of 2 known empty squares
: >: > save 2*3 bits later because of 2 known pawns
: >: > total saved: 4-3-1+12-2-6=4
: >: > 256 gives 8 saved bits, castling possibility exist
: >: > 2 bits to say first castling possibility
: >: > 6 bits to say where other king is
: >: > save 5 bits because of 1 known rook
: >: > 1 bit to say if there are more castling or ep possibilities.
: >: > then 2 bits to identify castling or ep
: >: > total saved: 4-2-6+5-1=4
: >: >
: >: > Use these codes to encode the remaining squares:
: >: > 1 empty *36 = 36 or *32 = 32
: >: > 01x Pp *0 = 0 or *16 = 48
: >: > 00xxx QRBNqrbn *26 = 130 or *14 = 70
: >: >
: >: > total: 1+12+36+130=179 or 1+12+32+48+70=163
: >: > first number with promotions, second without

: Even with binary compression it keeps getting smaller!

: >: It is possible to promote all 16 pawns if one really tries!

: There are at least 8 captures then.

: >After 8 captures and 16 promotions there would be 14+16-8 = 22 pieces


: >left other than the kings. Less than in my example.

: >Use these codes to encode the remaining squares:
: >1 empty *40 = 40
: >01x Pp *0 = 0
: >00xxx QRBNqrbn *22 = 110


: >total: 1+12+40+110 = 163 bits

: I have a feeling that this can be improved, but i guess that arithmetic coding
: will save even much more: that 12 bits is not necessary for coding the
: kings: after putting 1 king on the board you have only 63 squares left...
: ...so you need less then 12 bits. for that.

Yes, my scheme can be improved quite a lot.
Don't hesitate to post a better scheme.

I think my typo confused you.

Urban Koistinen

unread,
Nov 10, 1995, 3:00:00 AM11/10/95
to
Alexander Boronka (etk1...@rpool10.rus.uni-stuttgart.de) wrote:
: Hi, this is Alex from Germany.

: Another way to store a position is not to store the position itself but
: the moves so far. That sound to need more bit than about 200. Wrong!
: This way could need more than 200 but often it won't. But you have a
: great advantage. First you don't need to consider En passent, rochade.
: Second you can replay the whole game.

I agree that it is more interesting to store games well than to
store positions in few bits.

: Following version to store each move is from a friend of mine:

[Long description of how to store moves deleted]

It should be easy enough to get 5 bits/move with a simple
encoding of moves and gzip for ordinary games databases.
(Storing several games together.)

With 40 moves/game that means 200 bits/game.

S.Read

unread,
Nov 10, 1995, 3:00:00 AM11/10/95
to
UK: Urban Koistinen (e...@algonet.se) 10 Nov 1995 19:41 +0100
UK> It should be easy enough to get 5 bits/move with a simple
UK> encoding of moves and gzip for ordinary games databases.
UK> (Storing several games together.)
UK> With 40 moves/game that means 200 bits/game.

Sorry, no. You probably have forgotten that there are TWO players
in a game of chess.

40 moves per game presumably means 40 moves for EACH player which
is 80 x 5 bits = 400 bits per game

ha ha ha ha ha!!!!

Simon Read "lurk before you leeeeeeeeeeeap!"


S.Read

unread,
Nov 10, 1995, 3:00:00 AM11/10/95
to
UK: Urban Koistinen - e...@algonet.se

UK> It should be easy enough to get 5 bits/move with a simple
UK> encoding of moves and gzip for ordinary games databases.
UK> (Storing several games together.)
UK> With 40 moves/game that means 200 bits/game.

Sorry, no. You probably have forgotten that there are TWO players
in a game of chess.

40 moves per game means 40 moves for EACH player which

S.Read

unread,
Nov 10, 1995, 3:00:00 AM11/10/95
to
If you want to compress games, you simply name the moves made from the
starting position, but you need a clever way of indicating which moves
were made.

Use the technique of ordering the moves by their tactical worth - if you
are using a computer to store bits you can certainly use the computer to
calculate moves. The computer uses a known method to order the moves
say, "Alpha-beta to 6 ply, pure material evaluation only" and produces a
score for each move. This orders the moves. Quite a lot of moves will
have the same score. You then use the secondary ordering of position on
the board. Anyway, it is most likely that moves will be from the earlier
part of the list, ie not making terrible tactical mistakes. Information
theory tells us that we can use a method of less bits to refer to those
few more likely moves which score highest (or least low) tactically.

So we may get away with 3 bits per move _on_average_ .

Simon Read


Robert Hyatt

unread,
Nov 10, 1995, 3:00:00 AM11/10/95
to
In article <47tqtl$8...@sophocles.algonet.se>,
Urban Koistinen <e...@sophocles.algonet.se> wrote:
-->Vincent Diepeveen (vdie...@cs.ruu.nl) wrote:
-->: In <47nckn$m...@aristotle.algonet.se> e...@aristotle.algonet.se (Urban Koistinen) writes:
-->
-->: >Dr R.E. Blundell (r...@uxa.liv.ac.uk) wrote:
-->: >: In article <46qvhf$2...@krant.cs.ruu.nl> vdie...@cs.ruu.nl (Vincent Diepeveen) writes:
-->: >: > The number of possible chesspositions is less then 2^164, as
-->: >: > it is possible to store easily a chessposition in 164 bits.
-->: >: > Just build a huffman tree out of the pieces, and include
-->: >: > neutral as an element (coded with 1 bit).
-->
-->: >: > I'm currently looking how much bits you need to encode a

-->: >: > position using arithmetic coding.
-->
-->: >With 12 promoted pawns:
-->: >1 - empty square *36 = 36
-->: >010 or 011 - pawn *0 = 0
-->: >00xxxx pieces *28 = 168
-->
-->: >total=204
-->
-->: If you promote then i can prove with simple induction
-->: that for every pawn that is promoting a piece is captured.
-->: This also means that there are more neutral squares, which
-->: require only 1 bit at most to encode.
-->
-->Maybe you can but:
-->The captured piece might be the same for up to 3 promotions.
-->Consider the case where all pawns have moved two steps forward,
-->then the moves: axb5 cxd4, exf5 gxh4 are made.
-->Now all 12 remaining pawns can be promoted without a single
-->capture.
-->
-->: Besides: having more then 2 queens on the board is nonsens.
-->
-->Not when you are counting the number of legally reachable
-->positions.
-->--
-->Urban Koistinen - e...@algonet.se


while we are "discussing" this (I regret mentioning 163 by now.. :) ) don't forget
that much is "moot" since the pieces on the board are but part of a position. Don't
forget move history. A position that has occurred twice is not the same as when the
position occurs for the third time. This causes the infamous draw problems in the
trans/ref table.

Bob

Urban Koistinen

unread,
Nov 11, 1995, 3:00:00 AM11/11/95
to
Robert Hyatt (hy...@willis.cis.uab.edu) wrote:
[quoted text deleted]

: while we are "discussing" this (I regret mentioning 163 by now.. :) )


: don't forget
: that much is "moot" since the pieces on the board are but part of a
: position. Don't
: forget move history. A position that has occurred twice is not the
: same as when the
: position occurs for the third time. This causes the infamous draw
: problems in the
: trans/ref table.

Correct, but disregarding history is all right if you want to
find the table size needed to get perfect play by lookup.
(That is the way Shannon used the number he gave.)
For chess computers there ought to be ways to reduce the problem.
One way is to only use the transposition table for the last few
plies.
Another would be to store the four last positions of the branch
that is being examined. That way the simplest kind of repetition
could be found.

What ways have you tried besides keeping searches with drawn
values out of the transposition table?

Ed Seedhouse

unread,
Nov 11, 1995, 3:00:00 AM11/11/95
to
vdie...@cs.ruu.nl (Vincent Diepeveen) wrote:

>>: > I'm currently looking how much bits you need to encode a

>>: > position using arithmetic coding.

It occurs to me that the starting position of any game is a known.
Therefore the starting position can be given the defined value 0, and
encoded in 1 bit.

The approach that suggests itself to me is that we therefore only need
to store a value for the squares that are not the same as in the
starting positon.

Each square that is changed by being vacant when it was occupied in
the starting position can be stored in 6 bits (6 for it's position on
the 64 square [2^6] grid. That leaves only the squares that are
changed from the original position to be coded for and each of these
should be encodable in 9 bits - 6 for the location on the 64 (2^6)
square grid and 3 for the type and color of the piece. I guess we
need a couple more bits to code the possibility of castling and en
passent capture. An extra bit for each piece that has this
possibility should do it I imagine.

Since in most positions a good many squares will be unchanged from the
starting positions, and many of those which have changed will be
empty, it seems to me that this could be a productive approach to
compactly encoding chess positions.

I am no mathematician, however. Does anyone who is truly computer or
math literate care to point out any glaring flaws in this approach?
I'd certainly be interested in finding out, anyway. :-)


Ed Seedhouse
President, Victoria Chess Club.
CFC Rating: 2047


Urban Koistinen

unread,
Nov 12, 1995, 3:00:00 AM11/12/95
to
S.Read (me944p) wrote:
: UK: Urban Koistinen - e...@algonet.se

: UK> It should be easy enough to get 5 bits/move with a simple
: UK> encoding of moves and gzip for ordinary games databases.
: UK> (Storing several games together.)
: UK> With 40 moves/game that means 200 bits/game.

: Sorry, no. You probably have forgotten that there are TWO players
: in a game of chess.

: 40 moves per game means 40 moves for EACH player which
: is 80 x 5 bits = 400 bits per game

Eh, you are right!

: ha ha ha ha ha!!!!

: Simon Read "lurk before you leeeeeeeeeeeap!"

--
Urban Koistinen - e...@algonet.se

Ed Seedhouse

unread,
Nov 12, 1995, 3:00:00 AM11/12/95
to
e...@sophocles.algonet.se (Urban Koistinen) wrote:

>Ed Seedhouse (e...@islandnet.com) wrote:
>: vdie...@cs.ruu.nl (Vincent Diepeveen) wrote:

>: >>: > I'm currently looking how much bits you need to encode a
>: >>: > position using arithmetic coding.

>: It occurs to me that the starting position of any game is a known.
>: Therefore the starting position can be given the defined value 0, and
>: encoded in 1 bit.

>: The approach that suggests itself to me is that we therefore only need
>: to store a value for the squares that are not the same as in the
>: starting positon.

>: I am no mathematician, however. Does anyone who is truly computer or


>: math literate care to point out any glaring flaws in this approach?
>: I'd certainly be interested in finding out, anyway. :-)

>I hope you don't get too upset by this then:

Not upset at all, but I don't see this as a "problem" for my proposal.

>forsythe "8/8/rnbqkbnr/pppppppp/PPPPPPPP/RNBQKBNR/8/8"
>Would require 64*(6+6+3)=64*15=960 bits using your scheme.
>(Ignoring castling, ep and side to move)
>There are other flaws, but I guess the one is enough.
>Beware that I often get wrong results by a factor of 2 :-)

I think this is a rather "unusual" position, don't you? The whole
point of "my" scheme (I have no idea whether it is in any way original
to me) is that it is most efficient for the type of positions that are
most likely to arise in a chess game. Naturally an extreme position
will be ineficiently encoded, but how often will such positions arise?
I think the idea is to save memory space for keeping hash tables in
computers playing actual games.

Urban Koistinen

unread,
Nov 12, 1995, 3:00:00 AM11/12/95
to
Ed Seedhouse (e...@islandnet.com) wrote:
: vdie...@cs.ruu.nl (Vincent Diepeveen) wrote:

: >>: > I'm currently looking how much bits you need to encode a
: >>: > position using arithmetic coding.

: It occurs to me that the starting position of any game is a known.
: Therefore the starting position can be given the defined value 0, and
: encoded in 1 bit.

: The approach that suggests itself to me is that we therefore only need
: to store a value for the squares that are not the same as in the
: starting positon.

: Each square that is changed by being vacant when it was occupied in
: the starting position can be stored in 6 bits (6 for it's position on


: the 64 square [2^6] grid. That leaves only the squares that are
: changed from the original position to be coded for and each of these
: should be encodable in 9 bits - 6 for the location on the 64 (2^6)
: square grid and 3 for the type and color of the piece. I guess we
: need a couple more bits to code the possibility of castling and en
: passent capture. An extra bit for each piece that has this
: possibility should do it I imagine.

: Since in most positions a good many squares will be unchanged from the
: starting positions, and many of those which have changed will be
: empty, it seems to me that this could be a productive approach to
: compactly encoding chess positions.

: I am no mathematician, however. Does anyone who is truly computer or


: math literate care to point out any glaring flaws in this approach?
: I'd certainly be interested in finding out, anyway. :-)

I hope you don't get too upset by this then:

forsythe "8/8/rnbqkbnr/pppppppp/PPPPPPPP/RNBQKBNR/8/8"


Would require 64*(6+6+3)=64*15=960 bits using your scheme.
(Ignoring castling, ep and side to move)
There are other flaws, but I guess the one is enough.
Beware that I often get wrong results by a factor of 2 :-)

Vincent Diepeveen

unread,
Nov 13, 1995, 3:00:00 AM11/13/95
to

>Hi, this is Alex from Germany.

This is the Netherlands coming in...

>Another way to store a position is not to store the position itself but
>the moves so far. That sound to need more bit than about 200. Wrong!
>This way could need more than 200 but often it won't. But you have a
>great advantage. First you don't need to consider En passent, rochade.
>Second you can replay the whole game.

>Following version to store each move is from a friend of mine:

>1. Start checking each field, begining with a1. If this field is free go
> to the next field. After a8 go to b1 ...
>2. If a field isn't free try out all possible moves from this field.
> In general a pawn has less possible moves than a qween.
> Each possible move gets a number, beginning with 0.
> If all possible moves from a field are numberd, go to the next field.
> If this field is free, goto next field ...
> IF it is white's turn of course only try out the possible move for white.
>3. After you have numbers all possible moves of a color, you know how
> much Bit you need to store this move.

This is the beginning of a great combined idea; ^8
Assuming you have an empty board, and pieces in your hand:
now count field by field until you arrive on the right square.

First we start with Kings, as we need them anyway.

White king: where to put it: on field 4 for example.

First the binary version, which can be compressed using arithmetic
compression:

64 possibilities: needing 6 bits. 6 total
black king, 63 possibilities, at most 6 bits. 12 total
white queen 63 possibitlitis, 62 squares, 1 possibilitie that it is
not there!

This takes at maximum 6x32 bits <= 192 bits. That is simply too much.

Now a retry: First we make a bitboard of the piece set, 1 for being
there 0 for being captured; 32 bits.
Then still another 6x32 bits are needed to encode WHERE they are.

>Example: At the beginning of a game:
>root on a1 can't move.
>night on b1 can move to a3. This is move number 0 = #0
>night on b1 can also move to c3. -> move number 1 = #1
>bishops, qween, king can't move.
>night on g1 can move to f3 -> #2
>night can also move to h1 -> #3
>a-Pawn can move to a3 (#4) and a4 (#5)
>b-Pawn ...
>h-Pawn can move to h3 (#18) and h4 (#19)

>Result: White can do 20 possible moves (in that special case)
>20 moves -> 5 bit
>That means you need 5 bit to store the first move

>Example from above: if white moves e4, this means move #13 = 01101

>Then continue with black, white, black, ...

>Even in a complex possition you normally can store a move in 7 bits.

If you must do this for 32 pieces then 7x32 is over 200 bits.
The problem here is again WHERE are the pieces. In this storing way
you again must specify for 32 pieces where they are standing.

With the huffman algorithm the overhead of this question WHERE is
stored in 64 bits, but a minimum overhead of 32 bits. However the
problem then is WHAT piece is on that location.

I read about a whole othere way of storing a position. It was posted
few years ago in this newsgroup. It was gambling that you could describe
a position in 100 bits. The guy who thought this out had next idea:

Suppose you are making multiple choice questions, with only 2
questions: YES, or NO, Then it is possible to ask after the position:
- is it an openingsposition?
<if no then>
- middlegame?
<if yes then>
- Is the position french?
<if yes then>
- Is black having a bad c8 bishop
< if yes then>
- is blacks king on the right?

Yes on a question is 1
No on a question is 0

With a lot of structural questions a computer could make a position.
Of course, it is hard to gamble how much questions (= bits) there
are needed to describe a position. However, 100 questions are a lot!
May be even 70 is sufficient!

Vincent.

Alexander Boronka

unread,
Nov 14, 1995, 3:00:00 AM11/14/95
to

On 13 Nov 1995, Vincent Diepeveen wrote:

> If you must do this for 32 pieces then 7x32 is over 200 bits.
> The problem here is again WHERE are the pieces. In this storing way
> you again must specify for 32 pieces where they are standing.

I only must do this for one piece per move. And I need not storing the
positions of all the not moving pieces because all the moves played yet
define their field exactly.

Dr R.E. Blundell

unread,
Nov 14, 1995, 3:00:00 AM11/14/95
to
This is getting interesting. According to Dennis Breuker
(bre...@cs.rulimburg.nl)

: Nievergelt states:


: "136 bits suffice to determine *any* legal chess position (of which
: there are about 10^40"
: However, he does not say how he calculated this number. (BTW 2^136 is
: about 8*10^40)

I wonder what he means by position? Maybe he just means the positions of the
pieces, and doesn't bother with castling etc. I hope he hasn't just taken log
base 2 of 10^40!?

This is quite a bit less than the best so far posted to this group which is
163, if promotions, repeated positions and the possibility of a draw due to
moves made without pawn moves are ignored. However, I think I can see how we
can do better. vdie...@cs.ruu.nl (Vincent Diepeveen) suggets the following
rather neat idea:

>Encode side to move in 1 bit
>Encode the positions of the kings in 2*12 bits.

>There are 404 impossible positions that I use as follows:

[Details deleted - they encode en passant and castling possibilities which if
they are present free up quite a few bits because the positions of certain
pieces become known.]

>Use these codes to encode the remaining squares:
>1 empty *36 = 36 or *32 = 32
>01x Pp *0 = 0 or *16 = 48
>00xxx QRBNqrbn *26 = 130 or *14 = 70
>
>total: 1+12+36+130=179 or 1+12+32+48+70=163
>first number with promotions, second without

Supposing we take the first bit of each code (which indicates whether a piece
is present) and arrange these first. So far, this changes nothing. This gives a
table of 64 bits indicating which squares are occupied (ok - you only use 62
because the positions of the kings are known but lets ignore that for the
moment). This carries quite a bit of information, in particular the number of
pieces, which can be used to further reduce the space required to specify which
pieces are where. For instance, if less that 32 pieces are present then we know
we will save at least 2 bits (the cost of a pawn). However, if all 32 are
present then the position and identity of the last piece is not required, again
saving at least 2 bits. Admittedly 2 bits isn't much of a saving, but the
method can be extended.

In general, I don't think a lower bound can be estabilished because we are
dealing with a *single* position in which the various possibilities are
strongly correlated. This is not a Markov chain, and cannot be represented by
one while we insist that we look at a single position therefore I don't think
it is possible to define a Shanon entropy. Then again, never say never.

Rob

--
Dr R E Blundell (Email r...@liv.ac.uk),

Department of Electrical Engineering and Electronics,

University of Liverpool, Brownlow Hill, P.O. Box 147,

Liverpool L69 3BX

Urban Koistinen

unread,
Nov 18, 1995, 3:00:00 AM11/18/95
to

Isn't it better then to store positions as follows:
1 bit to determine if it should be stored in the max 179 bit format or
as follows:
Encode the moves made from the starting position.

This would typically need about 5 bits/half move made.
Worst case is 180 bits.

(Disclaimer: the 179-bit encoding scheme does not consider history beyond
ep and castling possibilities.)

Urban Koistinen - e...@algonet.se

Alexander Boronka

unread,
Nov 20, 1995, 3:00:00 AM11/20/95
to

On 18 Nov 1995, Urban Koistinen wrote:

>
> This would typically need about 5 bits/half move made.
> Worst case is 180 bits.
>
> (Disclaimer: the 179-bit encoding scheme does not consider history beyond
> ep and castling possibilities.)
>
> Urban Koistinen - e...@algonet.se
>

Everyone can do what he/she wants. Every algorithm has its advantages and
disadvantages.

Ciao, Alexander Boronka

Urban Koistinen

unread,
Nov 20, 1995, 3:00:00 AM11/20/95
to
Alexander Boronka (etk1...@rpool4.rus.uni-stuttgart.de) wrote:

: On 18 Nov 1995, Urban Koistinen wrote:

: >
: > This would typically need about 5 bits/half move made.
: > Worst case is 180 bits.
: >
: > (Disclaimer: the 179-bit encoding scheme does not consider history beyond
: > ep and castling possibilities.)

: Everyone can do what he/she wants. Every algorithm has its advantages and
: disadvantages.

That is what makes comparing them interesting.
I have concentrated on worst case encoding size,
if you want to focus on some other feuture,
I will be happy to discuss that.

Scott Edward Taylor

unread,
Nov 22, 1995, 3:00:00 AM11/22/95
to
Ed Seedhouse (e...@islandnet.com) wrote:
: e...@sophocles.algonet.se (Urban Koistinen) wrote:

: >Ed Seedhouse (e...@islandnet.com) wrote:
: >: vdie...@cs.ruu.nl (Vincent Diepeveen) wrote:

: >: >>: > I'm currently looking how much bits you need to encode a
: >: >>: > position using arithmetic coding.

: >: It occurs to me that the starting position of any game is a known.
: >: Therefore the starting position can be given the defined value 0, and
: >: encoded in 1 bit.

: >: The approach that suggests itself to me is that we therefore only need
: >: to store a value for the squares that are not the same as in the
: >: starting positon.

: >: I am no mathematician, however. Does anyone who is truly computer or


: >: math literate care to point out any glaring flaws in this approach?
: >: I'd certainly be interested in finding out, anyway. :-)

: >I hope you don't get too upset by this then:

: Not upset at all, but I don't see this as a "problem" for my proposal.

: >forsythe "8/8/rnbqkbnr/pppppppp/PPPPPPPP/RNBQKBNR/8/8"


: >Would require 64*(6+6+3)=64*15=960 bits using your scheme.
: >(Ignoring castling, ep and side to move)
: >There are other flaws, but I guess the one is enough.
: >Beware that I often get wrong results by a factor of 2 :-)

: I think this is a rather "unusual" position, don't you? The whole


: point of "my" scheme (I have no idea whether it is in any way original
: to me) is that it is most efficient for the type of positions that are
: most likely to arise in a chess game. Naturally an extreme position
: will be ineficiently encoded, but how often will such positions arise?
: I think the idea is to save memory space for keeping hash tables in
: computers playing actual games.

Of course, IMHO, the most important consideration for chess programs,
especially those that rely on "brute force" algorithms, is how quickly
the internal storage representation can be decoded into something
useful to the program; in these days of 8 and 16 MB computers (for
a "standard" PC--a machine intended for use as a chess computer would
likely have more), a few bits here and there don't matter nearly as
much as they did back in the days of the Apple II. Of course, if you're
building an embedded system (i.e., a portable dedicated chess palmtop),
you might need to take the memory into account (depending on how much
you wanted to spend on the components). The usual approach of having
a directly accessed linear integer array is probably as good as any
(here's a case in which, although object-oriented analysis is good,
object-oriented programming might not be, at least for the board,
unless you just implement the aforementioned array as a class member).


--
-------------------------------------------------------------------------
| Scott Taylor (sta...@netcom.com) | What kind of an idea are you? |
| CI$: 70662,1777 AOL: STaylor758 ----------------------------------|
| WWW URL: ftp://ftp.netcom.com/pub/st/staylor/homepage.html |
-------------------------------------------------------------------------

Urban Koistinen

unread,
Nov 24, 1995, 3:00:00 AM11/24/95
to
Scott Edward Taylor (sta...@netcom.com) wrote:
: Ed Seedhouse (e...@islandnet.com) wrote:
: : e...@sophocles.algonet.se (Urban Koistinen) wrote:

As 64*4 bits = 256 bits is enough to store the board position, it
seem to be more space-efficient than Ed Seedhouses' scheme too,
at least for positions well into the game.

Rain

unread,
Dec 14, 1995, 3:00:00 AM12/14/95
to
e...@aristotle.algonet.se (Urban Koistinen) wrote:

[snips]

>As 64*4 bits = 256 bits is enough to store the board position, it
>seem to be more space-efficient than Ed Seedhouses' scheme too,
>at least for positions well into the game.
>--
>Urban Koistinen - e...@algonet.se

64*4?

It strikes me that this is derived from encoding pieces on a square
matrix - i.e. board[x] = piece value, which is 4 bits.

Let's see. Pawn, Rook, Knight, Bishop, Queen, King. That's six
pieces. We also need an "empty" value, for seven total pieces, or 3
bits. Add one in for colour, and voila! 4 bits.

So far so good. However it doesn't include overhead for whether
castling is allowed, and if so, for which player(s) and which side(s).
So, a little more than 256 bits would be needed this way. We'll
ignore this, however.

How about this, then? There are only 32 pieces, maximum. Encoding
their positions as part of the piece description would require 6 bits.
Add in the 8 bits for the piece itself, and you have 10 bits/piece *
32 pieces = 320 bits. A net loss of 64 bits.

However, if one were to keep track only of those pieces actually on
the board, the capture of every piece would reduce the storage by 10
bits. Thus, after 7 captures, this becomes more efficient, at 250
bits.

One might even consider a hybrid system, in which the former method
was used during the early game and the latter in the midgame, thus
allowing the maximum of storable positions in a given amount of
memory.

Here's another idea. Don't store a board position at all; store a
move list. We know what the board looks like at the beginning;
there's no need to store it. Now you can simply store the 12 bits
needed to encode a "from, to" move for each position.

One objection might be that after a long string of moves, the net
storage would be enormous. Not necessarily. Try this:

First, encode a board position in whatever format makes you happy.
For each move, simply build the movelist and store that. When the
movelist grows too large, save the current state as a new board
position and start the movelist over again as though this position
were the initial board.

By doing this, some 21 moves can be encoded in 512 bits (256 for the
initial position, 256 for the movelist), instead of the 5376 bits (at
256 bits / position) they would otherwise need. It might be a bit
slower to parse, but unless I've goofed up somewhere (eminently
possible :]) we've just improve storage by an order of magnitude -
surely worth a little extra processing.

Comments?


Mike Leahy (BOOKUP)

unread,
Dec 15, 1995, 3:00:00 AM12/15/95
to
rain...@Direct.CA (Rain) wrote:
>e...@aristotle.algonet.se (Urban Koistinen) wrote:
>
> [snips]
>
>>As 64*4 bits = 256 bits is enough to store the board position, it
>>seem to be more space-efficient than Ed Seedhouses' scheme too,
>>at least for positions well into the game.
>>--
>>Urban Koistinen - e...@algonet.se
>
> 64*4?
>
> It strikes me that this is derived from encoding pieces on a square
>matrix - i.e. board[x] = piece value, which is 4 bits.
>
> Let's see. Pawn, Rook, Knight, Bishop, Queen, King. That's six
>pieces. We also need an "empty" value, for seven total pieces, or 3
>bits. Add one in for colour, and voila! 4 bits.


This is exactly the scheme used in BOOKUP (DOS,
Windows and Mac).


> So far so good. However it doesn't include overhead for whether
>castling is allowed, and if so, for which player(s) and which side(s).
>So, a little more than 256 bits would be needed this way. We'll
>ignore this, however.

You're right. One more byte does the trick.

> How about this, then? There are only 32 pieces, maximum. Encoding
>their positions as part of the piece description would require 6 bits.
>Add in the 8 bits for the piece itself, and you have 10 bits/piece *
>32 pieces = 320 bits. A net loss of 64 bits.
>
> However, if one were to keep track only of those pieces actually on
>the board, the capture of every piece would reduce the storage by 10
>bits. Thus, after 7 captures, this becomes more efficient, at 250
>bits.
>
> One might even consider a hybrid system, in which the former method
>was used during the early game and the latter in the midgame, thus
>allowing the maximum of storable positions in a given amount of
>memory.

Speed used to be an issue with this approachc due to the overhead
of packing and unpacking. Most database systems don't have
efficient methods of using variable-length keys so the
application of further compression ranges from impractical
to pointless. This is from a database programmer's
perspective, of course. A programmer of a playing program
might well want to do this.

> Here's another idea. Don't store a board position at all; store a
>move list. We know what the board looks like at the beginning;
>there's no need to store it. Now you can simply store the 12 bits
>needed to encode a "from, to" move for each position.
>
> One objection might be that after a long string of moves, the net
>storage would be enormous. Not necessarily. Try this:
>
> First, encode a board position in whatever format makes you happy.
>For each move, simply build the movelist and store that. When the
>movelist grows too large, save the current state as a new board
>position and start the movelist over again as though this position
>were the initial board.
>
> By doing this, some 21 moves can be encoded in 512 bits (256 for the
>initial position, 256 for the movelist), instead of the 5376 bits (at
>256 bits / position) they would otherwise need. It might be a bit
>slower to parse, but unless I've goofed up somewhere (eminently
>possible :]) we've just improve storage by an order of magnitude -
>surely worth a little extra processing.
>
> Comments?

Yes, the string idea is similar to the way ChessBase
and Chess Assistant store games. It just doesn't do
much good for instant location of transpositions.

Mike Leahy
"The Database Man!"


Urban Koistinen

unread,
Dec 15, 1995, 3:00:00 AM12/15/95
to
Don Fong (df...@cse.ucsc.edu) wrote:
<snip>
: PMFJI, i seem to have missed the previous postings in this thread.
: but you don't need 12 bits. consider "from". true, there are 64
: squares = 6 bits, but at most 16 of those squares (in any one position)
: are a valid "from" square. so no more than 4 bits are needed for the
: "from" square. now consider "to". no existing chess piece has more
: than 28 moves in any given position. so you could generate the moves
: in a canonical order, then encode any "to" square as its place in this
: canonical order. so you need at most 5 bits for "to". altogether you
: need at most 4+5=9 bits for "from,to" . (hmm, only one piece --- the Q
: --- can ever have more than 16 moves.)

That is similar to a method sje recommended:

c = getchar();
mover = c&15;
from = piece[color][mover];
type = board[from];
move = move_table[from][type][(c>>4)&15];
if (move==0) move = move_table[from][type][getchar()];
make_move(move);

Where make_move() updates piece, board and color

The above is as I remember it, sje might care to correct me.

I think using and updating board[] slow parsing down.

: taking this a step further, you could generate all moves for all
: pieces in a canonical order, then encode the move (both "from" and "to")
: as its place in canonical order. i don't know whether this would
: save anything. (Q: does any position have more than 255 legal moves?)

This is what the last version of PGC I have seen does.
I don't think there are any positions that can be reached legally
from the starting position that have more than 255 legal moves, but
the margin is surprisingly small.

Urban Koistinen

unread,
Dec 15, 1995, 3:00:00 AM12/15/95
to
Rain (rain...@Direct.CA) wrote:
: e...@aristotle.algonet.se (Urban Koistinen) wrote:

: [snips]

: >As 64*4 bits = 256 bits is enough to store the board position, it
: >seem to be more space-efficient than Ed Seedhouses' scheme too,
: >at least for positions well into the game.

: >--
: >Urban Koistinen - e...@algonet.se

: 64*4?

: It strikes me that this is derived from encoding pieces on a square
: matrix - i.e. board[x] = piece value, which is 4 bits.

Yes, that is the idea.

: Let's see. Pawn, Rook, Knight, Bishop, Queen, King. That's six


: pieces. We also need an "empty" value, for seven total pieces, or 3
: bits. Add one in for colour, and voila! 4 bits.

12 ordinary pieces, 1 empty, 1 for rook that might participate
in castling, 1 for the king of the side to move, 1 for the pawn
that just made a double move.
16 values and easy to decode too.

: So far so good. However it doesn't include overhead for whether


: castling is allowed, and if so, for which player(s) and which side(s).
: So, a little more than 256 bits would be needed this way. We'll
: ignore this, however.

No need to ignore it.

: How about this, then? There are only 32 pieces, maximum. Encoding


: their positions as part of the piece description would require 6 bits.
: Add in the 8 bits for the piece itself, and you have 10 bits/piece *

------------>4
: 32 pieces = 320 bits. A net loss of 64 bits.

Why not:
Position of 32 pieces: 32*6
Encode captured pieces by placing them on their own king square.
Encode castling possibility by placing rook on other king square.
Encode promotion/ep in 3 bits/pawn. P,Q,R,B,N,ep
Encode side to move in 1 bit.
This will use 32*6+16*3+1 = 241

: However, if one were to keep track only of those pieces actually on


: the board, the capture of every piece would reduce the storage by 10
: bits. Thus, after 7 captures, this becomes more efficient, at 250
: bits.

Don't forget the 5 bits you'd need to store the number of pieces.

: One might even consider a hybrid system, in which the former method


: was used during the early game and the latter in the midgame, thus
: allowing the maximum of storable positions in a given amount of
: memory.

Don't forget the 1 bit you need to decide what system to use.

: Here's another idea. Don't store a board position at all; store a


: move list. We know what the board looks like at the beginning;
: there's no need to store it. Now you can simply store the 12 bits
: needed to encode a "from, to" move for each position.

: One objection might be that after a long string of moves, the net
: storage would be enormous. Not necessarily. Try this:

If you are encoding games, you should compare your scheme with
other game encoding schemes.

: First, encode a board position in whatever format makes you happy.


: For each move, simply build the movelist and store that. When the
: movelist grows too large, save the current state as a new board
: position and start the movelist over again as though this position
: were the initial board.

: By doing this, some 21 moves can be encoded in 512 bits (256 for the
: initial position, 256 for the movelist), instead of the 5376 bits (at
: 256 bits / position) they would otherwise need. It might be a bit
: slower to parse, but unless I've goofed up somewhere (eminently
: possible :]) we've just improve storage by an order of magnitude -
: surely worth a little extra processing.

What is your intended use?
Is it meant to reduce the required storage for BookUp?

: Comments?

I have spent too much time on figuring out how to encode
chess moves so they can be parsed quickly.
My scheme would store the position of each piece.
The type would be stored in the move.
That way, parsing can be very quick and there are only
about 4300 different moves, about 12+ bits/move but
in ordinary games 95% of the moves would be among
the 240 most common.

GivenRandy

unread,
Dec 15, 1995, 3:00:00 AM12/15/95
to
256? Come on, guys. Think about the number of PIECES (32), then look
into Huffman coding, then arithmetic coding. Look at past postings to
this Newsgroup (you will find many) about this subject.

Randy Given <Given...@aol.com>

Don Fong

unread,
Dec 15, 1995, 3:00:00 AM12/15/95
to
In article <4apn0v$d...@grid.direct.ca>, Rain <rain...@Direct.CA> wrote:
>e...@aristotle.algonet.se (Urban Koistinen) wrote:
>
> [snips]
>
>>As 64*4 bits = 256 bits is enough to store the board position, it
>>seem to be more space-efficient than Ed Seedhouses' scheme too,
>>at least for positions well into the game.
>>--
>>Urban Koistinen - e...@algonet.se
>
> 64*4?
>
> It strikes me that this is derived from encoding pieces on a square
>matrix - i.e. board[x] = piece value, which is 4 bits.
>
> Let's see. Pawn, Rook, Knight, Bishop, Queen, King. That's six
>pieces. We also need an "empty" value, for seven total pieces, or 3
>bits. Add one in for colour, and voila! 4 bits.
>
> So far so good. However it doesn't include overhead for whether
>castling is allowed, and if so, for which player(s) and which side(s).
>So, a little more than 256 bits would be needed this way. We'll
>ignore this, however.
>
> How about this, then? There are only 32 pieces, maximum. Encoding
>their positions as part of the piece description would require 6 bits.
>Add in the 8 bits for the piece itself, and you have 10 bits/piece *
>32 pieces = 320 bits. A net loss of 64 bits.
>
> However, if one were to keep track only of those pieces actually on
>the board, the capture of every piece would reduce the storage by 10
>bits. Thus, after 7 captures, this becomes more efficient, at 250
>bits.
>
> One might even consider a hybrid system, in which the former method
>was used during the early game and the latter in the midgame, thus
>allowing the maximum of storable positions in a given amount of
>memory.
>
> Here's another idea. Don't store a board position at all; store a
>move list. We know what the board looks like at the beginning;
>there's no need to store it. Now you can simply store the 12 bits
>needed to encode a "from, to" move for each position.

PMFJI, i seem to have missed the previous postings in this thread.


but you don't need 12 bits. consider "from". true, there are 64
squares = 6 bits, but at most 16 of those squares (in any one position)
are a valid "from" square. so no more than 4 bits are needed for the
"from" square. now consider "to". no existing chess piece has more
than 28 moves in any given position. so you could generate the moves
in a canonical order, then encode any "to" square as its place in this
canonical order. so you need at most 5 bits for "to". altogether you
need at most 4+5=9 bits for "from,to" . (hmm, only one piece --- the Q
--- can ever have more than 16 moves.)

taking this a step further, you could generate all moves for all
pieces in a canonical order, then encode the move (both "from" and "to")
as its place in canonical order. i don't know whether this would
save anything. (Q: does any position have more than 255 legal moves?)

> One objection might be that after a long string of moves, the net


>storage would be enormous. Not necessarily. Try this:
>

> First, encode a board position in whatever format makes you happy.
>For each move, simply build the movelist and store that. When the
>movelist grows too large, save the current state as a new board
>position and start the movelist over again as though this position
>were the initial board.
>
> By doing this, some 21 moves can be encoded in 512 bits (256 for the
>initial position, 256 for the movelist), instead of the 5376 bits (at
>256 bits / position) they would otherwise need. It might be a bit
>slower to parse, but unless I've goofed up somewhere (eminently
>possible :]) we've just improve storage by an order of magnitude -
>surely worth a little extra processing.
>

> Comments?


Q Q
Q
Q
Q
Q
Q RK
Q B
Q B
--
--- don fong ``i still want the peace dividend''
--

Urban Koistinen

unread,
Dec 16, 1995, 3:00:00 AM12/16/95
to
Mike Leahy (BOOKUP) (boo...@coil.com) wrote:
: rain...@Direct.CA (Rain) wrote:
<snip>
: > Here's another idea. Don't store a board position at all; store a

: >move list. We know what the board looks like at the beginning;
: >there's no need to store it. Now you can simply store the 12 bits
: >needed to encode a "from, to" move for each position.
: >
: > One objection might be that after a long string of moves, the net

: >storage would be enormous. Not necessarily. Try this:
: >
: > First, encode a board position in whatever format makes you happy.
: >For each move, simply build the movelist and store that. When the
: >movelist grows too large, save the current state as a new board
: >position and start the movelist over again as though this position
: >were the initial board.
: >
: > By doing this, some 21 moves can be encoded in 512 bits (256 for the
: >initial position, 256 for the movelist), instead of the 5376 bits (at
: >256 bits / position) they would otherwise need. It might be a bit
: >slower to parse, but unless I've goofed up somewhere (eminently
: >possible :]) we've just improve storage by an order of magnitude -
: >surely worth a little extra processing.
: >
: > Comments?

: Yes, the string idea is similar to the way ChessBase


: and Chess Assistant store games. It just doesn't do
: much good for instant location of transpositions.

That is what you would use transposition tables for.
Have a pointer to the game and move number.
32 bits is a lot less than 256 bits.

I realize you need to store other information in
the transposition table too, but you should be able
to at least halve the database size.

Gianluigi Masciulli

unread,
Dec 16, 1995, 3:00:00 AM12/16/95
to
df...@cse.ucsc.edu (Don Fong) wrote:
......

> taking this a step further, you could generate all moves for all
>pieces in a canonical order, then encode the move (both "from" and "to")
>as its place in canonical order. i don't know whether this would
>save anything. (Q: does any position have more than 255 legal moves?)

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

The world record is 218.(by petrovic (1928) and Dickins(1968))
However In normal play I never see more than 100 legal moves.
So you can safely assume legal moves < 255.


Gianluigi Masciulli
gmasc...@texnet.it


Joost de Heer

unread,
Dec 17, 1995, 3:00:00 AM12/17/95
to
In <4av318$q...@server-b.cs.interbusiness.it> gmasc...@texnet.it (Gianluigi Masciulli) writes:

>df...@cse.ucsc.edu (Don Fong) wrote:
>......

>> taking this a step further, you could generate all moves for all
>>pieces in a canonical order, then encode the move (both "from" and "to")
>>as its place in canonical order. i don't know whether this would
>>save anything. (Q: does any position have more than 255 legal moves?)
> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

>The world record is 218.(by petrovic (1928) and Dickins(1968))

The world record is actually 288 moves. But the position is sort of illegal :-)
In legal positions the record is indeed 218 moves. Positions are as follows:

Legal Illegal
WR -- -- -- -- -- -- WR WB WQ WQ WQ WQ WQ WQ WB
-- -- -- -- WQ -- -- -- WQ -- -- -- -- -- -- WQ
-- WQ -- -- -- -- WQ -- WQ -- -- -- -- -- -- WQ
-- -- -- -- -- -- -- -- WQ -- -- -- -- -- -- WQ
-- -- WQ -- -- -- -- WQ WQ -- -- -- -- -- -- WQ
WQ -- -- -- -- WQ -- -- WQ -- -- -- -- -- -- WQ
BP BP -- WQ -- -- -- -- WQ -- -- -- -- -- -- WQ
BK WB WN WN -- WK WB -- WB WQ WQ WQ WQ WQ WQ WB

Joost
--
Think about all the good in your life - It's only temporary
Think about all the positive sides in life - They never last forever
So drink to forget and drown all your sorrow SENTENCED
Bury your dreams and choose Catharsis NEPENTHE

0 new messages