Author: Roberto Waldteufel
Date: 04:52:57 10/11/98
Go up one level in this thread
On October 11, 1998 at 03:07:04, blass uri wrote: > >On October 11, 1998 at 00:42:55, Robert Hyatt wrote: > >>On October 10, 1998 at 00:56:05, blass uri wrote: >> >>> >>>On October 09, 1998 at 22:54:49, Roberto Waldteufel wrote: >>> >>>> >>>>On October 09, 1998 at 18:46:36, David Eppstein wrote: >>>> >>>>>On October 09, 1998 at 15:24:26, Robert Hyatt wrote: >>>>>>This doesn't matter however, because *every* possible position must be accounted >>>>>>for, with an exact distance to mate for the side on move with that specific >>>>>>piece configuration. So they *all* have to be computed to build the next one >>>>>>after them... >>>>> >>>>>You don't need distance to mate if you are searching from a non-tablebase >>>>>position trying to reach a tablebase position (and aren't worried about the 50 >>>>>move rule, but you must not be since you're using distance to mate). >>>>> >>>>>If the actual game reaches a won tablebase position, you need some way to force >>>>>progress, but it doesn't have to be distance to mate. If you can always search >>>>>deeply enough to find a conversion (capture or pawn move), you can use distance >>>>>to conversion, and only store win/loss/draw in the tablebase. In any KXP-KP or >>>>>KX-KPP endgame, searching deeply enough to find a conversion should be easy >>>>>(there are fewer than a million distinct positions in which at most one pawn has >>>>>moved, so you can load just that part of the tablebase into memory and use the >>>>>hashtable to do the search quickly no matter how deep it is). >>>>> >>>>>But I agree with your main point, that the heuristics suggested by the poster >>>>>you were responding to aren't good enough -- the information needs to be exact, >>>>>and you need to compute lots of other tablebases before you can think about >>>>>KPP-KP. >>>> >>>>Even if the search were too deep to be feasible, eg an ending like KBBKN, it is >>>>still possible to reduce memory access requirements during the search by storing >>>>only win/loss/draw information, if we maintain a separate tablebase (not used in >>>>the search) which simply contains the best move >>> >>>You need memory to store the best move for example in KBBKN for the stronger >>>side the maximal number of legal moves is 8+13+13=34 legal moves >>>and you need 6 bits for a move so I think you do not save memory by this. >>>If you have a good order of moves and always 1 of the first 32 moves is best you >>>can need only 5 bits >>> >> >> >>I don't want to sound "harsh" but let's not get rediculous. Exactly *how* >>can we generate moves and *guarantee* that the best move is in the first >>32? That is completely *impossible* to do, and discussing it makes no sense >>at all. >> >>Also, in databases, we *do* *not* store "moves". That is a misconception of >>some sort. Moves are not stored, only the status of each possible position. > >I know that we store a number for every position and the numbers represent moves >but I understand that the idea of roberto is to to store numbers that represent >moves and to store the result(only in win,draw,loss) instead of storing numbers >that represent exact results > >In KBBvs KN we can do for every position a list of legal moves such that the >moves that lose a bishop without giving the oppoent to mate in 1 or causing the >distance of the kings to be longer are in the end of the list. > >If in all the positions there is a best move from the 32 first moves in the list >we can store the right move by 5 bits. >> >> >> >> >>>If you store distance to conversion with my idea you need only 5 bits >>>for 1-2,3-4,...49-50,draw,loss >>>You need to do a search but I do not think there is a problem with small search. >>> >>>Uri >> >> >>this kind of statement isn't helping, either. "I do not think..." is not >>a convincing argument. > >you need to search only to improve the score. >and if 2 plies are not enough you search for 4 plies > > "I implemented this and can prove that it will work" >is >>going to convince me a lot quicker. > >I did not try to implement it but I see no problems with the idea. > > "thinking" doesn't cut it here. It *has* >>to be right or it will certainly be wrong... And wrong we can't stand, because >>we trust these results *perfectly*... > >I agree it has to be right but I do not see a reason why it is wrong >The algoritam is simple and the only problem I can see is a problem of time but >I understand that 1000 hits on the tablebases per position is not a problem and >you do not need more to search 4 plies(for most of the lines you need only 2 >plies and 4 plies are only for best defences of the loser). > >Uri Hi Uri, Let me explain exactly what I had in mind. For something like KPK my method requires *two* files, a small one and a large one. Whenever a KPK position with stronger side to move occurs in the regular search, I look it up in the small file, where a single bit per position is stored to indicate win/draw and I return the result as appropriate. Many endings would require the possibility of loss (therefore needing 2 bits per position instead of 1), but in KPvK there is no possibility of a loss for the stronger side, so 1 bit per position is rquired. This cuts down on the size of the table for he purpose of table look-ups during the search, which must be very fast, so I thought a smaller table would cut down on memory bandwidth and improve speed. When the program finds itself with a KPK position at the root, no score is necessary, but a move is needed. This is where the large file comes in. This would contain a move for every position. You could try to compress the way the move is stored - I use 1 byte to store the move, consisting of 6 bits for destination square and two bits to identify the moving piece and if the move involves an underpromotion (there exist 6 KPK positions in which the only way to win is to underpromote to a rook). But it is not so important for this file to be compressed, because you only access it once to make the move, with no searching at all. I have implemented and tested this in my program Rabbit, and it definately works. I have also constructed move tables for KQK and KRK which work in a similar way, except there is no small file of win/draw states, because the stronger side to move can *always* win these positions. I have not yet successfully implemented KBNK (my next target ending), but I have dabbled a bit with this. Here the stronger side does not *always* have a win, even with the move, because the knight may get trapped in a corner, but it might be cheaper to have a special piece of code to recognise these rare cases rather than a table of win/draw results consisting of 99.9999% wins. However, once we can tell wins apart from draws, a table of moves is all that is needed to play out the mate perfectly. However, the size of 4-piece tables really does require that we take full advantage of symmetry to reduce the number of positions, and that in turn complicates the coding considerably. In principle I see no reason why this idea could not be extended to other tablebases. It is really just a different way of organising the information so that the nodes inside the search only use a small fraction of the total memory needed for the conventional distance-score. Best wishes, Roberto
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.