Author: Angrim
Date: 19:59:08 10/21/01
Go up one level in this thread
On October 21, 2001 at 20:59:30, Ratko V Tomic wrote: >Dan: >>>I don't know why you need to know the distance to mate (which is given >>> as the reason not to store the move). If you make the best >>> possible move, then it does not matter what the distance is. > >>If you only use N piece tablebases once you are down to N pieces on >>the board, then your idea would work. However you also need to be >>able to probe them when you reach an N piece position in the search, >>and want to find out if this position is won or lost. For this purpose >>all you need is win/draw/loss, and some people do use tablebases that >>only store this information since they take less space. But to find >>the shortest win when searching a position with more than N pieces, >>you need to have distance to mate stored in the table. > >Dan was talking about keeping the best move (instead of distance to >mate), not the win/draw/loss only. Knowing the best move implies >the knowledge of the distance to mate since the child nodes >of a table position are also table positions i.e. one can follow >the best moves and obtain quickly the distance to mate. So, here >one would trade off potentially large quantities of table space >for some additional time cost in extracting the distance-to-mate >value from the best-move value. So you are suggesting following the chain of "best move" values to find the positions win/loss/draw value even in the search? That would be horribly expensive time-wise, as it would take N+1 table probes to find the score for a mate in N since you would have to follow the chain clear till the king was captured. You also have a problem with draws here, looks like you would need to do up to 100 table probes to find that a pos was a draw by 50 turn rule. > >Since the best-move encoding can take advantage of any endgame >knowledge one can put into the move generator (used to list the >available moves and specify the best one), this approach allows >potentially large space savings which is further improvable as >the more knowledge gets added to the encoder (using arithmetic >encoding and a good quality generator, one may encode the best >move in a fraction of a single bit, at least for those clasess >of endgame positions where the generator can offer the best >move with a probability greater than 50%). Optimist :) To compress to less than 1 bit per position you would have to guess right a lot more than 50% of the time. When you pass 50% success rate, the cost to store a position which was guessed correctly does drop below one bit, but the wrong guesses take several bits each to store and pull the average back up. Note that Nalimov tables are compressed, and average around 1.3 bits per position. They use huffman rather than arithmetic encoding as the final layer of compression, possibly because of patents on arithmetic encoding. > The direct distance >to mate encoding doesn't offer any obvious way to save space >by adding endgame knowledge into the encoder. Actually, there is a somewhat similar idea for dtm tables, which is not used that I know of. The idea being to guess the dtm value useing endgame-specific knowlege, and produce a series of guesses similar to your series of guessed moves. Then store the index into the series of guessed values. If you guess right often enough you end up storeing a whole lot of 0s which then compress very nice. I expect for either method, guessing the right value often enough to result in improved compression is quite hard, and very very slow. Angrim
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.