Author: Robert Hyatt
Date: 09:07:25 08/26/05
Go up one level in this thread
On August 25, 2005 at 12:46:56, James Swafford wrote: >On August 25, 2005 at 12:34:20, Daniel Shawul wrote: > >>On August 24, 2005 at 23:22:50, Robert Hyatt wrote: >> >>>On August 24, 2005 at 22:23:11, James Swafford wrote: >>> >>>> >>>>I'm sure most parallel searchers use algorithms that allow splitting >>>>at arbitrary nodes in the tree. I'm curious how good (or bad!) >>>>it would be to simply spawn threads at the root to search an entire >>>>move. >>>> >>>>In other words, if I have 4 processors, then I would have 4 search >>>>threads running, each searching a different root move. >>> >>>Here's an assignment. Take your favorite program, and set up a middlegame >>>position. Let it start searching. When an iteration takes at least a minute, >>>pay careful attention, and watch your time when it starts the next iteration. >>>Watch carefully and notice when it pops up a score for the first move and goes >>>on to the next move. Then watch carefully until that iteration ends. >>> >>>Here is the question. >>> >>>You have three times. >>> >>>time(iteration start) >>>time(first score displayed) >>>time(iteration ended) >>> >>>look at the difference between the first two, and compare that to the difference >>>between the last two divided by #legal_moves-1... >>> >>>You will note that the first move takes _way_ more time than all the other moves >>>combined. now guess what happens when you search the second-best move first? >>>It takes as long as the first move. And then guess how long the first move >>>takes? Same time it took before. >>> >>>Bottom line is that this only gives you a very tiny speedup. Maybe 1.5X if you >> 1.5X ? i think that is too big. >> Last time i tried PVsplit , it only gave 1.2-1.3 speed up. >> If what you said is correct , i should probably try it. >>daniel > >Wouldn't your speedup be worse the better your move ordering is? > >-- >James No. If you can get a copy of my dissertation, I searched three types of trees. 1. worst-first ordering, which is the worst ordering you can do. And that turns the alpha/beta tree into a minimax tree. It is easy to get a good speedup there. In fact, you can get an almost perfect speedup, limited only by the hardware bottlenecks. 2. best-first ordering, which is the best ordering possible, that is every node you search gets a progressively lower score. This produces the optimal alpha/beta tree (minimal tree size) and again, it is pretty easy to get a perfect speedup here as well, you just split at the "right places" and you never have to worry about doing extra work, because you don't in perfect ordering. 3. normal chess trees. This is the "problem case" because it is the _real_ case we have to deal with. And there is no way to get perfect move ordering, obviously, so you are going to have parallel search overhead where you search extra nodes. The more processors you use, the more overhead there is. Plain and simple. If you go for eliminating this overhead, then you end up with processors sitting around with no work to do. And you lose performance either way... > > >> >>>are lucky. We used this in the very first parallel search we did. Because we >>>had no time to develop something better for that ACM event. It was not good. >>> >>>Even worse, what about positions where you just have one or two legal moves? :) >>> >>> >>>> >>>> Yes, I know that's incredibly simplistic. I'm just curious as to >>>>how the naive approach compares to something more complex. >>> >>>Poorly. _very_ poorly. :) >>> >>> >>>> >>>>Thanks, >>>>-- >>>>James
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.