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
Vincent Diepeveen



Joined: 09 Mar 2006
Posts: 1738
Location: The Netherlands
PostPost subject: Re: Database storage methods    Posted: Sun Mar 11, 2012 4:58 pm Reply to topic Reply with quote
Dave_N wrote:
diep wrote:
Dave_N wrote:
I am thinking about Storing a compressed move list as a Tree in a hash table ...

The hash entry obviously has the following

int64 hash
int addrNext; // if needing a mainline
int addrVariation;


then for each move the game is merged by putting all variations found in a linked list of hash entries, so for a game list stored in sparse format

Code:

1.e4 e5 2.Nf3 Nc6 3.Bc4  // game 1
                          3.Bb5  // game 2
                          3.Nc3  // game 3

the main line is written first, then the variable addrVariation for Bc4 holds the array index of the hash bucket for Bb5, and the Bb5 bucket stores the hash bucket index for Nc3 etc ...

I don't know what to do about terminal nodes or nodes with only 1 game passing through - perhaps the index of the game can be written and merged iff another game scores a hit ?

I also tried to create a DAWG (direct acyclic word graph) for the FEN's to try to create perfect hashing ... the fen can already be compressed to 5 bit chars, then I got a 15 mb to 10 mb compression for the Fen list to DAWG file sizes.

If anyone has tried this disk tree concept I'd be interested to hear about how to compress the tree and whether its worth storing sparse move lists, or whether to just use SQL and a compressed move list, with maybe a gui button to call CQL for position searches.


You soon will find out this eats lots of space. What i did do in the old Diep game format, dating back from 1994 or so, is always generate moves in the same manner,by keeping a sorted list of pieces (so the same pieces need to get sorted by the square they're on).

Then you can easily store each move in 1 byte, as each position P has at most 220 moves or so. I know of a position of 218 moves by head, but for sure not 220.

Now this goes all pretty quick actually.

If you want to put more system time into it then a simple runlength encoding trick can reduce the size of the movelist even further.


I am already indexing a legal move list and decoding back to pgn - my legal moves are always generated in the same way, KRNBQP (or some similar order depending on check too). I can radix sort the moves lists (similar to sorting by ECO, of course 1.a3 might turn up in the legal moves list first anyway), but I am thinking about ways of clustering the transpositions - I generate fen's during compression, so hashing is natural. Building "merge trees" in a file on disk seems less stable however (harder to debug and very time consuming) perhaps hash values could be first clustered then written to make the task easier.


There is no need to sort the movelist at all. Just generation needs to be deterministic of the movelist, that's all.
Back to top
View user's profile Send private message Send e-mail Visit poster's website MSN Messenger
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