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 

New 6-piece tablebases
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions Flat
View previous topic :: View next topic  
Author Message
Ronald de Man



Joined: 28 Feb 2012
Posts: 3362

PostPost subject: Re: New 6-piece tablebases    Posted: Sat Apr 13, 2013 3:54 pm Reply to topic Reply with quote

stevemulligan wrote:
Nice work Ronald! How can they be so much smaller than the compressed Gaviota tables?

There are several reasons:

- Distance to zeroing move (DTZ) instead of distance to mate (DTM).

- DTZ and WDL (win/draw/loss) information is stored in separate tables without duplicating the WDL information in the DTZ table. This allows me to store for DTZ only the "smaller half" of white-to-move / black-to-move information, because DTZ is only probed at the root.

- Tricks in encoding WDL information. Positions with a winning capture are stored as "don't care". Something similar (but more complicated) for positions with a drawing capture. Of course illegal positions (side to move can capture the king) are set to don't care as well. The compression algorithm sets these values to what compresses best. The cost is a round of captures in the probing code, which I consider acceptable because these probe into much smaller tables which may be assumed to be cached in RAM.

- Tricks in encoding DTZ information. As already mentioned WDL information is removed, so draws are "don't care" and only the distance to win or loss is stored. Positions with a winning capture or pawn move are set to don't care, as this can be tested easily when probing.

- My compression algorithm seems to do quite well. It's not a general purpose compressor, so it is hard to compare to e.g. LZMA used by Gaviota, but LZMA and other compressors that compress "online" (i.e. read input and produce output in a single pass) suffer from small block sizes. My compressor constructs a (small) dictionary on the basis of the whole table which results in a sort of "random access" compression/decompression with very small blocks (at most 64 bytes for WDL, at most 1024 bytes for DTZ). The only efficiency lost by making blocks smaller is a few bits lost at the end of each block (because the next symbol does not fit anymore).

- The order of piece types in the indexing function can have a large impact on compression ratio. My indexing function therefore allows for many permutations of piece types. Before compressing a table a search is done for a good permutation (by testing on a subset of the data).

The size of my tables is slightly increased by the inclusion of information on the 50-move rule (without losing the ability to play out wins affected by the 50-move rule), but my compression deals with this efficiently and it adds something that I think was not available before.

Size is one thing, probing overhead another. Throwing away the "bigger half" of DTZ of course increases probing overhead of DTZ, but this is only done at the root so I find this completely acceptable. The trick with winning/drawing captures has a cost when probing WDL, but it should not lead to more I/O and it reduces the size quite a bit, which means that more compressed data can be cached and I/O is reduced. Overall I think it is a win. I don't cache decompressed data but instead make use of the small block size and the fact that it is faster to extract a single value from a block than to decompress the whole block.
Back to top
View user's profile Send private message
Display posts from previous:   
Subject Author Date/Time
New 6-piece tablebases Ronald de Man Mon Apr 01, 2013 10:03 pm
      Re: New 6-piece tablebases Oscar Toledo G. Fri Apr 05, 2013 3:46 am
      Re: New 6-piece tablebases Lucas Braesch Fri Apr 05, 2013 5:14 am
            Re: New 6-piece tablebases Ronald de Man Fri Apr 05, 2013 7:09 pm
                  Re: New 6-piece tablebases Lucas Braesch Sat Apr 06, 2013 12:56 am
                        Re: New 6-piece tablebases Ronald de Man Sat Apr 06, 2013 2:57 am
                        Re: New 6-piece tablebases Don Dailey Sun Jun 16, 2013 1:04 pm
                              Re: New 6-piece tablebases Ronald de Man Sun Jun 16, 2013 1:43 pm
                                    Re: New 6-piece tablebases Don Dailey Sun Jun 16, 2013 2:23 pm
                                          Re: New 6-piece tablebases Ronald de Man Sun Jun 16, 2013 3:06 pm
                                                Re: New 6-piece tablebases Don Dailey Sun Jun 16, 2013 3:26 pm
                                                      Re: New 6-piece tablebases Ronald de Man Sun Jun 16, 2013 4:55 pm
                                                            Re: New 6-piece tablebases Don Dailey Sun Jun 16, 2013 6:19 pm
                                                                  Re: New 6-piece tablebases Ronald de Man Sun Jun 16, 2013 7:54 pm
                                                                        Re: New 6-piece tablebases Don Dailey Mon Jun 17, 2013 12:21 am
                                                                              Re: New 6-piece tablebases Joshua Shriver Wed Mar 02, 2016 3:16 pm
      Re: New 6-piece tablebases Martin Sedlak Fri Apr 05, 2013 8:01 am
            Re: New 6-piece tablebases Ronald de Man Fri Apr 05, 2013 8:00 pm
      Re: New 6-piece tablebases Richard Vida Fri Apr 05, 2013 11:57 am
            Re: New 6-piece tablebases Ronald de Man Fri Apr 05, 2013 9:03 pm
                  Re: New 6-piece tablebases Ahmed Mansoor Mon Aug 12, 2013 9:47 am
                        Re: New 6-piece tablebases Ahmed Mansoor Fri Aug 16, 2013 8:13 am
      Re: New 6-piece tablebases Álvaro Begué Fri Apr 05, 2013 2:11 pm
            Re: New 6-piece tablebases H.G.Muller Fri Apr 05, 2013 2:17 pm
      Re: New 6-piece tablebases Robert Houdart Sat Apr 06, 2013 3:25 pm
            Re: New 6-piece tablebases Daniel Shawul Sat Apr 06, 2013 4:02 pm
                  Re: New 6-piece tablebases Robert Houdart Sat Apr 06, 2013 5:54 pm
                        Re: New 6-piece tablebases Daniel Shawul Sat Apr 06, 2013 6:31 pm
                              Re: New 6-piece tablebases Robert Houdart Sat Apr 06, 2013 6:46 pm
                                    Re: New 6-piece tablebases Daniel Shawul Sat Apr 06, 2013 6:54 pm
                                          Re: New 6-piece tablebases Robert Houdart Sat Apr 06, 2013 11:04 pm
            Re: New 6-piece tablebases Ronald de Man Sat Apr 06, 2013 4:37 pm
                  Re: New 6-piece tablebases Robert Houdart Sat Apr 06, 2013 5:55 pm
      Re: New 6-piece tablebases Ronald de Man Sun Apr 07, 2013 11:19 pm
      Re: New 6-piece tablebases Joshua Shriver Mon Apr 08, 2013 2:51 pm
            Re: New 6-piece tablebases Ronald de Man Mon Apr 08, 2013 7:17 pm
                  Re: New 6-piece tablebases Joshua Shriver Mon Apr 08, 2013 7:22 pm
                        Re: New 6-piece tablebases Ronald de Man Mon Apr 08, 2013 8:19 pm
                        Re: New 6-piece tablebases Sven Schüle Mon Apr 08, 2013 8:34 pm
                              Re: New 6-piece tablebases Joshua Shriver Mon Apr 08, 2013 8:42 pm
                                    Re: New 6-piece tablebases Tano-Urayoan Russi Roman Thu Apr 11, 2013 5:27 pm
                                          Re: New 6-piece tablebases Joshua Shriver Fri Apr 12, 2013 12:28 am
                              Re: New 6-piece tablebases Ronald de Man Mon Apr 08, 2013 8:58 pm
                  Re: New 6-piece tablebases Joshua Shriver Mon Apr 08, 2013 7:23 pm
                        Re: New 6-piece tablebases Ronald de Man Mon Apr 08, 2013 8:27 pm
      Re: New 6-piece tablebases Joshua Shriver Tue Apr 09, 2013 4:45 am
            Re: New 6-piece tablebases Ronald de Man Tue Apr 09, 2013 7:40 am
            Re: New 6-piece tablebases Ronald de Man Tue Apr 09, 2013 8:04 am
            Re: New 6-piece tablebases Ronald de Man Wed Apr 10, 2013 12:29 am
      Re: New 6-piece tablebases Alexander Zacharias Tue Apr 09, 2013 6:10 pm
            Re: New 6-piece tablebases Matthew R. Brades Tue Apr 09, 2013 8:07 pm
                  Re: New 6-piece tablebases Alexander Zacharias Tue Apr 09, 2013 10:41 pm
                        Re: New 6-piece tablebases Ronald de Man Wed Apr 10, 2013 12:35 am
                              Re: New 6-piece tablebases Evert Glebbeek Wed Apr 10, 2013 7:20 am
                                    Re: New 6-piece tablebases Ronald de Man Wed Apr 10, 2013 11:53 am
                                          Re: New 6-piece tablebases Evert Glebbeek Wed Apr 10, 2013 1:22 pm
                                                Re: New 6-piece tablebases Ronald de Man Wed Apr 10, 2013 6:51 pm
                              Re: New 6-piece tablebases Gerd Isenberg Wed Apr 10, 2013 4:13 pm
                                    Re: New 6-piece tablebases Ronald de Man Wed Apr 10, 2013 6:55 pm
                                          Re: New 6-piece tablebases Gerd Isenberg Wed Apr 10, 2013 7:55 pm
            Re: New 6-piece tablebases Ronald de Man Tue Apr 09, 2013 10:44 pm
      Re: New 6-piece tablebases Steve Mulligan Sat Apr 13, 2013 2:23 pm
            Re: New 6-piece tablebases Ronald de Man Sat Apr 13, 2013 3:54 pm
                  Re: New 6-piece tablebases Steve Mulligan Sat Apr 13, 2013 5:18 pm
                        Re: New 6-piece tablebases Miguel A. Ballicora Sat Apr 13, 2013 5:38 pm
                        Re: New 6-piece tablebases Ronald de Man Sat Apr 13, 2013 6:28 pm
                              Re: New 6-piece tablebases H.G.Muller Sat Apr 13, 2013 8:40 pm
                                    Re: New 6-piece tablebases Uri Blass Tue Apr 16, 2013 12:30 am
                                          Re: New 6-piece tablebases Uri Blass Tue Apr 16, 2013 12:44 am
                                          Re: New 6-piece tablebases H.G.Muller Tue Apr 16, 2013 6:33 am
                              Re: New 6-piece tablebases Steve Mulligan Sat Apr 13, 2013 9:12 pm
                  Re: New 6-piece tablebases Miguel A. Ballicora Sat Apr 13, 2013 5:26 pm
                  Re: New 6-piece tablebases Ben Nye Sun Apr 14, 2013 7:43 pm
                        Re: New 6-piece tablebases Ronald de Man Sun Apr 14, 2013 8:45 pm
                              Re: New 6-piece tablebases Ben Nye Tue Apr 16, 2013 4:32 pm
                                    Re: New 6-piece tablebases Ronald de Man Tue Apr 16, 2013 6:48 pm
                                          Re: New 6-piece tablebases Ben Nye Wed Apr 17, 2013 11:26 pm
      Re: New 6-piece tablebases Ronald de Man Mon Apr 15, 2013 11:14 pm
            Re: New 6-piece tablebases Joshua Shriver Tue Apr 16, 2013 4:23 pm
                  Re: New 6-piece tablebases Ronald de Man Tue Apr 16, 2013 6:47 pm
                        Re: New 6-piece tablebases Rein Halbersma Wed Jan 04, 2017 11:43 am
                              Re: New 6-piece tablebases Ronald de Man Wed Jan 04, 2017 9:23 pm
                                    Re: New 6-piece tablebases Bojun Guo Thu Jan 05, 2017 1:24 am
                                          Re: New 6-piece tablebases Joshua Shriver Wed Jan 11, 2017 7:18 am
                                                Re: New 6-piece tablebases daniel jose Wed Jan 11, 2017 2:12 pm
            Re: New 6-piece tablebases Ronald de Man Thu Apr 25, 2013 5:56 pm
      Re: New 6-piece tablebases Jean-Francois Romang Sat Apr 27, 2013 4:21 pm
            Re: New 6-piece tablebases Jean-Francois Romang Sun Apr 28, 2013 10:08 am
                  Re: New 6-piece tablebases Vael Jean-Paul Sun Apr 28, 2013 12:26 pm
                        Re: New 6-piece tablebases Jean-Francois Romang Sun Apr 28, 2013 12:50 pm
                              Re: New 6-piece tablebases Vael Jean-Paul Sun Apr 28, 2013 12:58 pm
                                    Re: New 6-piece tablebases Vael Jean-Paul Sun Apr 28, 2013 1:15 pm
                                          Re: New 6-piece tablebases Michel Van den Bergh Sun Apr 28, 2013 2:48 pm
                        Re: New 6-piece tablebases Jean-Francois Romang Sun Apr 28, 2013 12:54 pm
                  Re: New 6-piece tablebases Adam Hair Sun Apr 28, 2013 3:46 pm
                        Re: New 6-piece tablebases Adam Hair Sun Apr 28, 2013 4:00 pm
      Re: New 6-piece tablebases Marek Soszynski Sun Jun 16, 2013 6:22 am
      Re: New 6-piece tablebases Kirill Kryukov Tue Jun 18, 2013 8:25 am
            Re: New 6-piece tablebases Ronald de Man Tue Jun 18, 2013 9:18 am
                  Re: New 6-piece tablebases Vael Jean-Paul Sun Aug 04, 2013 6:58 pm
                        Re: New 6-piece tablebases Vael Jean-Paul Mon Aug 05, 2013 5:45 pm
                              Re: New 6-piece tablebases Vael Jean-Paul Mon Aug 12, 2013 9:41 am
                  Re: New 6-piece tablebases Kirill Kryukov Wed Aug 21, 2013 1:06 am
                        Re: New 6-piece tablebases Ronald de Man Thu Aug 22, 2013 1:34 pm
                              Re: New 6-piece tablebases Kirill Kryukov Thu Aug 22, 2013 1:47 pm
                              Re: New 6-piece tablebases Ahmed Mansoor Fri Aug 23, 2013 7:22 am
                                    Re: New 6-piece tablebases Ronald de Man Fri Aug 23, 2013 2:29 pm
                                          Re: New 6-piece tablebases Ahmed Mansoor Fri Aug 23, 2013 5:47 pm
                        Re: New 6-piece tablebases Ronald de Man Mon Sep 02, 2013 10:24 pm
                              Re: New 6-piece tablebases Ahmed Mansoor Tue Sep 03, 2013 5:30 pm
                                    Re: New 6-piece tablebases Joshua Shriver Wed Sep 04, 2013 3:28 am
                              Re: New 6-piece tablebases Kirill Kryukov Tue Sep 03, 2013 11:17 pm
                                    Re: New 6-piece tablebases Rob Nicholas Thu Sep 12, 2013 2:32 am
                                          Re: New 6-piece tablebases Kirill Kryukov Thu Sep 12, 2013 3:31 am
                                                Re: New 6-piece tablebases Rob Nicholas Thu Sep 12, 2013 11:20 am
                                                      Re: New 6-piece tablebases Kirill Kryukov Thu Sep 12, 2013 11:50 am
                                                            Re: New 6-piece tablebases Ronald de Man Thu Sep 12, 2013 6:08 pm
                                                                  Re: New 6-piece tablebases Kirill Kryukov Thu Sep 12, 2013 11:39 pm
                                                                        Re: New 6-piece tablebases Rob Nicholas Fri Sep 13, 2013 1:24 am
                                                                              Re: New 6-piece tablebases Ronald de Man Sat Sep 14, 2013 2:27 am
                                                                                    Re: New 6-piece tablebases Kirill Kryukov Sat Sep 14, 2013 2:52 am
                                                                                    Re: New 6-piece tablebases Ahmed Mansoor Sat Sep 14, 2013 7:26 am
                                                                                    Re: New 6-piece tablebases Paul Henri Tue Sep 17, 2013 8:38 pm
                                                                                          Re: New 6-piece tablebases Paul Henri Tue Sep 17, 2013 9:18 pm
                                                                                          Re: New 6-piece tablebases Ronald de Man Wed Sep 18, 2013 1:08 am
                                                                                          Re: New 6-piece tablebases Paul Henri Wed Sep 18, 2013 6:34 pm
                                                                                          Re: New 6-piece tablebases Ronald de Man Wed Sep 18, 2013 7:24 pm
                                                                                          Re: New 6-piece tablebases Paul Henri Wed Sep 18, 2013 8:24 pm
                                                                                          Re: New 6-piece tablebases Ronald de Man Thu Sep 19, 2013 12:50 am
                                                                                          Re: New 6-piece tablebases Ahmed Mansoor Sun Sep 22, 2013 7:36 am
                                                                                          Re: New 6-piece tablebases Roberto Possioto Sun Sep 22, 2013 10:40 am
                                                                                          Re: New 6-piece tablebases Ahmed Mansoor Sun Sep 22, 2013 12:37 pm
                                                                                          Re: New 6-piece tablebases Paul Henri Mon Sep 23, 2013 2:44 pm
                                                                                          Re: New 6-piece tablebases Paul Henri Mon Sep 23, 2013 4:39 pm
                                                                                          Re: New 6-piece tablebases Marek Soszynski Mon Sep 23, 2013 4:50 pm
                                                                                          Re: New 6-piece tablebases Vincent Lejeune Mon Sep 23, 2013 5:50 pm
                                                                                          Re: New 6-piece tablebases Edmund Moshammer Mon Sep 23, 2013 6:11 pm
                                                                                          Re: New 6-piece tablebases jose mº velasco Mon Sep 23, 2013 7:01 pm
                                                                                          Re: New 6-piece tablebases Vincent Lejeune Mon Sep 23, 2013 7:02 pm
                                                                                          Re: New 6-piece tablebases Ronald de Man Mon Sep 23, 2013 7:44 pm
                                                                                          Re: New 6-piece tablebases Ronald de Man Mon Sep 23, 2013 7:51 pm
                                                                                          Re: New 6-piece tablebases Rob Nicholas Mon Sep 23, 2013 8:48 pm
                                                                                          Re: New 6-piece tablebases Ronald de Man Mon Sep 23, 2013 10:43 pm
                                                                                          Re: New 6-piece tablebases Rob Nicholas Mon Sep 23, 2013 11:59 pm
                                                                                          Re: New 6-piece tablebases Ronald de Man Tue Sep 24, 2013 12:10 am
                                                                                          Re: New 6-piece tablebases Shivkumar Shivaji Tue Sep 24, 2013 3:17 am
                                                                                          Re: New 6-piece tablebases Roberto Possioto Tue Sep 24, 2013 9:26 am
                                                                                          Re: New 6-piece tablebases Paul Henri Mon Sep 23, 2013 7:29 pm
      Re: New 6-piece tablebases robert jones Sat Aug 24, 2013 1:18 am
            Re: New 6-piece tablebases Ronald de Man Sat Aug 24, 2013 11:06 am
                  Re: New 6-piece tablebases H.G.Muller Sat Aug 24, 2013 12:53 pm
                        Re: New 6-piece tablebases Ronald de Man Sun Aug 25, 2013 1:02 am
                              Re: New 6-piece tablebases Kirill Kryukov Sun Aug 25, 2013 9:32 am
                  Re: New 6-piece tablebases Roberto Possioto Sat Aug 31, 2013 2:09 pm
                        Re: New 6-piece tablebases Ronald de Man Sat Aug 31, 2013 2:15 pm
                              Re: New 6-piece tablebases Roberto Possioto Sat Aug 31, 2013 3:19 pm
                                    Re: New 6-piece tablebases Ronald de Man Sat Aug 31, 2013 3:32 pm
      Re: New 6-piece tablebases Kirill Kryukov Mon Aug 26, 2013 10:19 am
            Re: New 6-piece tablebases Ronald de Man Wed Aug 28, 2013 11:18 pm
                  Re: New 6-piece tablebases Kirill Kryukov Thu Aug 29, 2013 11:09 am
                  Re: New 6-piece tablebases Kirill Kryukov Wed Sep 11, 2013 6:55 am
                        Re: New 6-piece tablebases Joshua Shriver Wed Sep 11, 2013 7:19 am
                              Re: New 6-piece tablebases Kirill Kryukov Wed Sep 11, 2013 7:50 am
                                    Re: New 6-piece tablebases Joshua Shriver Wed Sep 11, 2013 7:56 am
                                          Re: New 6-piece tablebases Kirill Kryukov Wed Sep 11, 2013 8:01 am
                                          Re: New 6-piece tablebases Vael Jean-Paul Wed Sep 11, 2013 8:05 am
                                                Re: New 6-piece tablebases Joshua Shriver Wed Sep 11, 2013 8:12 am
                                                      Re: New 6-piece tablebases Roberto Possioto Wed Sep 11, 2013 8:55 am
                                          Re: New 6-piece tablebases Bajusz Tamás Wed Sep 11, 2013 1:50 pm
      Re: New 6-piece tablebases Joshua Shriver Tue Sep 03, 2013 5:12 pm
            Re: New 6-piece tablebases Roberto Possioto Tue Sep 03, 2013 5:45 pm
            Re: New 6-piece tablebases Norman Schmidt Tue Sep 03, 2013 5:45 pm
                  Re: New 6-piece tablebases Ahmed Mansoor Tue Sep 03, 2013 6:31 pm
                        Re: New 6-piece tablebases Norman Schmidt Tue Sep 03, 2013 7:54 pm
                              Re: New 6-piece tablebases Kirill Kryukov Wed Sep 04, 2013 6:23 am
                                    Re: New 6-piece tablebases Ahmed Mansoor Wed Sep 04, 2013 10:56 am
                  Re: New 6-piece tablebases Kirill Kryukov Tue Sep 03, 2013 11:20 pm
            Re: New 6-piece tablebases Paul Henri Tue Sep 10, 2013 6:05 pm
                  Re: New 6-piece tablebases Vincent Lejeune Wed Sep 11, 2013 10:12 am
                        Re: New 6-piece tablebases Kirill Kryukov Wed Sep 11, 2013 10:59 am
                              Re: New 6-piece tablebases Vincent Lejeune Wed Sep 11, 2013 11:21 am
                                    Re: New 6-piece tablebases Joshua Shriver Wed Sep 11, 2013 11:24 am
      Re: New 6-piece tablebases Joshua Shriver Wed Sep 04, 2013 3:35 am
            Re: New 6-piece tablebases Ahmed Mansoor Wed Sep 04, 2013 11:47 am
                  Re: New 6-piece tablebases Ronald de Man Wed Sep 04, 2013 12:10 pm
                        Re: New 6-piece tablebases Ahmed Mansoor Wed Sep 04, 2013 12:33 pm
      Re: New 6-piece tablebases Edmund Moshammer Wed Sep 25, 2013 6:42 pm
            Re: New 6-piece tablebases Ronald de Man Wed Sep 25, 2013 8:48 pm
      Re: New 6-piece tablebases: missing statistics Guy Haworth Wed Mar 02, 2016 3:13 pm
            Re: New 6-piece tablebases: missing statistics jose mº velasco Wed Mar 02, 2016 3:51 pm
                  Re: New 6-piece tablebases: missing statistics Guy Haworth Wed Mar 02, 2016 9:07 pm
            Re: New 6-piece tablebases: missing statistics Guy Haworth Mon Mar 07, 2016 11:24 am
      Re: New 6-piece tablebases Ed Trice Sat Jan 07, 2017 4:01 am
            Re: New 6-piece tablebases Michael B Wed Jan 11, 2017 2:47 am
                  Re: New 6-piece tablebases Joshua Shriver Wed Jan 11, 2017 7:15 am
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