In a message dated 12/10/01 7:42:55 PM Pacific Standard Time,
tomh_at_po.crl.go.jp writes:
> > My own rule is much stronger; I call it "Raymond's Rule" because I
> > worked it out, implemented it, and discussed it with others before anyone
> > else thought about it. Noone on this forum has yet given any indication
> > that he understands why it's important.
>
> Well, I haven't been listening for a while. Would you care to go into
> more detail about this?
Horne: All 'A's play home immediately, all '2's play home if the same-suit
'A' is already there, an 'N' plays home if the same-suit 'N-1' and both
'N-1's of the opposite color are already home.
Raymond: All 'A's play home immediately, an 'N' plays home if the same-suit
'N-1', both 'N-2's of the opposite color, and the other same-color 'N-3' are
already home.
> > One of my solver's goals has already been achieved.
>
> Cool.
Hmmmm. A trendy new Japanese expression?
> By the way, if I might delve into solver internals here for a moment, do
> you use a position store to keep track of already visited positions?
Yes, a transposition table is mandatory unless I want to spend several weeks
trying to find a solution to a single deal. But I never record all positions,
and in some cases positions are retained for shorter or longer periods of
time.
> ...what is the smallest number of bytes required to encode a position?
Information theory may show that fewer bytes are necessary, but the smallest
practical representation I've worked out is 36 bytes. However, a long series
of positions can be represented in many fewer than 36 bytes per position.
> Shlomi uses MD5 over the whole position (guaranteed to have collisions
> overall, though I can't prove it'll always, or ever, happen within a given
> game),
I've experimented with a dozen hash schemes. MD5 was far too slow.
> ...and I use a simple sixbit compression scheme over the whole
> position (with the piles sorted). My current implementation has two
> features: perfect hash and invertible. Now, for the "have I been here
> before" test, only a perfect hash is needed, so it should be possible to
> separate these functions, keeping very lightly compressed representations
> around on queues of positions waiting to be evaluated, while the hash can
> be very compact but not invertible (but still perfect).
The hash I use has collisions but not many, while it requires very little
effort to create the hash for a position. Overall much faster than any other
I tried.
> Can you get away with just the visible cards,
You can get away with as little as you want. For about a year I hashed only
the visible cards, but not all of them. But the less you use, the bigger the
buckets and the longer the secondary search.
> ...or just the cards that have been moved,
Yes. As little as you want.
> (A drawback of a position store is that it prevents the cool feature of
> having the solver keep going after finding a solution, looking for others.
That shouldn't be a problem, unless something in your implementation gets in
the way.
Bill Raymond
Received on Tue Dec 11 2001 - 01:25:47 IST