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 3:41 pm Reply to topic Reply with quote
Edmund wrote:
diep wrote:
Note that to store FENs, you can store chesspositions pretty compact.
A simple method is to use say for example:

64 bits : bitmap that basically says whether a piece is on a square or not

now we have for 32 pieces at most which can have 12 values, so with arithmetic encoding that's :

log 12 / log 2 = 3.58 bits
So for 32 pieces that's 114.7 = 115 bits.
So we have 147 bits for the position.
now let's store also its properties.
side to move is 1 bit , we are at 148 now.
we know we have at most 5 pawns we can capture en passant.
that's 2.32 bits.

That bad luck so far is that added up with the pieces that's 117.04 bits
so doesn't fit in 117 bits yet.

So we are at 151 now. Then for each side we must store 2 bits for castling rights of the rook at most.

So we end at 155 bits for a position.

Now Bob will probably post something about repetitions and stuff like that, but he isn't hashing that into crafty either and he is hashing en passant and castling rights, so 155 bits it is Smile


Some comments:
you are missing the 7 bits needed for the 50-move counter; this counter can be combined with the ep squares because it has to be 0 in case of ep possibilities.



No we aren't missing that at all - is crafty hashing it?

Quote:

You are missing out on some gains from restrictions due to chess rules. Pawns may occupy only 3/4 of the board, there is exactly one king per side, the kings may not be on neighboring squares and side to move may not give check.
There are some more, but the gains would probably not justify the efforts.


Yes it is possible to get a far more compact way of storing the position.

See some postings i did do on the pawns calculations some months/years ago in this forum.

You really can get the search space calculation down to 10^40 or less quite easily.

Using that scheme then to store will be far more efficient, yet that's not really his question if i understood well.

In fact if i look at what diep sees within its search space, knowing it'll search all nonsense as well, i notice that actually it never manages to promote more than 1 pawn simultaneously causing never to be more than 2 queens of 1 side on the board.

Sure it is possble and sure i bet some player one day tried to get 3 queens just to tease his opponent (something i'm never doing in chess - but i know there is some sadists out there).

Yet even the wildest search of Diep isn't showing this for game play.

So how many positions are there practical possible to achieve for within game play?

I don't know. Maybe 10^30? Maybe 10^35. You tell me.

There is more practical constraints for example. For example all 8 pieces aren't on the other side of the board usually.

So some sophisticated huffman+arithmetic encoding that you tune to the average case, if you go measure in the entire search during entire game, i bet you'll not gonna get over a 116 bits or so.

Vincent
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