On Wed, 6 Mar 2002 WKRfresno_at_aol.com wrote:
> I doubt that I had much credibility when I wrote that my solver had done over
> one million games per hour last year. Now that yours runs near that magnitude
> people will start to believe it can be done.
Well, I'm not really in that ballpark, but a factor of ten or so would
get me there. That's not really so hard to imagine, in principle. I
know for a fact that there are many places in my solver that could be
sped up through relatively simple optimizations, but a factor of ten
would be difficult without major architectural changes. The biggest
thing is search order. My solver will always do single card moves and
it'll always use a simple tree search with heuristics and no
lookahead. You do multi-card moves and more in-depth analysis of the
positions. Eliminating unlikely moves is a big win. Consider that
when a human expert solves a game, he or she probably only considers
roughly O(N) positions, where N is the number of moves in the game.
That is, a good human player can go through a game without ever
hitting undo, or only hitting it a few times. Even starting over
doesn't increase the number of positions examined much. Right now I'm
looking at maybe 2 or 3 _thousand_ positions. Getting down to 2 or 3
_hundred_ would be in the ballpark of human ability, and at computer
speeds, I don't doubt that 1e6 g/h is possible...
> If you are using an Alpha (64 bits?), can the numbers be normalized to those
> run on other processors?
Well, I have a 666 MHz Alpha, but it's quad-issue, so it can execute 4
instructions simultaneously, but not all possible combinations of
instructions. So the real rate is variable, and these are also RISC
instructions. That is, it's tough to compare with Intel. I don't
have a lot of numbers for other processors. I welcome benchmarks
using Patsolve's autoplay feature. time patsolve -fS -N0 1000. I get
28 sec (user) = 35.7 g/s ~ 128,000 g/h. My 100 MHz Pentium laptop
does it in 355 sec ~ 10,000 g/h. So the Alpha is 12.6 times as fast
even though the clock rate is only 6.6 times as fast. This makes
sense since it's an all-integer computation. You get higher rates
with Alpha if you can mix floating point with integer -- this box has
two FPUs and two integer ALUs.
> Damn. I don't know whether yours (of you) has an apostrophe. Now I do, if
> the spell checker is reliable.
Your's is never correct. That'd be "your is".
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 Mar 06 2002 - 17:13:39 IST