Author: Paul Byrne
Date: 01:22:50 10/28/01
Go up one level in this thread
On October 28, 2001 at 03:34:23, Poschmann wrote: >On October 28, 2001 at 02:57:59, Poschmann wrote: > >>On October 28, 2001 at 02:50:56, Poschmann wrote: >> >>>On October 28, 2001 at 02:19:31, Paul Byrne wrote: >>> >>>>I've been looking at tablebases lately and was wondering if anyone >>>>has ever played with this idea (before I spend too much time on it!) >>>> >>>>Basically, take the normal (Nalimov or whatever) tablebases in their >>>>uncompressed form and divide the mate-in-x or loss-in-x values by some >>>>number N. So mate-in-1 through N become (+1) mate-in-(N+1) through 2*N >>>>become (+2), etc. Then compress the resulting files as usual. >>>> >>>>The idea being to reduce the number of different values to make the file >>>>more compressible. >>>> >>>>This would, of course, make life a little more difficult for the engine. :) >>>>When the position is not yet into a tablebase, there would be little effect -- >>>>other than any mate/loss scores being a little inaccurate. Once the position >>>>on the board is actually a tablebase position, a short search would have to >>>>be done to determine the correct move. For example, if the position OTB is >>>>scored as (+5), then one would search for the move that forces a (+4) position >>>>the quickest. >>>> >>>>I did a little test to see if the space savings is worthwhile... >>>>Using the kbbkn.nbb/nbw tablebases (something with long mates) and the >>>>kqnkn.nbb/nbw tablebases (mostly short mates) with various N's -- the >>>>numbers are the percentage of the regular _compressed_ tablebases: >>>> >>>> N=2 N=3 N=4 N=5 N=10 N=100 >>>>kbbkn.nbb 84.67 75.00 68.26 63.74 52.08 23.11 >>>>kbbkn.nbw 82.96 73.21 66.98 62.13 47.80 9.10 >>>>kqnkn.nbb 64.40 48.51 40.58 31.93 19.21 5.86 >>>>kqnkn.nbw 63.51 46.43 37.20 28.70 6.36 2.57 >>>> >>>>The last 2 columns were just out of curiousity. :) >>>> >>>>The question is, how large can N be made while still allowing tablebase >>>>positions to be played out in a reasonable amount of time? Don't know (yet). >>>> >>>>None of this would help for generating tablebases, of course. You still need >>>>the normal tablebases to generate the reduced ones. And I'd imagine most >>>>engine authors would prefer the full tablebases, but for the average >>>>player I don't know they'd notice much difference and could save a few GB >>>>of disk space... less stuff to distribute or download too. >>>> >>>>I suppose a lot of folks have enough disk space for 3/4/5 man tables >>>>nowadays, but when the 6 man tables become more complete/common, this may >>>>help some. >>>> >>>>-paul >>> >>>If a program uses tablebaeses it do it in the following way: >>>1. Look into the tablebases to find the current position. For example mate in >> M moves. >> 2. Generate all possible moves in this position. Generate this position. >> Look in the tablebases, if this position has a distance of M-1 moves to the >> end. If this holds true, select the move. If not, try the next one. >> -> Therefore you need the true distances to mate in all possible positions. >> >>Ralf Poschmann > >Even if you use a N ply search from the current position to find out the next >move with another value this still holds true. Example: >1. Your reduced tablebase value is k=K/N. K is the true distance to mate >2. You are looking for a position with l=k-1 >3. You can not distinguish, if L=(k-1)*N or L=(k-1)*N+N-1 > >Because the order of evaluation of moves is randomly, an arbitrary move >with value l=k-1 is selected. Therefore your mate solution could be much longer >then the optimal one. In the worst case you need probably N times more moves to >achive the mate. > >Ralf Poschmann I'm pretty sure it is always possible to determine a true mate-in-n value from such a tablebase. - Suppose the current position has a value of +5 (so the true value is somewhere between 4*N+1 and 5*N). - First do a 1 ply search -- that is, test each of our moves. If you find one that is -4, then you pick that move. In this case you know the original position must have an actual value of 4*N+1. (Look at it this way, if N=4, then you know the value is from mate-in-17 and 20. If it is possible to make a move and hit a position that is between loss-in-13 and 16, then the original position MUST have been mate-in-17. - If you don't see a -4, then take each of the moves that produces a -5 position and search deeper (anything -6 or more can be discarded). - Keep increasing the depth until you can produce a -4. - The actual mate-in-n value can be determined by how deep you have to look; the maximum depth you might have to search is determined by N. So I'm pretty sure it is always possible to play optimally once you actually get a tablebase position. I'm not sure how many tablebase lookups will be required to do it though. - paul
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.