Author: Robert Hyatt
Date: 21:03:19 01/29/02
Go up one level in this thread
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)... > >>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. > 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. > >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. > >> >>>> >>>>> >>>>>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; >>>>>k1K3R1/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; >>>>>k1K1R3/8/8/8/8/8/8/8 w - - ce 32762; pv Rh8; >>>>>k1KR4/8/8/8/8/8/8/8 w - - ce 32762; pv Rh8; >>>>>5K1k/R7/8/8/8/8/8/8 w - - ce 32762; pv Ra8; >>>>>5K1k/8/R7/8/8/8/8/8 w - - ce 32762; pv Ra8; >>>>>5K1k/8/8/R7/8/8/8/8 w - - ce 32762; pv Ra8; >>>>>5K1k/8/8/8/R7/8/8/8 w - - ce 32762; pv Ra8; >>>>>5K1k/8/8/8/8/R7/8/8 w - - ce 32762; pv Ra8; >>>>>5K1k/8/8/8/8/8/R7/8 w - - ce 32762; pv Ra8; >>>>>5K1k/8/8/8/8/8/8/R7 w - - ce 32762; pv Ra8; >>>>>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; >>>>>8/8/8/8/8/8/7r/K1k5 b - - ce 32762; pv Rh1; >>>>>8/8/8/8/8/7r/8/K1k5 b - - ce 32762; pv Rh1; >>>>>8/8/8/8/7r/8/8/K1k5 b - - ce 32762; pv Rh1; >>>>>8/8/8/7r/8/8/8/K1k5 b - - ce 32762; pv Rh1; >>>>>8/8/7r/8/8/8/8/K1k5 b - - ce 32762; pv Rh1; >>>>>8/7r/8/8/8/8/8/K1k5 b - - ce 32762; pv Rh1; >>>>>7r/8/8/8/8/8/8/K1k5 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/K1k2r2 b - - ce 32762; pv Rh1; >>>>>8/8/8/8/8/8/8/K1k1r3 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; >>>>>r7/8/8/8/8/8/8/5k1K b - - ce 32762; pv Ra1; >>>>>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;
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.