Author: Roberto Waldteufel
Date: 09:00:44 10/11/98
Go up one level in this thread
On October 11, 1998 at 09:23:27, blass uri wrote: > >On October 11, 1998 at 07:52:57, Roberto Waldteufel wrote: > >> >>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 thought that there is a need for this files to be compressed because you have >not infinite memory in the harddisk and if you want to use many files like this >for 4 pieces and for 5 pieces you may have a problem to save the files. > >I understand that you thought about compressing only to do the program faster > >Problem of memory in the harddisk is not important for you now because you did >not implemented even 4 pieces files but it may be important for the future > >In KPK v K the program may play perfect by search so you do not have to save >files >saving files for moves start to be important only for endings like KQKR >positions. >saving files for distance to mate is the same as saving files for moves because >you can compute the move by the distance to mate and the question is only for >what option you need less memory > >Best wishes >Uri I found it was a pain to search for the move in KPK because my search always cuts the search off when it sees a winning position, so it does not look far enough ahead to make progress. If you have to do a special test as to whether to carry on searching, you lose efficiency for all those cases where only the result matters. The table of moves does not take up much space, and saves effort for the search, since this way any interior node of KPK type is automatically a leaf node. 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.