On Wed, 12 Dec 2001 WKRfresno_at_aol.com wrote:
> I can't imagine why any board got worse. Hope I spelled out my rule correctly.
It has more to do with order of evaluation in my solver. I use some
heuristics to choose a path through the board's solution graph, and small
changes almost anywhere can influence the path, causing it to find a
different solution. My solver is (roughly) BFS, but sometimes I'll do a
branch early 'cause I'm being greedy. Horne's rule might have me remove a
card (and more importantly, ignore the possibilty of not removing it) when
your rule wouldn't, and greed in this case is defined as removing cards.
So it's quite likely to affect the path through the graph.
I have on occasion toyed with the idea of using lookahead rather than
heuristics. For example, since it isn't strictly BFS, when I get to a
node that's been visited before, I always keep the first path. But, I
could backtrack to the common ancestor and keep whichever path is
shortest. I should check how many paths that'd change. Right now I only
get 37% re-visits on average, but it's the exceptions that matter...
> > ...These games require at least Horne's rule to be solvable.
>
> I think you mean tractable.
I should have added, "if you are doing automoves." A greedy automover
that moves things out whenever it can will lose.
> One cannot make assumptions about my hash buckets ...
Oh, I can certainly make assumptions. :-) They might not be correct...
> A hash bucket by definition contains positions that all hash to a
> particular value, not positions that are similar.
True, but with a hash that creates buckets containing similar positions,
the potential to compress the bucket increases, saving space. At the
expense of time. Might not be worth the effort, though.
> Oops, a real programmer would forego food, sleep and perhaps everything else
> other than caffeine and sugar to find that prune.
That would in fact be true in my case, were it not for the fact that I am
a real programmer with a job, and a project with several deadlines
looming. :-( Gathering stats is fine though 'cause I can just let it run
all day. Gotta do something with those background cycles (I'm also doing
OGR). Speculation is also an important part of email breakfast. :-)
Dr. Tom Holroyd
"I am, as I said, inspired by the biological phenomena in which
chemical forces are used in repetitious fashion to produce all
kinds of weird effects (one of which is the author)."
-- Richard Feynman, _There's Plenty of Room at the Bottom_
Received on Wed Dec 12 2001 - 19:10:24 IST