Author: Les Fernandez
Date: 08:34:48 01/30/02
Go up one level in this thread
On January 30, 2002 at 08:44:33, Vincent Diepeveen wrote: >On January 30, 2002 at 01:56:33, Dann Corbit wrote: > >>On January 30, 2002 at 00:03:19, Robert Hyatt wrote: >>>On January 29, 2002 at 13:58:20, Dann Corbit wrote: >>>>No. His notion is that if you mirror using every symmetry, the total number of >>>>those positions (including ALL reflections) would be less than 2^81 in that >>>>category. >>> >>>OK. You are a math guy. If you allow for 8 symmetries, which is false for >>>positions with pawns, you reduce the number of bits by a factor of 8, which >>>is 3 bits. That is the mistake that is being made here, unless I misunderstand >>>something seriously. IE for king vs king, allowing _all_ possible permutations >>>even with two kings on one square, you get 64^2 positions, which is >>>2^12. If you take into account 8 symmetries, you reduce that to 2^9 positions, >>>not 2^(12/8)... >> >>Let's suppose that you need 170 bits to encode a chess position. Now, with that >>position [for instance], you may have automatically stored 50 permutation of it. >> The net number of bits needed to store each of those 50 positions is 170/50 = >>3.4 bits. Any time you run into one of the others, you perform the same >>algorithm and discard any duplicates (low-order keys already stored). You end >>up storing a single position, which represents an entire class of positions. > >this is wrong. you need 170 bits to store a position then. the other >positions i don't store in my EGTBs either, nor does Eugene store it. > >Something simple you guys try to present as something big. I have seen >this a lot in computerchess. It is complete bla bla BS. Also what you guys >do is already known as mirrorring. Ernst A Heinz has written a lot in >ICCA/ICGA papers about mirrorring. Vinny I can assure you that there is more to this then "just" mirrorring. Mirrorring to me implies some form of symmetry and although mirrorring is certainly a part of all this a big portion has nothing to do with mirrorring that you seem to hesitate addressing. With that being the case your statement above is wrong. > >Did you know that white/black mirrorring already was invented in mirrorring? > >Inventing new terms 'reflections' for this is simply not the way to go. > >>>>>Second, you simply store the index into the ordered list of positions. >>>> >>>>With all its associated data. >>>> >>>>>But you totally ignore how you are going to turn that "index" into a real >>>>>position? Or how you are going to turn a real position into that index? >>>> >>>>You take the position you are interested, and create all of its reflections (it >>>>can be hundreds). >>> >>> >>>How can there be more than 8 "reflections"? you can find symmetry along thhe >>>vertical center, horizontal center, and the two diagonals. >> >>Well, they are actually more than just reflections. >>The sliding piece is also factored into it. Consider this list of positions: >>2Q3nk/6n1/8/8/8/8/8/K7 w - - ce 32734; pv Qh3+; >>2q4k/8/8/8/8/8/1N6/KN6 b - - ce 32734; pv Qa6+; >>6nk/3Q2n1/8/8/8/8/8/K7 w - - ce 32734; pv Qh3+; >>6nk/6n1/4Q3/8/8/8/8/K7 w - - ce 32734; pv Qh3+; >>6nk/6n1/8/5Q2/8/8/8/K7 w - - ce 32734; pv Qh3+; >>6nk/6n1/8/8/6Q1/8/8/K7 w - - ce 32734; pv Qh3+; >>6nk/6n1/8/8/8/1Q6/8/K7 w - - ce 32734; pv Qh3+; >>6nk/6n1/8/8/8/2Q5/8/K7 w - - ce 32734; pv Qh3+; >>6nk/6n1/8/8/8/3Q4/8/K7 w - - ce 32734; pv Qh3+; >>6nk/6n1/8/8/8/4Q3/8/K7 w - - ce 32734; pv Qh3+; >>6nk/6n1/8/8/8/5Q2/8/K7 w - - ce 32734; pv Qh3+; >>6nk/6n1/8/8/8/6Q1/8/K7 w - - ce 32734; pv Qh3+; >>6nk/6n1/8/8/8/8/6Q1/K7 w - - ce 32734; pv Qh3+; >>6nk/6n1/8/8/8/8/8/K4Q2 w - - ce 32734; pv Qh3+; >>6nk/6n1/8/8/8/Q7/8/K7 w - - ce 32734; pv Qh3+; >>7k/1q6/8/8/8/8/1N6/KN6 b - - ce 32734; pv Qa6+; >>7k/8/1q6/8/8/8/1N6/KN6 b - - ce 32734; pv Qa6+; >>7k/8/2q5/8/8/8/1N6/KN6 b - - ce 32734; pv Qa6+; >>7k/8/3q4/8/8/8/1N6/KN6 b - - ce 32734; pv Qa6+; >>7k/8/4q3/8/8/8/1N6/KN6 b - - ce 32734; pv Qa6+; >>7k/8/5q2/8/8/8/1N6/KN6 b - - ce 32734; pv Qa6+; >>7k/8/6q1/8/8/8/1N6/KN6 b - - ce 32734; pv Qa6+; >>7k/8/7q/8/8/8/1N6/KN6 b - - ce 32734; pv Qa6+; >>7k/8/8/1q6/8/8/1N6/KN6 b - - ce 32734; pv Qa6+; >>7k/8/8/8/2q5/8/1N6/KN6 b - - ce 32734; pv Qa6+; >>7k/8/8/8/8/3q4/1N6/KN6 b - - ce 32734; pv Qa6+; >>7k/8/8/8/8/8/1N2q3/KN6 b - - ce 32734; pv Qa6+; >>7k/8/8/8/8/8/1N6/KN3q2 b - - ce 32734; pv Qa6+; >>k4q2/8/8/8/8/8/6N1/6NK b - - ce 32734; pv Qh6+; >>k7/6q1/8/8/8/8/6N1/6NK b - - ce 32734; pv Qh6+; >>k7/8/1q6/8/8/8/6N1/6NK b - - ce 32734; pv Qh6+; >>k7/8/2q5/8/8/8/6N1/6NK b - - ce 32734; pv Qh6+; >>k7/8/3q4/8/8/8/6N1/6NK b - - ce 32734; pv Qh6+; >>k7/8/4q3/8/8/8/6N1/6NK b - - ce 32734; pv Qh6+; >>k7/8/5q2/8/8/8/6N1/6NK b - - ce 32734; pv Qh6+; >>k7/8/6q1/8/8/8/6N1/6NK b - - ce 32734; pv Qh6+; >>k7/8/8/6q1/8/8/6N1/6NK b - - ce 32734; pv Qh6+; >>k7/8/8/8/5q2/8/6N1/6NK b - - ce 32734; pv Qh6+; >>k7/8/8/8/8/4q3/6N1/6NK b - - ce 32734; pv Qh6+; >>k7/8/8/8/8/8/3q2N1/6NK b - - ce 32734; pv Qh6+; >>k7/8/8/8/8/8/6N1/2q3NK b - - ce 32734; pv Qh6+; >>k7/8/q7/8/8/8/6N1/6NK b - - ce 32734; pv Qh6+; >>kn3Q2/1n6/8/8/8/8/8/7K w - - ce 32734; pv Qa3+; >>kn6/1n2Q3/8/8/8/8/8/7K w - - ce 32734; pv Qa3+; >>kn6/1n6/3Q4/8/8/8/8/7K w - - ce 32734; pv Qa3+; >>kn6/1n6/8/2Q5/8/8/8/7K w - - ce 32734; pv Qa3+; >>kn6/1n6/8/8/1Q6/8/8/7K w - - ce 32734; pv Qa3+; >>kn6/1n6/8/8/8/1Q6/8/7K w - - ce 32734; pv Qa3+; >>kn6/1n6/8/8/8/2Q5/8/7K w - - ce 32734; pv Qa3+; >>kn6/1n6/8/8/8/3Q4/8/7K w - - ce 32734; pv Qa3+; >>kn6/1n6/8/8/8/4Q3/8/7K w - - ce 32734; pv Qa3+; >>kn6/1n6/8/8/8/5Q2/8/7K w - - ce 32734; pv Qa3+; >>kn6/1n6/8/8/8/6Q1/8/7K w - - ce 32734; pv Qa3+; >>kn6/1n6/8/8/8/7Q/8/7K w - - ce 32734; pv Qa3+; >>kn6/1n6/8/8/8/8/1Q6/7K w - - ce 32734; pv Qa3+; >>kn6/1n6/8/8/8/8/8/2Q4K w - - ce 32734; pv Qa3+; >> >>All were generated in a fraction of a second using VB. Now, if we should >>encounter any of those positions in a chess game, we simply run the permutator >>on it, and find the smallest one (quick-select is O(n) on average). We look up >>that key in the database. That gives us the score and the move to make. >> >>>> Then, you lexically sort them from smallest to largest using >>>>memcmp. Then, you look in the database for the smallest of those positions. >>>>The same procedure will have been used to store the original entry into the >>>>database. Let's revisit the set that Les posted: >>> >>> >>>This is simply intractable at terminal nodes in the search tree. Which was >>>+one+ of the points raised here several times. >> >>In that case, don't use it there. Use it only at the root. However, I don't >>think it would be any more expensive than Eugene's tablebase files, if done >>properly. >> >>>>1R3K1k/8/8/8/8/8/8/8 w - - ce 32762; pv Ra8; >>>>2R2K1k/8/8/8/8/8/8/8 w - - ce 32762; pv Ra8; >>>>3R1K1k/8/8/8/8/8/8/8 w - - ce 32762; pv Ra8; >>>>4RK1k/8/8/8/8/8/8/8 w - - ce 32762; pv Ra8; >>>>5K1k/8/8/8/8/8/8/R7 w - - ce 32762; pv Ra8; >>>>5K1k/8/8/8/8/8/R7/8 w - - ce 32762; pv Ra8; >>>>5K1k/8/8/8/8/R7/8/8 w - - ce 32762; pv Ra8; >>>>5K1k/8/8/8/R7/8/8/8 w - - ce 32762; pv Ra8; >>>>5K1k/8/8/R7/8/8/8/8 w - - ce 32762; pv Ra8; >>>>5K1k/8/R7/8/8/8/8/8 w - - ce 32762; pv Ra8; >>>>5K1k/R7/8/8/8/8/8/8 w - - ce 32762; pv Ra8; >>>>7r/8/8/8/8/8/8/K1k5 b - - ce 32762; pv Rh1; >>>>8/7r/8/8/8/8/8/K1k5 b - - ce 32762; pv Rh1; >>>>8/8/7r/8/8/8/8/K1k5 b - - ce 32762; pv Rh1; >>>>8/8/8/7r/8/8/8/K1k5 b - - ce 32762; pv Rh1; >>>>8/8/8/8/7r/8/8/K1k5 b - - ce 32762; pv Rh1; >>>>8/8/8/8/8/7r/8/K1k5 b - - ce 32762; pv Rh1; >>>>8/8/8/8/8/8/7r/K1k5 b - - ce 32762; pv Rh1; >>>>8/8/8/8/8/8/8/1r3k1K b - - ce 32762; pv Ra1; >>>>8/8/8/8/8/8/8/2r2k1K b - - ce 32762; pv Ra1; >>>>8/8/8/8/8/8/8/3r1k1K b - - ce 32762; pv Ra1; >>>>8/8/8/8/8/8/8/4rk1K b - - ce 32762; pv Ra1; >>>>8/8/8/8/8/8/8/K1k1r3 b - - ce 32762; pv Rh1; >>>>8/8/8/8/8/8/8/K1k2r2 b - - ce 32762; pv Rh1; >>>>8/8/8/8/8/8/8/K1k3r1 b - - ce 32762; pv Rh1; >>>>8/8/8/8/8/8/8/K1kr4 b - - ce 32762; pv Rh1; >>>>8/8/8/8/8/8/r7/5k1K b - - ce 32762; pv Ra1; >>>>8/8/8/8/8/r7/8/5k1K b - - ce 32762; pv Ra1; >>>>8/8/8/8/r7/8/8/5k1K b - - ce 32762; pv Ra1; >>>>8/8/8/r7/8/8/8/5k1K b - - ce 32762; pv Ra1; >>>>8/8/r7/8/8/8/8/5k1K b - - ce 32762; pv Ra1; >>>>8/r7/8/8/8/8/8/5k1K b - - ce 32762; pv Ra1; >>>>k1K1R3/8/8/8/8/8/8/8 w - - ce 32762; pv Rh8; >>>>k1K2R2/8/8/8/8/8/8/8 w - - ce 32762; pv Rh8; >>>>k1K3R1/8/8/8/8/8/8/8 w - - ce 32762; pv Rh8; >>>>k1K5/7R/8/8/8/8/8/8 w - - ce 32762; pv Rh8; >>>>k1K5/8/7R/8/8/8/8/8 w - - ce 32762; pv Rh8; >>>>k1K5/8/8/7R/8/8/8/8 w - - ce 32762; pv Rh8; >>>>k1K5/8/8/8/7R/8/8/8 w - - ce 32762; pv Rh8; >>>>k1K5/8/8/8/8/7R/8/8 w - - ce 32762; pv Rh8; >>>>k1K5/8/8/8/8/8/7R/8 w - - ce 32762; pv Rh8; >>>>k1K5/8/8/8/8/8/8/7R w - - ce 32762; pv Rh8; >>>>k1KR4/8/8/8/8/8/8/8 w - - ce 32762; pv Rh8; >>>>r7/8/8/8/8/8/8/5k1K b - - ce 32762; pv Ra1; >>>> >>>>All of these positions are exact equivalents -- created by rotations, >>>>reflections, etc. (should be the pm instead of the pv, but that's neither here >>>>nor there). Anyway, all we need to do is store the first position: >>>>1R3K1k/8/8/8/8/8/8/8 w - - ce 32762; pv Ra8; >>>>And from that, we can generate all the others. Using that position and its >>>>associated information, we can quickly look up the solution to any of the other >>>>problems. We simply take the position we are given and perform the same >>>>rotations and reflections (they are very simple, and the code to do it is posted >>>>on my ftp site). Then, pick the smallest one from that set and look into the >>>>database and see if it is there. If it is present, then we have a solution >>>>move. >>>> >>>>>It is computationally intractable in either direction... >>>> >>>>Not only is it simple to calculate, he has a working version. >>> >>>Simple enough you can do it everywhere in the tree? It doesn't appear to be >>>so. Just doing the symmetries has a big computational requirement of moving >>>an array of board contents thru all sorts of gyrations. >> >>The math is incredibly simple. A lot less work than decompressing a page from a >>Nalimov tablebase file, I would guess.
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.