bug-gnubg
[Top][All Lists]

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

 From: Øystein Johansen Subject: Re: [Bug-gnubg] (OT) Position ID documentation Date: Tue, 25 May 2010 12:41:20 +0200

A bit off topic:

The first note at the end of the page says:
<quote>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!</quote>

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....