Parallel search gives different values than sequential

[nimble_ninja]

I am running into an issue when testing my parallel implementation of alpha-beta where the sequential search gives a somewhat different score than the parallel search. The scores don't vary by all that much, but they are different. As far as I can tell, this is because, when parallelizing the search algorithm, you must make different alpha-beta calls -- specifically, ones with wider windows, since, after searching the first child node, you split and provide the current alpha and beta values you have to multiple alpha-beta calls simultaneously, even though one of those calls could update the values for the other call to make it more narrow.

Is this inevitable, or is my implementation faulty?

[syzygy]

Is this inevitable, or is my implementation faulty?

Inevitable.

You can't avoid minimal variations in timing resulting in nodes being searched in different order, hash entries being filled in different order, etc.

Essentially, an efficient search will always try to make the best use of knowledge gained from the nodes it has searched before. With a parallel search, you will have searched a slightly different set of nodes before searching any particular node, so that knowledge will not be constant. So a window will be wider or narrower, a hash move will be missing, some killer moves will be sorted differently, etc.

The more "intelligent" your search (e.g. reductions based on alpha/beta values or move order), the bigger the deviations between runs will be.

[bob]

I am running into an issue when testing my parallel implementation of alpha-beta where the sequential search gives a somewhat different score than the parallel search. The scores don't vary by all that much, but they are different. As far as I can tell, this is because, when parallelizing the search algorithm, you must make different alpha-beta calls -- specifically, ones with wider windows, since, after searching the first child node, you split and provide the current alpha and beta values you have to multiple alpha-beta calls simultaneously, even though one of those calls could update the values for the other call to make it more narrow.

Is this inevitable, or is my implementation faulty?

differing scores and moves is pretty common. But when you say "ones with wider windows" what does that mean? My parallel search looks the same from that perspective whether it is serial or parallel. I still use PVS, parallel searches would always be "null-window" searches if you use something like YBW, since the first move has been searched already, and the rest are searched with null-window.