Author: Vincent Diepeveen
Date: 16:34:49 08/29/05
Go up one level in this thread
On August 29, 2005 at 16:28:39, Eugene Nalimov wrote: >On August 29, 2005 at 15:57:51, Joshua Shriver wrote: > >>Good Afternoon, >> >> What is the WDL format? I've unsuccessfully been able to find information >>on it. Is it a chess specific compression of general data? >> >>-Josh > >Store only Win/Draw/Lost value for every position, not the full value (Win in >N/Draw/Lost in N). > >The simplest way to encode them would be to fit 5 values in a byte. 3**5 == 243, >that is less than 256 different values, so you can store them into a byte. When >probing you can easily get a value by using 243-element decode table (much >faster than divisions). >Other possibility would be to store 4 values into a byte -- 2 bits per position. >Such table would be larger by itself, but it may compresses better -- when I >experimented resulting compressed tables were smaller. > >Or you can store 2 tables -- one with Win/No Win, and other with Lost/No Lost. >Presumable they will compress even better, and in lot of cases during the search >you will probe only one of them, because that is all you need to know. > >Of course all those tables have drawback: you should assume that chess program >that uses only them will be able to win a won position. E.g. it knows that OTB >position is won. It know that out of all moves 3 moves also lead to won >positions. Unfortunately it may not be able to figure out that current position >is (say) mate in 30, move A leads to mate in 29, while moves B and C -- to mate >in 35, and it may decide to make the wrong move. Hopefully such situation is >rare enough, but I suspect it is more often when position is complex enough -- >i.e. exactly when you need TBs. >Thanks, >Eugene Odds of blowing a won position to a draw are real tiny. Especially when using a 20-40 ply search or so in far endgame, which is about the search depths you get typically when you get guided by EGTBs. The huge advantage of WDL over DTM is of course that software using WDL will be able to use all EGTBs in tournaments even at small computers, whereas the ones using DTM will be in serious trouble. It's very likely all 7 men will be generated long before there is enough storage to store them in DTM. Additional advantage of WDL is that you can store in the cache more positions. If i recall well you store uncompressed pages in RAM. That means with say 128MB ram you can store from the tough 6 men around 64 million positions. If some clever guy would rewrite it to a compressed storing of pages (which requires rewriting the compressor basically), we're speaking of a factor 3 to 4 more entries that you can store in RAM. Say roughly 256 million. With the growing search depths and nodes per second of engines that's quite little if you remember well that the total dataset contains 5T positions. This where with WDL the odds for a cache hits are quite bigger as a factor 40-100 more can get stored in cache in such a case. Already for 6 men this is a huge advantage favouring WDL big big big bigtime. With 7 men coming in a few years, storing DTZ or DTM gets just too ugly. So from practical viewpoint WDL has major advantages over DTM. Then we didn't even discuss that it's quite difficult to have all 6 men in nalimov format. Besides Skinner, do you know many who have? >>> >>>It's just computational problem, all you need is 1 array of 2 TB to >>>generate it, and after that supercompress it to WDL format. DTZ is >>>perhaps interesting to generate if your goal is to publish near to >>>maximin positions, but from computerchess viewpoint what matters is the >>>result in the game. That can be either one of the next 3: win, draw or loss. >>> >>>Supercompressed this EGTB in wdl is like 3GB. >>> >>>Additional i'm interested in knowing what from their database what the longest >>>win is for the KRB side in the KRBNKRB egtb. >>> >>>Vincent
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.