SMP and questions

[bob]

Why would you do that? You just found a move that raises beta, why not stop everyone and sic all threads on this specific move so that you can get a score back?

Or do you propose that in case of a move that is going to raise alpha in a PV node, you stop all other threads searching the same node and put them on the open window research of the move that failed high? In that case the aborted searches will have to be completely redone (but with an improved alpha).

I don't think this is what you meant, but I'll have a look at crafty to see how you are dealing with this case.

That's exactly what I do, in fact, but we are talking specifically about the root here, which is somewhat different from other nodes. There are race conditions here that don't happen anywhere eise. In any case, when a cpu fails high, any processor searching on that sub-tree or anywhere below that fail-high instantly gets aborted and the search is re-started. If I am at the root and get a fail-high, everybody gets aborted and the search re-starts with the YBW counter set to zero forcing all cpus to search the first root move together.

[bob]

Why would you do that? You just found a move that raises beta, why not stop everyone and sic all threads on this specific move so that you can get a score back?

Or do you propose that in case of a move that is going to raise alpha in a PV node, you stop all other threads searching the same node and put them on the open window research of the move that failed high? In that case the aborted searches will have to be completely redone (but with an improved alpha).

I don't think this is what you meant, but I'll have a look at crafty to see how you are dealing with this case.

From SearchParallel() I understand that the "PVS re-search code" (and all other invocations of Search()) simply uses the local alpha and beta without checking whether a parallel thread in the meantime has raised alpha.

You might be able to reduce the search overhead a bit by updating alpha to a value stored in a location shared by all threads searching the particular PV node, each time before you start a search or re-search of a move in a PV node.

I think it is pointless. almost 100% of the nodes are searched with V, V+1 for a window, and once can't raise alpha there without instantly getting a fail-high and aborting. Years ago I went through the trouble of raising alpha, but it was complicated, and it produced exactly zero measurable benefit so I canned it. I might have saved that version, I believe it was actually released and used for several versions...

[bob]

You might be able to reduce the search overhead a bit by updating alpha to a value stored in a location shared by all threads searching the particular PV node, each time before you start a search

Makes sense. I thought everyone is doing that. If not, they should.

With PVS how can this work? An alpha update is an instant fail-high first...

or re-search of a move in a PV node.

This is not so obvious. It might be better to retry the reduced search with updated alpha. If it still returns a score above the new alpha only then do a full depth re-search.

[Don]

You might be able to reduce the search overhead a bit by updating alpha to a value stored in a location shared by all threads searching the particular PV node, each time before you start a search

Makes sense. I thought everyone is doing that. If not, they should.

With PVS how can this work? An alpha update is an instant fail-high first...

or re-search of a move in a PV node.

This is not so obvious. It might be better to retry the reduced search with updated alpha. If it still returns a score above the new alpha only then do a full depth re-search.

You can do that at PV nodes however. Maybe that is what they are suggesting.

[syzygy]

You might be able to reduce the search overhead a bit by updating alpha to a value stored in a location shared by all threads searching the particular PV node, each time before you start a search

Makes sense. I thought everyone is doing that. If not, they should.

With PVS how can this work? An alpha update is an instant fail-high first...

or re-search of a move in a PV node.

This is not so obvious. It might be better to retry the reduced search with updated alpha. If it still returns a score above the new alpha only then do a full depth re-search.

You can do that at PV nodes however. Maybe that is what they are suggesting.

Yes, that is why I wrote "PV node" everywhere

Like Richard I would have expected all programs to do this, but at least crafty doesn't seem to do it. This is what I am talking about (and yes I am using PVS):

If you search a PV node with a single thread, then if one move returns a value for which alpha < value < beta (after a fail-high on a zero window search and a re-search if this was not the first move, because this is PVS), then alpha is increased to alpha and the remaining moves are searched with a zero window around the new alpha. And if one of those fails high, it is re-searched with a window (improved_alpha, beta) instead of (original_alpha, beta).

If you search a PV node with multiple threads, each thread searching a different subset of moves, then it obviously makes sense to do the same across threads. If one thread has searched a move that returned an improved alpha (after fail-high plus re-search), why not let the other threads search subsequent moves with the improved alpha. This is problematic for moves already being searched in parallel, but it is trivial for moves that still have to be searched. Simply update alpha from a shared memory location before recursively invoking search() from that PV split node.

This is not so obvious. It might be better to retry the reduced search with updated alpha. If it still returns a score above the new alpha only then do a full depth re-search.

Yes, exactly. This is what I proposed to Joona, except that I did it in relation to the re-search of the full depth fail high. So the complete idea is (at PV split nodes and doing LMR):

Code: Select all

do {
  do {
    alpha = sp->alpha;
    value = -search(..., -alpha-1, -alpha, depth - 1 - reduction);
  } while (value > alpha && value <= sp->alpha);

  if (value > alpha) {
    alpha = sp->alpha;
    value = -search(..., -alpha-1, -alpha, depth - 1);
  }
} while (value > alpha && value <= sp->alpha);

if (value > alpha && value < beta) {
  alpha = sp->alpha;
  value = -search(..., -beta, -alpha, depth - 1);
}

[Don]

You might be able to reduce the search overhead a bit by updating alpha to a value stored in a location shared by all threads searching the particular PV node, each time before you start a search

Makes sense. I thought everyone is doing that. If not, they should.

With PVS how can this work? An alpha update is an instant fail-high first...

or re-search of a move in a PV node.

This is not so obvious. It might be better to retry the reduced search with updated alpha. If it still returns a score above the new alpha only then do a full depth re-search.

You can do that at PV nodes however. Maybe that is what they are suggesting.

Yes, that is why I wrote "PV node" everywhere

Like Richard I would have expected all programs to do this, but at least crafty doesn't seem to do it. This is what I am talking about (and yes I am using PVS):

If you search a PV node with a single thread, then if one move returns a value for which alpha < value < beta (after a fail-high on a zero window search and a re-search if this was not the first move, because this is PVS), then alpha is increased to alpha and the remaining moves are searched with a zero window around the new alpha. And if one of those fails high, it is re-searched with a window (improved_alpha, beta) instead of (original_alpha, beta).

If you search a PV node with multiple threads, each thread searching a different subset of moves, then it obviously makes sense to do the same across threads. If one thread has searched a move that returned an improved alpha (after fail-high plus re-search), why not let the other threads search subsequent moves with the improved alpha. This is problematic for moves already being searched in parallel, but it is trivial for moves that still have to be searched. Simply update alpha from a shared memory location before recursively invoking search() from that PV split node.

I don't know if there is anything to be gained, but whenever alpha gets updated you could abort any nodes still being searched and simply restart them with the new alpha. The hash tables would preserve the state so that this is not like restarting from scratch. In fact due to the hash tables it might create a nearly instant cutoff.

This is not so obvious. It might be better to retry the reduced search with updated alpha. If it still returns a score above the new alpha only then do a full depth re-search.

Yes, exactly. This is what I proposed to Joona, except that I did it in relation to the re-search of the full depth fail high. So the complete idea is (at PV split nodes and doing LMR):

Code: Select all

do {
  do {
    alpha = sp->alpha;
    value = -search(..., -alpha-1, -alpha, depth - 1 - reduction);
  } while (value > alpha && value <= sp->alpha);

  if (value > alpha) {
    alpha = sp->alpha;
    value = -search(..., -alpha-1, -alpha, depth - 1);
  }
} while (value > alpha && value <= sp->alpha);

if (value > alpha && value < beta) {
  alpha = sp->alpha;
  value = -search(..., -beta, -alpha, depth - 1);
}

[syzygy]

I don't know if there is anything to be gained, but whenever alpha gets updated you could abort any nodes still being searched and simply restart them with the new alpha. The hash tables would preserve the state so that this is not like restarting from scratch. In fact due to the hash tables it might create a nearly instant cutoff.

I also have no idea whether this would gain something, but it certainly makes sense to try it.

Another idea is to propagate the new alpha to ongoing zero window searches on sibling moves. If those searches finally fail low, it would mean the real score is at most the new alpha, which is all we need to know. If one of those searches fails high, it would only mean the real score for that move is higher than the old alpha, so a re-search would be in order. This should gain a bit (over continuing with the old alpha), but it seems quite messy to implement. Simply aborting and restarting as you suggest is cleaner and might actually work better.

[diep]

You might be able to reduce the search overhead a bit by updating alpha to a value stored in a location shared by all threads searching the particular PV node, each time before you start a search

Makes sense. I thought everyone is doing that. If not, they should.

With PVS how can this work? An alpha update is an instant fail-high first...

This is correct. It's a fail high. So in Diep the AbortFailHigh() also aborts in this case all CPU's still searching in case of an alpha update.

Note that you are also correct in another posting saying that when you measured it didn't have a big impact to keep searching.

I couldn't measure much of a difference either, yet as it removes a worst case i'm doing it.

Might a different move give a cutoff as well, it first will need to get researched anyway prior to make it to mainline, so it cannot bite.
(except when you would be comparing it against the new alpha that just was improved, as it's above the old alpha, yet it's likely it's not above the new alpha).

Yet despite that i couldn't measure a difference some years ago, i'm still giving the abort there, as it is a clear case of an AbortFailHigh().

[bob]

You might be able to reduce the search overhead a bit by updating alpha to a value stored in a location shared by all threads searching the particular PV node, each time before you start a search

Makes sense. I thought everyone is doing that. If not, they should.

With PVS how can this work? An alpha update is an instant fail-high first...

or re-search of a move in a PV node.

This is not so obvious. It might be better to retry the reduced search with updated alpha. If it still returns a score above the new alpha only then do a full depth re-search.

You can do that at PV nodes however. Maybe that is what they are suggesting.

And one believes that doing this on just a very small number of nodes overall is going to have some big effect? It didn't when I tested it quite extensively... Prior to PVS, it would likely help measurably.

[syzygy]

And one believes that doing this on just a very small number of nodes overall is going to have some big effect?

That the number of PV nodes is very small is not a very good argument. All other nodes are searched starting from a PV node. With tighter bounds, those subtrees will be smaller.

I suppose you wouldn't be in favour of replacing "alpha" by "o_alpha" (original alpha) in each recursive invocation of Search() inside crafty's Search(), even though that only makes a difference in the very small number of nodes that are PV nodes. If updating alpha within a thread is a good idea, it should also be a good idea across threads.

That the number of PV nodes is very small means that updating alpha in those nodes is essentially free.

Anyway, it is just a suggestion. If it really makes no measurable difference, this all doesn't matter. It would surprise me if that is the case, but I have not tried to measure it myself (yet).