Difference between revisions of "Syzygy Bases"

From Chessprogramming wiki
Jump to: navigation, search
Line 4: Line 4:
  
 
'''Syzygy Bases''', <ref>[http://www.talkchess.com/forum/viewtopic.php?t=47681&start=45 Re: New 6-piece tablebases] by [[Ronald de Man]], [[CCC]], April 10, 2013</ref><br/>
 
'''Syzygy Bases''', <ref>[http://www.talkchess.com/forum/viewtopic.php?t=47681&start=45 Re: New 6-piece tablebases] by [[Ronald de Man]], [[CCC]], April 10, 2013</ref><br/>
a compact six piece endgame database developed by [[Ronald de Man]], published April 01, 2013, but not as [https://en.wikipedia.org/wiki/April_Fools%27_Day April Fool]. Syzygy Bases consist of two sets of files, '''WDL''' files storing win/draw/loss information considering the [[Fifty-move Rule|fifty-move rule]] for access during [[Search|search]], and '''DTZ''' files with [[Endgame Tablebases#DTZ50|distance-to-zero]] information for access at the [[Root|root]]. The generator is released under the [[Free Software Foundation#GPL|GNU General Public License Version 2]], the [[Thread|thread safe]] probing code is released without restrictions <ref>[http://www.talkchess.com/forum/viewtopic.php?t=47681 New 6-piece tablebases] by [[Ronald de Man]], [[CCC]], April 01, 2013</ref> . As of February 2015, all 3-5 and most important 6-men Syzygy Bases are commercially available on 4 [https://en.wikipedia.org/wiki/DVD DVDs] by [[ChessBase]] as ''Endgame Turbo 4'' for their products [[Fritz|Deep Fritz 14]], [[Komodo#8|Komodo Chess 8]], [[Houdini|Houdini 4]] or [[ChessBase (Database)|ChessBase 12/13]] <ref>[http://shop.chessbase.com/en/products/endspiel_turbo_4 Endgame Turbo 4] by [[ChessBase]]</ref> <ref>[http://en.chessbase.com/post/syzygy-tablebases-newest-fastest-smallest Syzygy Tablebases: newest, fastest, smallest] by [[Albert Silver]], [[ChessBase|ChessBase News]], February 08, 2015</ref> .  
+
a compact six piece endgame database developed by [[Ronald de Man]], published on April 01, 2013. Since August 2018, '''seven piece''' Syzygy Bases are available after an effort by [[Bojun Guo]] started in March 2018 <ref>[http://talkchess.com/forum3/viewtopic.php?f=7&t=66797&start=472 Re: 7-men Syzygy attempt] by [[Bojun Guo]], [[CCC]], August 19, 2018 </ref>. Syzygy Bases consist of two sets of files, '''WDL''' files storing win/draw/loss information considering the [[Fifty-move Rule|fifty-move rule]] for access during [[Search|search]], and '''DTZ''' files with [[Endgame Tablebases#DTZ50|distance-to-zero]] information for access at the [[Root|root]]. The generator is released under the [[Free Software Foundation#GPL|GNU General Public License Version 2]], the [[Thread|thread safe]] probing code is released without restrictions <ref>[http://www.talkchess.com/forum/viewtopic.php?t=47681 New 6-piece tablebases] by [[Ronald de Man]], [[CCC]], April 01, 2013</ref> . As of February 2015, all 3-5 and most important 6-men Syzygy Bases are commercially available on 4 [https://en.wikipedia.org/wiki/DVD DVDs] by [[ChessBase]] as ''Endgame Turbo 4'' for their products [[Fritz|Deep Fritz 14]], [[Komodo#8|Komodo Chess 8]], [[Houdini|Houdini 4]] or [[ChessBase (Database)|ChessBase 12/13]] <ref>[http://shop.chessbase.com/en/products/endspiel_turbo_4 Endgame Turbo 4] by [[ChessBase]]</ref> <ref>[http://en.chessbase.com/post/syzygy-tablebases-newest-fastest-smallest Syzygy Tablebases: newest, fastest, smallest] by [[Albert Silver]], [[ChessBase|ChessBase News]], February 08, 2015</ref>.  
  
 
=File Sizes=  
 
=File Sizes=  
Line 12: Line 12:
 
! WDL  
 
! WDL  
 
! DTZ  
 
! DTZ  
 +
! Total
 
|-
 
|-
 
! 5  
 
! 5  
| style="text-align:right;" | 378 MiB  
+
| style="text-align:right;" | 378 [https://en.wikipedia.org/wiki/Mebibyte MiB]
 
| style="text-align:right;" | 561 MiB  
 
| style="text-align:right;" | 561 MiB  
 +
| rowspan=2 | 151 [https://en.wikipedia.org/wiki/Gigabyte GB]
 
|-
 
|-
 
! 6  
 
! 6  
| style="text-align:right;" | 68.3 GiB  
+
| style="text-align:right;" | 68.3 [https://en.wikipedia.org/wiki/Gibibyte GiB]
 
| style="text-align:right;" | 81.9 GiB  
 
| style="text-align:right;" | 81.9 GiB  
 +
|-
 +
! 7
 +
|
 +
|
 +
| style="text-align:right;" | 17  [https://en.wikipedia.org/wiki/Terabyte TB]
 
|}
 
|}
  

Revision as of 23:35, 20 August 2018

Home * Knowledge * Endgame Tablebases * Syzygy Bases

Syzygy - Three Planets Dance Over La Silla [1]

Syzygy Bases, [2]
a compact six piece endgame database developed by Ronald de Man, published on April 01, 2013. Since August 2018, seven piece Syzygy Bases are available after an effort by Bojun Guo started in March 2018 [3]. Syzygy Bases consist of two sets of files, WDL files storing win/draw/loss information considering the fifty-move rule for access during search, and DTZ files with distance-to-zero information for access at the root. The generator is released under the GNU General Public License Version 2, the thread safe probing code is released without restrictions [4] . As of February 2015, all 3-5 and most important 6-men Syzygy Bases are commercially available on 4 DVDs by ChessBase as Endgame Turbo 4 for their products Deep Fritz 14, Komodo Chess 8, Houdini 4 or ChessBase 12/13 [5] [6].

File Sizes

Men WDL DTZ Total
5 378 MiB 561 MiB 151 GB
6 68.3 GiB 81.9 GiB
7 17 TB

The additional use of Haswell's BMI2 Parallel Bits Deposit (PDEP) and Parallel Bits Extract (PEXT) instructions, or their slower serial implementations, allows further size reduction [7] .

Generation of 7-men tablebases would require about 1 TB of RAM. Generation time will be about 64 x per table, which means around 175 x time total [8] . Ronald de Man isn't interested in creation of 7-men Syzygy [9] .

During the Search

During the search, with the WDL tables stored on SSD [10] , it is possible to probe the tables at all depths without much slowdown. They have been tested in Ronald de Man's engine Sjaak (playing on FICS as TrojanKnight(C)) a couple of months quite successfully, don't probing in quiescence search.

At the Root

At the root, since pure DTZ50-optimal play (i.e. minimaxing the number of moves to the next capture or pawn move by either side) can be very unnatural, it might be desirable to let the engine search on the winning moves until it becomes clear that insufficient progress is being made and only then switch to DTZ-optimal play (e.g. by detecting repetitions and monitoring the halfmove clock) [11] .

Quotes

by Ronald de Man in a reply to Guy Haworth, April 06, 2013 [12] :

I create both WDL and DTZ in one go, so I don't use WDL in the creation of DTZ. The algorithm used is the grandfather algorithm with 2 plies per iteration (I think HGM calls this leapfrogging, but I might be wrong). I tried the outcounting method, but it didn't seem to be competitive (and it makes things more complicated). [13] [14]
A pure WDL/DTZ pair is not of much use for creating WDL50+/DTZ50+. I create tables in RAM that have all the information necessary for WDL50+ and DTZ50+, then permute them to different indexing schemes and compress. I do test runs on subsets of the data to find good permutations. (The idea to try permutations is from Jesper Torp Kristensen's master thesis.) [15] [16] 

Endgame News

In his 2014 Chess Endgame News in ICGA Journal, Vol. 37, No. 2 [17] , Guy Haworth classified Syzygy Bases as new data in three ways:

  1. 5-valued scale for evaluating positions in the context of the FIDE 50-move rule (50mr) which constrains the length of phases of play
    1. +2 ≡ unconditional win for the side to move
    2. +1 ≡ ‘win’ which can be frustrated by best play and a 50mr draw-claim
    3. _0 ≡ unconditional draw
    4. -1 ≡ ‘loss’ saved by a 50mr draw-claim
    5. -2 ≡ unconditional loss
  2. depths for ‘50mr draw’ positions with value ±1
  3. depths in symmetric, information-preserving ply ‘p’

and further gives some news about early software bugs and glitches concerning ChessBase products, and the importance of MD5 to check the EGT integrity.

Fathom

Fathom is a stand-alone Syzygy based probing tool and API by Basil Falcinelli, introduced in November 2015 along with his Gull 3 release [18] . Unlike the original tbprobe code, Fathom does not necessarily require the callee to provide move generation functionality. The new modifications and extensions to Ronald de Man's original code which can be "redistributed and/or modified without restrictions", are released under the permissive MIT License. The API consists of three functions [19] :

  • tb_init initializes the tablebase
  • tb_probe_wdl probes the Win-Draw-Loss (WDL) table for a given position
  • tb_probe_root probes the Distance-To-Zero (DTZ) table for the given position.

Jon Dart has a fork of Fathom with some bug fixes and enhancements [20].

See also

Publications

Forum Posts

2013 ...

2014

2015 ...

2016

Re: Stockfish 7 and partial 6 piece syzygy problem? by Marco Costalba, CCC, September 01, 2016

2017

2018

Re: 7-men Syzygy attempt by Bojun Guo, CCC, August 19, 2018

External Links

Tablebase

Fathom

ChessBase

Misc

Michael Brecker, Mike Stern, Jeff Andrews, Adam Nussbaum, Joey Calderazzo

References

  1. It’s a real treat for photographers and astronomers alike: our skies are currently witnessing a phenomenon known as a syzygy — when three celestial bodies (or more) nearly align themselves in the sky. When celestial bodies have similar ecliptic longitude, this event is also known as a triple near-conjunction. Of course, this is just a trick of perspective, but this doesn't make it any less spectacular. In this case, these bodies are three planets, and the only thing needed to enjoy the show is a clear view of the sky at sunset. Luckily, this is what happened for ESO photo ambassador Yuri Beletsky, who had the chance to spot this spectacular view from ESO's La Silla Observatory in northern Chile on Sunday May 26 , 2013. Above the round domes of the telescopes, three of the planets in our Solar SystemJupiter (top), Venus (lower left), and Mercury (lower right) — were revealed aftersunset, engaged in their cosmic dance. An alignment like this happens only once every several years. The last one took place in May 2011, and the next one will not be until October 2015. This celestial triangle was at its best over the last week of May, but you may still be able to catch a glimpse of the three planets as they form ever-changing arrangements during their journey across the sky - source Three Planets Dance Over La Silla | ESO, Syzygy (astronomy) from Wikipedia
  2. Re: New 6-piece tablebases by Ronald de Man, CCC, April 10, 2013
  3. Re: 7-men Syzygy attempt by Bojun Guo, CCC, August 19, 2018
  4. New 6-piece tablebases by Ronald de Man, CCC, April 01, 2013
  5. Endgame Turbo 4 by ChessBase
  6. Syzygy Tablebases: newest, fastest, smallest by Albert Silver, ChessBase News, February 08, 2015
  7. Re: PEXT Bitboards by Ronald de Man, CCC, June 07, 2013
  8. Re: Syzygy tb generator for windows by syzygy, CCRL Discussion Board, June 01, 2014
  9. Re: 7-piece syzygy by syzygy, CCRL Discussion Board, July 03, 2014
  10. Re: SSD and the use of Tablebases by Ronald de Man, CCC, May 08, 2013
  11. Re: New 6-piece tablebases by Ronald de Man, CCC, April 05, 2013
  12. Re: New 6-piece tablebase generator by syzygy, CCRL Discussion Board, April 06, 2013
  13. Retrograde tablebase methods by BB+, OpenChess Forum, November 26, 2010
  14. Leapfrog: Retrograde Analysis from Leapfrog tablebase generator by Harm Geert Muller
  15. Jesper Torp Kristensen (2005). Generation and compression of endgame tables in chess with fast random access using OBDDs. Master thesis, Supervisor Peter Bro Miltersen, Aarhus University, pdf
  16. OBDD - Ordered Binary Decision Diagram from Wikipedia
  17. Guy Haworth (2014). Chess Endgame News. ICGA Journal, Vol. 37, No. 2
  18. Gull 3 Linux+Syzygy and Fathom released by Basil Falcinelli, CCC, November 20, 2015
  19. GitHub - basil00/Fathom: Syzygy TB probe tool by Basil Falcinelli
  20. jdart1/Fathom · GitHub by Jon Dart
  21. Found an interesting research by Kirill Kryukov, April, 12, 2013
  22. Wine (software) from Wikipedia
  23. N. Jesper Larsson, Alistair Moffat (1999). Offline Dictionary-Based Compression. DCC'99, pdf
  24. BitTorrent from Wikipedia

Up one level