Author: Guido
Date: 05:28:23 02/07/03
Go up one level in this thread
On February 06, 2003 at 14:07:39, Marc Bourzutschky wrote: >On February 06, 2003 at 13:14:28, Robert Hyatt wrote: > >>On February 05, 2003 at 13:08:06, Marc Bourzutschky wrote: >> >>>On February 05, 2003 at 12:57:40, Robert Hyatt wrote: >>> >>>>On February 05, 2003 at 06:01:16, Marc Bourzutschky wrote: >>>> >>>>>On February 05, 2003 at 04:25:46, GuyHaworth wrote: >>>>> >>>>>> >>>>>>Maybe they differ because an a1-h8 rotation does not leave the position >>>>>>unchanged when there are Pawns on the board. >>>>>> >>>>>>So ... they wouldn't be the same even if there was no e.p. rule. >>>>>> >>>>>>g >>>>> >>>>>The position does not have to be unchanged, only a 1-1 mapping needs to exist. >>>>>The symmetry actually used is: >>>>> >>>>>1. Flip the colors of all pieces >>>>>2. Flip the board (a1 <-> a8, h1 <-> h8, etc) including e.p. square >>>>>3. Change side to move >>>>> >>>>>For KPKP all positions in .nbb can be mapped to a position in .nbw this way, so >>>>>.nbb and .nbw have the same information content. There must be another reason >>>>>why Eugene keeps both files, probably more a convenience than anything else. >>>>>This will get more interesting once he generates KRPKRP, etc. Note that probing >>>>>code needs to be aware of the above transformation even for non-symmetrical >>>>>endings because, e.g., endings such as KPKBP.NBW have to get mapped to KBPKP.NBB >>>>>(including potential e.p. squares). >>>>> >>>>>-Marc >>>> >>>> >>>>Are you considering the 10 squares the king is constrained to occupy? I'm not >>>>sure how the >>>>symmetry will work since there is now a diagonal reflection that must be done, >>>>and that would >>>>leave pawns moving sideways... >>>> >>>>If I understand what you are asking, that is... >>> >>>When pawns are present, the white king is restricted only to the left side of >>>the board, not just the 10 squares of the a1-d1-d4 triangle. >> >> >>I hope that was my point. :) (BTW, I think the king is limited to 1/4 of the >>board, >>not 1/2...) Because you can do vertical/horizontal reflections to put the white >>king >>in the a1-a4-d4-d1-a1 corner of the board...) >> >>back to the symmetry. If you only have one side to move, how do you get >>symmetry? If >>you change the colors, you also change the side to move and you have nothing to >>look up... >>This means more work as now you have to make each move, and then probe. This >>isn't >>the case when you have fully symmetric piece-only endings of course. >> >>However, it _is_ good for a headache to think about it. :) > >It is actually pretty straightforward. This is how it is implemented in >crafty's probe.c: > >Suppose white has a queen, and black a rook and a pawn, and it is white to move. > Since Eugene only has the KRPKQ table but not the KQKRP table, the probe code >does the following: > >1. Switch the arrays with the white and black pieces (this effectively flips the >color of all the pieces) >2. Sets a flag to "invert" the board (a1 <-> a8, h1 <->h8, etc) >3. Switches the side to move from white to black > >This tranformation maps the non-existing KQKRP.NBW ending to the existing >KRPKQ.NBB ending. It does not matter whether there are pawns or not. > >For symmetrical endings the exact same transformation can be applied to map from >"black to move" to "white to move" in the same table. Eugene's code does that >automatically for pawnless symmetric endings, although it can be done equally >well for endings with pawns. >I'm sure once Eugene generates symmetric 6-man >endings with pawns he will implement that symmetry to eliminate one of the >redundant tables... The problem of using one only table for each ending is fairly complex. I solved this problem in the past but I abandoned this idea because it cost a lot of time if used during the search when many accesses must be made to the tables. It could be useful in the ending phase with TBs, because the cost of time becomes insignificant, but in my opinion the game is not worth the candle as the result can be read from the disk without loading the file into the RAM. So for instance consider the KRPKQ ending. There are 4 files: KRPKQ.NBW, KRPKQ.NBB, KQKRP.NBW, KQKRP.NBB. The last two are easily eliminated without problems applying symmetry and exchange of the colour on the first two files. But if we now keep only KRPKQ.NBW we have problems to determine the result of a position when black has to move. The solution I give to this problem consists in simulating the execution of all the black moves arriving at positions where W moves and as consequence it is possible to know the result interrogating the table. At this point I choose the worst W result to calculate the best B result and the correspondent B move. But now there is a problem: if one or more B moves contain a capture or a promotion I have to load another table to find the result. But loading this new table, of which I have only the file with move to W, in some cases I need to repeat the preceding process, i.e. examining all the moves, etc. and this requests a recursive procedure. In this recursion, and also for the KQKRP.NBW, KQKRP.NBB cases, it is necessary to change at any step the result to look for, saving case by case the best or the worst result. I hope to have given an idea of the complexity (and of the time to debug ...) and of the cost of this process if it must repeated many times during the search. Perhaps a better solution to this problem shall exist, but I didn't find it. As last note in generating tablebases it is possible to generate one table separately but the cost in time increase by a factor of about 20 times, because a position must be analyzed calculating moves with depth 2 instead of 1. Ciao Guido
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.