estimated number of chesspositions 
Vincent Diepeveen 
10/27/95 12:00 AM 
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  +======================================+ 
estimated number of chesspositions 
Joe Stella 
10/28/95 12:00 AM 
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. 
estimated number of chesspositions 
Abraham S. Mantell 
10/28/95 12:00 AM 
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

estimated number of chesspositions 
Jeffrey O. Curtis 
10/28/95 12:00 AM 
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

estimated number of chesspositions 
Robert Hyatt 
10/30/95 12:00 AM 
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) 9342213 115A Campbell Hall, UAB Station (205) 9345473 FAX Birmingham, AL 352941170

estimated number of chesspositions 
Robert Hyatt 
10/30/95 12:00 AM 
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 chessplaying 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 fourletter word and the extra bit specifies >whose move it is. The question then becomes how many 4letter words >are there in the chess vocabulary since this determines the minimum >number of bits necessary to specify all 4letter 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 4letter words which can be constructed >from the 13letter 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, righttoleft/toptobottom; toptobottom/righttoleft; 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 onmove = 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 nonzero (not empty). You simply exclusiveor these numbers which produces a 64bit random hashkey that is really nicely distributed over the 2^64 possible keys.
Bob  Robert Hyatt Computer and Information Sciences hy...@cis.uab.edu University of Alabama at Birmingham (205) 9342213 115A Campbell Hall, UAB Station (205) 9345473 FAX Birmingham, AL 352941170

estimated number of chesspositions 
Mike Leahy (BOOKUP) 
10/30/95 12:00 AM 
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!"

estimated number of chesspositions 
Vincent Diepeveen 
10/31/95 12:00 AM 
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)  ++  email : vdie...@cs.ruu.nl   Vincent Diepeveen  +======================================+

estimated number of chesspositions 
Steven J. Edwards 
10/31/95 12:00 AM 
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 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)

estimated number of chesspositions 
Jeffrey O. Curtis 
10/31/95 12:00 AM 
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 >chesshashtables 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 > > ++ >  email : vdie...@cs.ruu.nl  >  Vincent Diepeveen  > +======================================+

Encoding chess positions was: Number of... 
Urban Koistinen 
10/31/95 12:00 AM 
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*(411)=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*(1x)) 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 
estimated number of chesspositions 
Urban Koistinen 
11/1/95 12:00 AM 
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. 1314. : 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.  Urban Koistinen  e...@algonet.se

estimated number of chesspositions 
Vincent Diepeveen 
11/1/95 12:00 AM 
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.  ++  email : vdie...@cs.ruu.nl   Vincent Diepeveen  +======================================+

estimated number of chesspositions 
Tim Mann 
11/1/95 12:00 AM 
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 lefttoright, toptobottom, 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 50move rule or availability of a draw by repetition. The 50move 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 
estimated number of chesspositions 
Thomas R. Truscott 
11/3/95 12:00 AM 
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/c204.psTom Truscott 
estimated number of chesspositions 
Thomas R. Truscott 
11/3/95 12:00 AM 
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 ondisk 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 enpassant by swapping the enprise pawn with an impossible square (for example if a pawn moved e2e4 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 
estimated number of chesspositions 
Robert Hyatt 
11/7/95 12:00 AM 
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 6bit 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
 Robert Hyatt Computer and Information Sciences hy...@cis.uab.edu University of Alabama at Birmingham (205) 9342213 115A Campbell Hall, UAB Station (205) 9345473 FAX Birmingham, AL 352941170

estimated number of chesspositions 
Urban Koistinen 
11/9/95 12:00 AM 
Paul McMahon 3131 (ukcmcmp@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 epcapturing 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: 431+1226=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: 426+51=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+168 = 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  Urban Koistinen  e...@algonet.se

estimated number of chesspositions 
Vincent Diepeveen 
11/9/95 12:00 AM 
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
 ++  email : vdie...@cs.ruu.nl   Vincent Diepeveen  +======================================+ 
estimated number of chesspositions 
S.Read 
11/9/95 12:00 AM 
(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: ( >>>Cspeak ( >>Bspeak ( >Aspeak ( 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 dpawns promote ( 1 capture) someone does bxc then b and cpawns promote ( 1 capture) etc. Simon Read s.r...@cranfield.ac.uk "lurk before you leap!" 9 NOV 1995 15:00 GMT

estimated number of chesspositions 
Urban Koistinen 
11/9/95 12:00 AM 
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

estimated number of chesspositions 
Urban Koistinen 
11/9/95 12:00 AM 
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 epcapturing 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: 431+1226=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: 426+51=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+168 = 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  e...@algonet.se

estimated number of chesspositions 
Urban Koistinen 
11/10/95 12:00 AM 
Alexander Boronka ( etk1...@rpool10.rus.unistuttgart.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.  Urban Koistinen  e...@algonet.se

estimated number of chesspositions 
S.Read 
11/10/95 12:00 AM 
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!"

estimated number of chesspositions 
S.Read 
11/10/95 12:00 AM 
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 gameha ha ha ha ha!!!! Simon Read "lurk before you leeeeeeeeeeeap!"

estimated number of chesspositions 
S.Read 
11/10/95 12:00 AM 
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, "Alphabeta 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

estimated number of chesspositions 
Robert Hyatt 
11/10/95 12:00 AM 
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  Robert Hyatt Computer and Information Sciences hy...@cis.uab.edu University of Alabama at Birmingham (205) 9342213 115A Campbell Hall, UAB Station (205) 9345473 FAX Birmingham, AL 352941170

estimated number of chesspositions 
Urban Koistinen 
11/11/95 12:00 AM 
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?  Urban Koistinen  e...@algonet.se

Encoding board positions. 
Ed Seedhouse 
11/11/95 12:00 AM 
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

estimated number of chesspositions 
Urban Koistinen 
11/12/95 12:00 AM 
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 
Encoding board positions. 
Ed Seedhouse 
11/12/95 12:00 AM 
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. Ed Seedhouse President, Victoria Chess Club. CFC Rating: 2047

Encoding board positions. 
Urban Koistinen 
11/12/95 12:00 AM 
Ed Seedhouse ( e...@islandnet.com) wrote: : vdie...@cs.ruu.nl (Vincent Diepeveen) wrote: 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 :)
 Urban Koistinen  e...@algonet.se 
estimated number of chesspositions 
Vincent Diepeveen 
11/13/95 12:00 AM 
In <Pine.A32.3.91.951110091831.24399A100000@rpool10.rus.unistuttgart.de> Alexander Boronka <etk1...@rpool10.rus.unistuttgart.de> writes: >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 >aPawn can move to a3 (#4) and a4 (#5) >bPawn ... >hPawn 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.  ++  email : vdie...@cs.ruu.nl   Vincent Diepeveen  +======================================+

estimated number of chesspositions 
Alexander Boronka 
11/14/95 12:00 AM 
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. 
estimated number of chesspositions 
Dr R.E. Blundell 
11/14/95 12:00 AM 
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 
estimated number of chesspositions 
Urban Koistinen 
11/18/95 12:00 AM 
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 179bit encoding scheme does not consider history beyond ep and castling possibilities.) Urban Koistinen  e...@algonet.se 
estimated number of chesspositions 
Alexander Boronka 
11/20/95 12:00 AM 
On 18 Nov 1995, Urban Koistinen wrote: > > This would typically need about 5 bits/half move made. > Worst case is 180 bits. > > (Disclaimer: the 179bit 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 
estimated number of chesspositions 
Urban Koistinen 
11/20/95 12:00 AM 
Alexander Boronka ( etk1...@rpool4.rus.unistuttgart.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 179bit 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.  Urban Koistinen  e...@algonet.se

Encoding board positions. 
Scott Edward Taylor 
11/22/95 12:00 AM 
Ed Seedhouse ( e...@islandnet.com) wrote: : e...@sophocles.algonet.se (Urban Koistinen) wrote: 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" PCa 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 objectoriented analysis is good, objectoriented 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  

Encoding board positions. 
Urban Koistinen 
11/24/95 12:00 AM 

Encoding board positions. 
Rain 
12/14/95 12:00 AM 
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 spaceefficient 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?

Encoding board positions. 
Mike Leahy (BOOKUP) 
12/15/95 12:00 AM 
rainline@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 spaceefficient 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 variablelength 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!"

Encoding board positions. 
Urban Koistinen 
12/15/95 12:00 AM 
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  e...@algonet.se

Encoding board positions. 
Urban Koistinen 
12/15/95 12:00 AM 
Rain (rainline@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 spaceefficient 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.  Urban Koistinen  e...@algonet.se

Encoding board positions. 
GivenRandy 
12/15/95 12:00 AM 
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> 
Encoding board positions. 
Don Fong 
12/15/95 12:00 AM 
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'' 

Encoding board positions. 
Urban Koistinen 
12/16/95 12:00 AM 
Mike Leahy (BOOKUP) ( boo...@coil.com) wrote: : rainline@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.  Urban Koistinen  e...@algonet.se

Encoding board positions. 
Gianluigi Masciulli 
12/16/95 12:00 AM 
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

Encoding board positions. 
Joost de Heer 
12/17/95 12:00 AM 
In <4av318$q...@serverb.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 