Author: Uri Blass
Date: 01:32:41 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 It is not important for games and the only important thing is to reduce the distance for mate. If programs use brute force search they can find a move that reduce the distance for mate. suppose that tablebases tell you that the current move is mate in L=k*N+i when 0<=i<N If you search into depth i+1 by brute force you can find a move that reduces the distance to mate. You do not know i+1 but you can know that i+1<=N so you only need to search depth 1,depth 2...depth N with no pruning and no extensions when you can stop when you find an improvement in the score when the score of every position is defined by the reduced tablebases. Uri
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.