ChessUSA.com TalkChess.com
Hosted by Your Move Chess & Games
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Database storage methods
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions Flat
View previous topic :: View next topic  
Author Message
Don Dailey



Joined: 29 Apr 2008
Posts: 4323
PostPost subject: Re: Database storage methods    Posted: Sun Mar 11, 2012 5:25 am Reply to topic Reply with quote
Edmund wrote:
Don wrote:
hgm wrote:
Well, escapes can be viewed as a byte-quantized form of Hufman coding. If compactness is not the only criterion, but you also want to have some efficiency left on decoding, using SEE etc. seems a bad idea.

Decoding can be much faster, with an acceptable loss of compactness, by reserving codes for all possible move steps of the given piece type. You can then decode the move by just looking at the piece list section for that piece type to get the from square, and use a lookup table to get the step-vector. For orthodox Chess you would need 8x3 codes for Pawns, 3x8 for K+N, 4x14 for B+R and 28 for Q, for a total of 132. You would still need 8x3 codes for under-promotions, some of which could be also used for double-pushes, as Pawns that can double-push can never promote. (Castlings could be encoded as off-board King moves, as the King has to be on the edge to castle.) That leaves 100 codes for super-numerary pieces, of which you could set apart 8 for an extra N and 28 for an extra Q,R or B. That still would leave 64 codes with variable decoding (where you first would have to figure out what material is on the board to know what the codes mean) for the never-occurring situations with 3 and 4 Queens, 7 Knights or whatever, and some escape codes for positions so ridiculous that the 1-byte system cannot handle them.


Has anyone ever given consideration to how a compact opening book might be built using bloom filters or Golomb-coded sets?

It seems like a natural fit, except for the pesky false positive hit rate - a problem that I think makes this unworkable. With Golmob-coded sets we could (in theory) get a book down to something around 8 bits per position and still have transpositions detected.


Some Bloomfilter calculations:
n = total number of positions
m = size of the bloomfilter in bits
k = number of bits ORed to the filter for each position

According to http://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.html

for the m/n ratio of 8 (= 8 bits per position) the optimal value for k is 6 and this leaves us with a false positive rate of 2.16%.

Assuming that in a single game 10 moves are played out of book and for each position on average 30 moves are considered, the chance of a false move being played equals:
1 - ( 1 - 0.0216 ) ^ (10 * 30) = 99.857%

For 2 byte per position I am getting 12.867% and for 4 byte it is 0.006%

I couldn't find any similar statistics for Golmob-encoding. Can you provide any figures for false positive rates for an m/n ratio of 8 ?


Golomb encoding basically gets you closer to the theoretical minimum number of bits required for a given probability of false positives, it's probably only 20% or 30% less space but nothing dramatic.

I did a similar calculation and it seem completely unworkable. The "set" of positions to identify is much larger than the number of moves in the book which is s big problem.

There are a couple of ways to significantly constrain this. One of them is to consider only positions that are connected to a previous book move, so once out of book we are done. Another idea is to use a deterministic chess program to generate candidate moves. For example a 5 ply search done by your chess program under the same conditions to produce a move deterministically. The bloom filter identifies those positions where the search does not produce the desired move. It's ok to get a false positive in this case, it would only mean the program rejects the computers choice once in a while when it shouldn't. Of course this has serious limitations as you must now deal with the case where the computer does not pick the book move and it doesn't handle more than 1 possible book move.

Nothing really works well for a proper book system with high compression based on bloom filters that I can think of.
_________________
"Your superior intellect is no match for our puny weapons." -Kang and Kodos
Back to top
View user's profile Send private message Send e-mail
Display posts from previous:   
Subject Author Date/Time
Database storage methods david nash Thu Mar 08, 2012 10:56 am
      Re: Database storage methods Ed Schroder Thu Mar 08, 2012 11:59 am
            Re: Database storage methods Julien MARCEL Thu Mar 08, 2012 12:33 pm
                  Re: Database storage methods david nash Thu Mar 08, 2012 12:43 pm
                  Re: Database storage methods Martin Sedlak Thu Mar 08, 2012 1:00 pm
                        Re: Database storage methods Julien MARCEL Thu Mar 08, 2012 1:13 pm
                              Re: Database storage methods david nash Thu Mar 08, 2012 1:32 pm
                              Re: Database storage methods Martin Sedlak Thu Mar 08, 2012 1:45 pm
                                    Re: Database storage methods Julien MARCEL Thu Mar 08, 2012 1:51 pm
                        Re: Database storage methods Ed Schroder Thu Mar 08, 2012 3:42 pm
                  Re: Database storage methods Ed Schroder Thu Mar 08, 2012 3:46 pm
                  Re: Database storage methods Robert Hyatt Thu Mar 08, 2012 10:54 pm
                        Re: Database storage methods Julien MARCEL Thu Mar 08, 2012 11:53 pm
                              Re: Database storage methods Robert Hyatt Fri Mar 09, 2012 12:18 am
                              Re: Database storage methods Edmund Moshammer Fri Mar 09, 2012 12:51 am
                                    Re: Database storage methods H.G.Muller Fri Mar 09, 2012 9:29 am
                                          Re: Database storage methods Don Dailey Sat Mar 10, 2012 10:25 pm
                                                Re: Database storage methods Edmund Moshammer Sun Mar 11, 2012 12:27 am
                                                      Re: Database storage methods Don Dailey Sun Mar 11, 2012 5:25 am
                                    Re: Database storage methods Don Dailey Sat Mar 10, 2012 10:44 pm
                                    Re: Database storage methods Ronald de Man Sat Mar 10, 2012 11:45 pm
            Re: Database storage methods david nash Thu Mar 08, 2012 12:40 pm
      Re: Database storage methods H.G.Muller Thu Mar 08, 2012 4:36 pm
            Re: Database storage methods david nash Thu Mar 08, 2012 5:03 pm
                  Re: Database storage methods H.G.Muller Thu Mar 08, 2012 5:28 pm
                        Re: Database storage methods david nash Thu Mar 08, 2012 8:48 pm
      Re: Database storage methods Harald Lüßen Thu Mar 08, 2012 8:45 pm
            Re: Database storage methods david nash Thu Mar 08, 2012 8:51 pm
      Re: Database storage methods Nguyen Pham Thu Mar 08, 2012 10:39 pm
      Re: Database storage methods Vincent Diepeveen Sun Mar 11, 2012 6:41 am
            Re: Database storage methods david nash Sun Mar 11, 2012 4:49 pm
                  Re: Database storage methods Vincent Diepeveen Sun Mar 11, 2012 4:58 pm
                        Re: Database storage methods david nash Sun Mar 11, 2012 5:51 pm
      Re: Database storage methods Vincent Diepeveen Sun Mar 11, 2012 7:03 am
            Re: Database storage methods Vincent Diepeveen Sun Mar 11, 2012 7:21 am
            Re: Database storage methods Edmund Moshammer Sun Mar 11, 2012 9:21 am
                  Re: Database storage methods Vincent Diepeveen Sun Mar 11, 2012 3:41 pm
                        Re: Database storage methods david nash Sun Mar 11, 2012 5:08 pm
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum




Powered by phpBB © 2001, 2005 phpBB Group
Enhanced with Moby Threads