|Subject:||Re: [Bug-gnubg] (OT) Position ID documentation|
|Date:||Tue, 25 May 2010 13:29:51 +0000|
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
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
> you'd have to be a mathematical masochist to try it!
> Walter states that the number of possible positions in backgammon is:
> 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.
> *) Yes, I know which day it is....
> Bug-gnubg mailing list
Get a new e-mail account with Hotmail - Free. Sign-up now.
|[Prev in Thread]||Current Thread||[Next in Thread]|