First steps with SMP

[micron]

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: Select all

      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.

[kbhearn]

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.

[micron]

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.

[kbhearn]

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.

[micron]

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.

[Gerd Isenberg]

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