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
Robert Hyatt



Joined: 27 Feb 2006
Posts: 15814
Location: Birmingham, AL
PostPost subject: Re: Database storage methods    Posted: Thu Mar 08, 2012 10:54 pm Reply to topic Reply with quote
JuLieN wrote:
Rebel wrote:
One compression idea is to store a move (usually 2 bytes, or 2x6=12 bits) as an 8-bit number representing the number in the pseudo-legal move generation list. Takes a lot of extra processor time but saves disk space.


Right. In ICCA's January 1983 Newsletter, Kathe Spracklen (co-author of Sargon) writes a "Tutorial: Representation of an Opening Book Tree".

She discusses various methods and the one she finally chose was described to her by Ken Thompson (author of Belle).

As Ed said, each move in the tree is coded in a single byte: 6 bits are the index in the moves generation list, and the remaining two bits are coded "(" and ")" and help describe the tree.

To quote Kathe:

Quote:
One bit, designated '(', indicates that there is another move choice available in this position. The other bit, designated ')', indicates that we have reached the end of that line.


(Actually, when you think of it, you only need 7 bits: six for displacement and one for the '(/)': 0='(', 1=')'.)

For instance, the following tree:
Code:

e4 -- e5 -- Nf3 -- Nc6 -- Bb5 -- a6
 |       |        |       |        |
 |       |       f4     Nf6     Bc4
 |      c5 -- Nf3 -- d6 -- d4
 |       |               |
 |      e6            Nc6
d4 -- Nf6 -- c4 -- g6 -- Nc3
 |       |                |
 |       |               e6 -- Nc3 -- Bb4
 |       |                        |
 |       |                      Nf3
 |      d5 -- c4 -- c6 -- Nf3
 |       |       |      |
etc.   f5     Nf3   e6 -- Nc3
 |                      |
 |                     dxc4


Would translate as:

Code:

(e4  (e5  (Nf3  (Nc6  (Bb5  a6)
                              Bc4)
                       Nf6)
               f4)
       (c5  Nf3  (d6  d4)
                     Nc6)
        e6)
(d4  (Nf6  c4  (g6  Nc3)
                     e6  (Nc3  Bb4)
                           Nf3)
       (d5  (c4  (c6  Nf3)
                    (e6  Nc3)
                     dxc4)
              Nf3)
        f5)
etc.


Or, when stored:

Code:

(e4(e5(Nf3(Nc6(Bb5 a6)Bc4)Nf6)f4)(c5 Nf3)(d6 d4)Nc6)e6)(d4(Nf6 c4(g6 Nc3)e6(Nc3 Bb4)Nf3)(d5(c4(c6 Nf3)(e6 Nc3)dxc4)Nf3)f5) etc.


Hope that helps. Smile


Couple of points.

First, you need the full 8 bits for the index. There are positions with > 128 moves, which means 7 bits is not enough. The record is something like 230 legal moves.

Second, for chess engines, I don't think anyone stores a book in the way you describe, nor have they for many years. Problem is that transpositions are difficult to detect. Most just store a huge file of zobrist hash signatures. If you make a move in any position, and can find the zobrist signature in the book file, you know that was a book move.
Back to top
View user's profile Send private message
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