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

[保坂範行]

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