Branching Factor of top engines

[hgm]

I wonder if these low EBFs are still optimal. The search walks the same tree time after time, adding only few nodes. It might be better to iterate the depth in steps of two, so that they don't repeat the same ting with almost no change.

[Uri Blass]

I wonder if these low EBFs are still optimal. The search walks the same tree time after time, adding only few nodes. It might be better to iterate the depth in steps of two, so that they don't repeat the same ting with almost no change.

I tried this idea in the past in the stockfish framework with no significant result and based on my memory other people also tried it later in stockfish with no significant results.

Here are results of my own test when I decided to jump only by 1 in the last iterations(when the time already get closer to the optimal time)

http://tests.stockfishchess.org/tests/v ... 01df50fada

another try later got clearly bad results

http://tests.stockfishchess.org/tests/v ... 1ede1208ae

Maybe it can work with different time management or maybe it can work when the search is modified so all the calls to qsearch are with the same side to move but the program can prune also earlier in the tree.

[yurikvelo]

More data with newer engines and higher D

http://pastebin.com/8mpdgPk8
Position from game http://tcec.chessdom.com/archive.php?se=7&st=4&ga=12
r2q1rk1/pb1n1ppp/1p2pn2/2b1P3/2B5/2N2N2/PP2QPPP/R1B2RK1 b - - 0 12
1. c4 e6 2. Nf3 d5 3. e3 Nf6 4. d4 Be7 5. Nc3 O-O 6. Bd3 dxc4 7. Bxc4 b6 8. O-O Bb7 9. Qe2 c5 10. dxc5 Bxc5 11. e4 Nbd7 12. e5

12. .. Nd5

KNodes - total kilo nodes searched
Delta - cost of last ply in nodes
Bf-Last - cost of last ply in kilo-nodes / cost of prev ply in kilonodes
Total Bf = nodes ^ 1/D

Code: Select all

 
Stockfish 171114 [Syzygy 6-men]
D               KNodes          Delta           Bf for last D   Total Bf
=========================================================================
19              4 916           1 365                           2,250
20              5 527           611             0,4             2,173
21              8 909           3 382           5,5             2,143
22              14 449          5 540           1,6             2,116
23              20 842          6 393           1,2             2,081
24              41 188          20 346          3,2             2,076
25              59 796          18 608          0,9             2,047
26              81 831          22 035          1,2             2,015
27              127 000         45 169          2,0             1,996
28              178 000         51 000          1,1             1,971
29              205 000         27 000          0,5             1,935
30              237 000         32 000          1,2             1,902
31              297 000         60 000          1,9             1,876
32              385 000         88 000          1,5             1,855
33              595 000         210 000         2,4             1,845
34              810 000         215 000         1,0             1,828
35              1 232 000       422 000         2,0             1,819
36              2 130 000       898 000         2,1             1,816
37              2 587 000       457 000         0,5             1,796
38              4 867 000       2 280 000       5,0             1,799
39              9 077 000       4 210 000       1,8             1,800
40              10 732 000      1 655 000       0,4             1,781
41              13 513 000      2 781 000       1,7             1,766
42              16 116 000      2 603 000       0,9             1,750
43              27 535 000      11 419 000      4,4             1,749
44              44 034 000      16 499 000      1,4             1,745
45              63 399 000      19 365 000      1,2             1,738
 
 
Houdini 4
D               KNodes          Delta           Bf for last D   Total Bf
=========================================================================
19              33 795          10 216                          2,490
20              47 934          14 139          1,4             2,421
21              113 000         65 066          4,6             2,418
22              169 000         56 000          0,9             2,366
23              297 000         128 000         2,3             2,336
24              527 000         230 000         1,8             2,309
25              753 000         226 000         1,0             2,265
26              1 096 000       343 000         1,5             2,227
27              1 672 000       576 000         1,7             2,196
28              3 598 000       1 926 000       3,3             2,194
29              9 191 000       5 593 000       2,9             2,206
30              14 791 000      5 600 000       1,0             2,183
31              17 725 000      2 934 000       0,5             2,141
32              38 874 000      21 149 000      7,2             2,143
33              82 320 000      43 446 000      2,1             2,142
34              129 505 000     47 185 000      1,1             2,122
 
Komodo 8 [Syzygy 6-men]
D               KNodes          Delta           Bf for last D   Total Bf
=========================================================================
19              30 099                                          2,475
20              40 455          10 356                          2,401
21              82 573          42 118          4,1             2,382
22              135 000         52 427          1,2             2,342
23              205 000         70 000          1,3             2,298
24              284 000         79 000          1,1             2,250
25              504 000         220 000         2,8             2,229
26              690 000         186 000         0,8             2,188
27              1 318 000       628 000         3,4             2,177
28              1 884 000       566 000         0,9             2,144
29              2 971 000       1 087 000       1,9             2,122
30              4 700 000       1 729 000       1,6             2,101
31              10 247 000      5 547 000       3,2             2,103
32              13 638 000      3 391 000       0,6             2,074
 
Gull 3
D               KNodes          Delta           Bf for last D   Total Bf
=========================================================================
19              131 000         39 750                          2,674
20              179 000         48 000          1,2             2,586
21              382 000         203 000         4,2             2,563
22              650 000         268 000         1,3             2,515
23              1 379 000       729 000         2,7             2,497
24              3 949 000       2 570 000       3,5             2,511
25              6 207 000       2 258 000       0,9             2,464
 
Deep Junior 12 UCI x64
D               KNodes          Delta           Bf for last D   Total Bf
=========================================================================
19              558 000                                         2,886
20              921 000         363 000                         2,807
 
Electro 1.2 (IPPOLIT derivative)
D               KNodes          Delta           Bf for last D   Total Bf
=========================================================================
19              38 565          10 980                          2,508
20              107 000         68 435          6,2             2,520
21              165 000         58 000          0,8             2,462
22              214 000         49 000          0,8             2,391
23              258 000         44 000          0,9             2,321
24              433 000         175 000         4,0             2,290
25              611 000         178 000         1,0             2,246
26              1 436 000       825 000         4,6             2,250
27              2 201 000       765 000         0,9             2,218
28              3 440 000       1 239 000       1,6             2,191
29              6 597 000       3 157 000       2,5             2,181

[hgm]

I tried this idea in the past in the stockfish framework with no significant result and based on my memory other people also tried it later in stockfish with no significant results.

Here are results of my own test when I decided to jump only by 1 in the last iterations(when the time already get closer to the optimal time)

http://tests.stockfishchess.org/tests/v ... 01df50fada

another try later got clearly bad results

http://tests.stockfishchess.org/tests/v ... 1ede1208ae

Maybe it can work with different time management or maybe it can work when the search is modified so all the calls to qsearch are with the same side to move but the program can prune also earlier in the tree.

Interesting. Of course the last few iterations take most of the time anyway, so the gain should come from skipping the fore-last iteration. I guess that to really exploit this idea the time management should decide after iteration N if it is likely there is time for an iteration N+2, and if there is, start it immediately. If there isn't, but N+1 could still likely be finished within the target time, it could do that instead.

[Eelco de Groot]

I don't know if there really is such a thing as an EBF that is too low. In the sense that a more intelligent program will skip more senseless moves. But if it is too low, it probably means that you have to search wider, not deeper. Skipping an iteration is an attempt to search deeper in one go, making the EBF even lower if you succeed to reach N+2 in less time than you would including N+1. So I don't think this is really a good idea, to skip the one before last iteration. A theory may be that there will be some moves that look better if you evaluate them from point of view of the opponent (in the leaf position), and some if you view them from own point of view. You never can get a bonus for side to move exactly right. So in one iteration some of the first kind of moves will be chosen, in the next iteration the other kind again. I think that is a good thing; as long as you don't have a perfect side to move bonus you should evaluate both kind of moves.

The assumption is that, on average, iterative deepening is efficient so why would skipping one iteration then help? On average, a well tuned strictly iterative deepening process should be better than the one skipping just some iterations. If one of the iterations is not earning its keep, does that not mean your search is no good. If every other iteration could be skipped, that would be another thing, but I don't think that is the case. Well, at least that idea seems not to have had the best results when tested.

[EvgeniyZh]

Are there tests on lstests engines (Komodo 9.2, Stockfish dev, Fire 4, Protector)?

[yurikvelo]

Are there tests on lstests engines (Komodo 9.2, Stockfish dev, Fire 4, Protector)?

I updated link http://pastebin.com/8mpdgPk8

with K9.2, K9.3 and SF-2016

[tttony]

Thanks but the link is wrong because is an old test not 2016

[yurikvelo]

Thanks but the link is wrong because is an old test not 2016

link was updated with 3 new runs (last 3 tables)

[Ajedrecista]

Hello:

I bump this topic because I think that there could be interest in seeing how branching factors have evolved recently, specially in the new 'top 4' of Stockfish 8, Houdini 5, Komodo 10.2 and Shredder 13. There was a nice activity on this topic in the past and it could be good to bump this thread from time to time, just to keep track of the advances.

I would not do those tests in a reliable way, so this is why I ask more experienced people to do them. I do not pretend to sound cheeky.

Regards from Spain.

Ajedrecista.