Author: blass uri
Date: 08:20:50 10/11/98
Go up one level in this thread
On October 11, 1998 at 11:07:20, Robert Hyatt wrote: >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 > > >two things here... > >1. I'm not aware of any program that can "search" KP vs K to a win. In >Crafty, I added special evaluation for KP vs K so that I can play it correctly >without a tablebase... I meant only to do the right moves after search and it is not a problem with the evaluation function of all the top programs > >2. however the real point is deep in the search, say KRRP vs KRR, and you find >a way to trade all 4 rooks leaving you in a KP vs K ending. Do you do it? Only >if you are sure it is not drawn... so you need this *way* out in the search... I agree you need files but only for result in KP vs K ending and not for moves. 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.