SF branching factor

[Jouni]

With latest version I notice, that branching factor is about 1,25. Really impressive value! Before NNUE it was about 1,4. It was about same with 1 and 6 cores up to 40 plies. So the number of threads don't effect bf?

[Werewolf]

Virtually certain it does on SF Cluster, don't know about the normal version.

Has this lower BF lowered tactical ability?

[syzygy]

With latest version I notice, that branching factor is about 1,25. Really impressive value! Before NNUE it was about 1,4. It was about same with 1 and 6 cores up to 40 plies. So the number of threads don't effect bf?

More search threads will take more nodes to reach the same depth, but this does not increase the branching factor.

Suppose 8 threads search the same tree completely independently. They will need exactly 8x as many nodes to reach the same depth. The multiplication factor going from depth N to depth N+1 will be the same as for one thread, since 8/8 = 1.

[Jouni]

I forgot to say I tested in opening position. But I remember to read, that with more threads SF does more elaborate search e.g. less reductions. True/false?

[chrisw]

I forgot to say I tested in opening position. But I remember to read, that with more threads SF does more elaborate search e.g. less reductions. True/false?

True. Thread count affects some search parameters.

[syzygy]

I forgot to say I tested in opening position. But I remember to read, that with more threads SF does more elaborate search e.g. less reductions. True/false?

I don't think SF really takes into account the number of search threads when deciding on reductions and pruning. However, I would have to check the code to be sure about this.

If you have many threads searching, different threads will make different pruning and reduction decisions (because they have different information available to them), but this should not influence the branching factor.

With many search threads, some threads will be able to skip parts of the tree because the hash table already has the outcome, but this also cannot change the branching factor (you can't have superlinear speedup).

[chrisw]

I forgot to say I tested in opening position. But I remember to read, that with more threads SF does more elaborate search e.g. less reductions. True/false?

I don't think SF really takes into account the number of search threads when deciding on reductions and pruning. However, I would have to check the code to be sure about this.

SF is increasing reductions with thread count. I guess the rationale is that you can reduce more because chances are that other threads in similar situation will order moves differently and thus a possible late “missed” move would be “unmissed” elsewhere, get a chance to fail high and enter the global hash for all threads to maybe discover.

• /// Search::init() is called at startup to initialize various lookup tables
  
  void Search::init() {
  
  for (int i = 1; i < MAX_MOVES; ++i)
  Reductions = int((20.26 + std::log(Threads.size()) / 2) * std::log(i));
  }

If you have many threads searching, different threads will make different pruning and reduction decisions (because they have different information available to them), but this should not influence the branching factor.

With many search threads, some threads will be able to skip parts of the tree because the hash table already has the outcome, but this also cannot change the branching factor (you can't have superlinear speedup).

[syzygy]

I forgot to say I tested in opening position. But I remember to read, that with more threads SF does more elaborate search e.g. less reductions. True/false?

I don't think SF really takes into account the number of search threads when deciding on reductions and pruning. However, I would have to check the code to be sure about this.

But it does:

Code: Select all

void Search::init() {

  for (int i = 1; i < MAX_MOVES; ++i)
      Reductions[i] = int((20.26 + std::log(Threads.size()) / 2) * std::log(i));
}

This leads to larger reductions as the number of search threads increases and therefore a smaller branching factor.

But this effect seems to be quite small. Even with 64 threads, 20.26 + log(64) is just 22.066. (This could be tested using a single thread by replacing Threads.size() with 64 in this line of search.cpp.)

edit: I now see that Chris already pointed this out

[syzygy]

SF is increasing reductions with thread count. I guess the rationale is that you can reduce more because chances are that other threads in similar situation will order moves differently and thus a possible late “missed” move would be “unmissed” elsewhere, get a chance to fail high and enter the global hash for all threads to maybe discover.

Yes, I now remember that that was the intuitive reasoning, and I guess it helped in tests.

But I do wonder. If this indeed decreaes the branching factor, then if you get deep enough into the search, you will spend much fewer total nodes on each depth than a single-threaded search. (And those total nodes are from multiple threads, so are worth less.)

Perhaps the increase in reductions should only be applied at lower depths.

[Jouni]

But how to explain this from pro deo forum!?

The test was run with the Stockfish bench mark command for Stockfish 15.

bench 1024 32 26 default depth nnue - Threadripper
bench 1024 8 26 default depth nnue - $1500 Laptop.


Theadripper Results.
NPS = 21,956,331

$1500 Laptop Results.
NPS = 13,699,948

The Threadripper is 1.6x faster in NPS. If your conclusion is the Threadripper is the faster computer running Stockfish. You would be dead wrong.

Solve time to complete the benchmark.

$1500 Laptop Total Solve Time Results.
Total Time (ms) 110,731

Threadripper Total Solve Time Results.
Total Time (ms) 199,936

The $1500 Laptop is 1.8x faster in completing the benchmark test.