Hi > You could trim off a whole heap of 'unlikely' positions (more than 10 > chequers > on a single point for example),
Are you going to trim this sort of position?? Position ID: tt0NQAD/OwAAMA Match ID: UQkbAAAAAAAA Nori 2010/5/25 Jonathan Kinsey <[email protected]>: > You could trim off a whole heap of 'unlikely' positions (more than 10 > chequers > on a single point for example), then represent them with 63 (or less) bits > and > use the first bit for unusual positions (which will obviously need more than > 64 > bits). > > Jon > > On 25/05/2010 11:41, Øystein Johansen wrote: >> A bit off topic: >> >> The first note at the end of the page says: >> Theoretically, it would be possible to get it down to 64 bits by using >> Walter Trice's /D() >> expressions/ , but I think >> you'd have to be a mathematical masochist to try it! >> >> Walter states that the number of possible positions in backgammon is: >> 18,528,584,051,601,162,496 >> >> However 2^64 is 18,446,744,073,709,551,616 which is a bit lower than the >> theoretical number of positions. >> >> I therefore wonder if the note in the description is a bit wrong..... >> >> This email could end here, but there is more: if it is possible to get >> the number of legal (and relevant) position below 2^64 it would make >> hashing of positions more interesting. As disk space and memory space >> increases a perfect hash of position to 64-bit key would be the ultimate >> solution to ultimate question of life, the universe and everything.* >> Backgammon could be "solved" and implemented. (However finding such >> perfect hashing function seems a bit out of reach at the moment.) >> >> Let's first try to get the number of legal positions below 2^64. The >> difference is "only" 8.190836056001331E+16 positions. I could divide >> this differently into contact and non-contact positions. I could also >> remove irrelevant positions (ie positions already won), but I don't see >> how I can remove much more. I could find illegal positions like both >> players closed out. .... still think we're way above 2^64. >> >> If someone sees a brilliant way of representing a backgammon position >> (just the board) in 64 bit, I would be really interested for pure >> academic interest. >> >> -Øystein >> >> *) Yes, I know which day it is.... >> >> >> >> >> >> >> >> _______________________________________________ >> Bug-gnubg mailing list >> [email protected] >> http://lists.gnu.org/mailman/listinfo/bug-gnubg > > > > > ________________________________ > Get a new e-mail account with Hotmail - Free. Sign-up now. > _______________________________________________ > Bug-gnubg mailing list > [email protected] > http://lists.gnu.org/mailman/listinfo/bug-gnubg > > _______________________________________________ Bug-gnubg mailing list [email protected] http://lists.gnu.org/mailman/listinfo/bug-gnubg
