Author: Vincent Diepeveen
Date: 05:44:33 01/30/02
Go up one level in this thread
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. 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.