| View previous topic :: View next topic |
| Author |
Message |
Robert Purves
Joined: 15 Feb 2010
Posts: 155
Location: New Zealand
|
 Posted: Wed Nov 30, 2011 3:02 am Post subject: First steps with SMP |
  |
|
I have just implemented the first step of multi-threading my engine. It can search on the main thread and a parallel one simultaneously, each returning the same score and PV without crashing. Node count at any depth is exactly doubled by the extra thread. (All this is of course with the shared TT off).
Now I want to implement some form of YBW. Knowing little of the theory, I head for CPW and quickly find some fascinating pseudocode for the Jamboree algorithm:
http://chessprogramming.wikispaces.com/Jamboree
I understand the pseudocode in part, but am puzzled by the return values in two places (these are inside the parallel section):
| Code: |
s = -jamboree(c[i], -α - 1, -α);
if (s >= β) abort_and_return b;
...
s = -jamboree(c[i], -β, -α);
if (s >= β) abort_and_return b; |
I expected to see s returned, the same as in single-threaded search.
Is there a subtle issue with multithreading that makes b the correct return value, or is there a bug in the pseudocode?
Robert P. |
|
| Back to top |
|
 |
Kevin Hearn
Joined: 30 Dec 2010
Posts: 103
|
| Posted: Wed Nov 30, 2011 3:48 am Post subject: Re: First steps with SMP |
|
|
Just looks like the difference between fail soft and fail hard. Because you may have made different pruning decisions with a different search window when you fail you return the hard bound because you're not sure if you would've found something in the range (beta, score) in a future search when you look at branches that were subject to pruning with a lower window.
Shouldn't be anything special about multithreading that changes which way you decide to do things, both have their points. |
|
| Back to top |
|
|
Robert Purves
Joined: 15 Feb 2010
Posts: 155
Location: New Zealand
|
| Posted: Wed Nov 30, 2011 5:45 am Post subject: Re: First steps with SMP |
|
|
| Fail hard would be returning beta (β). But in the Jamboree pseudocode what is returned is a different variable b. It represents in some sense the best score so far, but is updated and used in a way that I cannot yet follow. |
|
| Back to top |
|
|
Kevin Hearn
Joined: 30 Dec 2010
Posts: 103
|
| Posted: Wed Nov 30, 2011 6:24 am Post subject: Re: First steps with SMP |
|
|
| my apologies. having now read the pseudocode, i'd agree it seems to be wrong. as written, it checks for fail high twice, and returns the best value found before the fail high which makes no sense at all. Overall the pseudocode appears to be a poorly written PVS missing any details pertaining to the actual parallelisation. |
|
| Back to top |
|
|
Robert Purves
Joined: 15 Feb 2010
Posts: 155
Location: New Zealand
|
| Posted: Wed Nov 30, 2011 12:28 pm Post subject: Re: First steps with SMP |
|
|
The CPW pseudocode is a corrupted version of the algorithm. The original:
http://supertech.csail.mit.edu/papers/startech.pdf
has abort_and_return s, which is much easier to believe and understand than abort_and_return b.
Also, one line is missing from the CPW code. |
|
| Back to top |
|
|
Gerd Isenberg
Joined: 08 Mar 2006
Posts: 1786
Location: Hattingen, Germany
|
| Posted: Wed Nov 30, 2011 12:46 pm Post subject: Re: First steps with SMP |
|
|
| micron wrote: |
The CPW pseudocode is a corrupted version of the algorithm. The original:
http://supertech.csail.mit.edu/papers/startech.pdf
has abort_and_return s, which is much easier to believe and understand than abort_and_return b.
Also, one line is missing from the CPW code. |
Thanks, corrected. How could that happen 
_________________
https://chessprogramming.wikispaces.com/ |
|
| Back to top |
|
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
