Author: Dann Corbit
Date: 22:56:33 01/29/02
Go up one level in this thread
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. >>>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.01 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.