In a message dated 12/12/01 1:43:51 AM Pacific Standard Time,
tomh_at_po.crl.go.jp writes:
> Indeed. I was using Horne's rule (what can I say, it's obvious), and
> switching to Raymond's rule improved the performance of the solver, not
> just in terms of time, but in terms of quality, which I define in terms of
> the length of the solution in single card moves. As usual, some boards
> got worse, but more got better (by 1/10 of a move on average, but the
> distribution is skewed and a larger number of games got shorter while a
> small number got rather longer). In particular, the 0-freecell games MS
> 5814 and MS 12392 both got worse (but were still solvable).
I can't imagine why any board got worse. Hope I spelled out my rule correctly.
> ...These games require at least Horne's rule to be solvable.
I think you mean tractable.
> > 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.
>
> I presume you mean _at most_ 36 bytes.
Well yes, but the average is many fewer than 36.
> And of course your second point
> there applies to your hash buckets, which are designed so that the
> positions in them are all similar and so you only need to record the
> differences (by storing them in a trie, for example).
One cannot make assumptions about my hash buckets or anything else based upon
what I write about concepts. A hash bucket by definition contains positions
that all hash to a particular value, not positions that are similar.
> > 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.
> Ah. When you know for sure that you'll never visit this position again,
> you don't have to save it.
If only we could know. We cannot.
> I've been using a splay tree (a type of balanced binary tree) instead of a
> hash, to gain the advantages of the caching properties of the splay tree
> (since I know that nearby positions often re-generate the same positions
> again). (OK, and because it's a cool data structure. :-)
Ahhhh!! A real programmer.
> It works pretty
> well when the tree is small, but some boards generate millions of
> intermediate positions, and it starts to take some time. Though, I've
> been thinking that my real problem is that I shouldn't be generating so
> many, and there's probably a big prune somewhere that I'm just too lazy to
> go looking for.
Oops, a real programmer would forego food, sleep and perhaps everything else
other than caffeine and sugar to find that prune.
> Indeed, preliminary analysis of a few boards suggests that 30-40% of the
> intermediate positions are only visited once. While not storing them in
> the first place would be an improvement, I'm still left with 2 million
> instead of 3. How many intermediate positions do you visit, for, say,
> MS#883 with zero freecells? My solver (doesn't solve it, and) generates
> almost 7 million positions, 2.6 million of which are unique, and 24% of
> which are visited only once.
> I'll bet you don't generate that many to begin with.
I've taken all those deals to 7.5m positions at the end, but much larger
numbers have been discarded. Still working on better tools.
BR
Received on Wed Dec 12 2001 - 10:18:05 IST