Re: [Bug-gnubg] (OT) Position ID documentation

[Jonathan Kinsey]

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
> address@hidden
> http://lists.gnu.org/mailman/listinfo/bug-gnubg

---

Get a new e-mail account with Hotmail - Free. Sign-up now.