Branching Factor of top engines

[Laskos]

Shredder GUI has a nice feature that it shows BF of the engines analyzing an EPD file. I fed a neutral EPD file of 30 middlegame positions without solutions bm or am, to such depths that on average an engine analyzes for around one minute or a bit more each position on an i7 core. So BFs are shown for relevant plies, where engines spend from seconds to minutes.

I took three top engines, and an oldie, Shredder 6PB from 2002. If BF is the branching factor, then 1/Log(BF) is proportional to the depth the engine searches.

Houdini 3
Ply:15 Positions: 30 Avg Nodes: 4474464 Branching = 1.54
Ply:16 Positions: 30 Avg Nodes: 9993292 Branching = 2.23
Ply:17 Positions: 30 Avg Nodes:16583899 Branching = 1.66
Ply:18 Positions: 30 Avg Nodes:29529725 Branching = 1.78
Ply:19 Positions: 30 Avg Nodes:59452946 Branching = 2.01
Ply:20 Positions: 30 Avg Nodes:100502642 Branching = 1.69
Ply:21 Positions: 30 Avg Nodes:226412605 Branching = 2.25
Average BF: 1.86
1/Log(BF)=1.61


Stockfish 3
Ply:17 Positions: 30 Avg Nodes: 5738272 Branching = 1.51
Ply:18 Positions: 30 Avg Nodes: 9495564 Branching = 1.65
Ply:19 Positions: 30 Avg Nodes:14927319 Branching = 1.57
Ply:20 Positions: 30 Avg Nodes:25380846 Branching = 1.70
Ply:21 Positions: 30 Avg Nodes:37913346 Branching = 1.49
Ply:22 Positions: 30 Avg Nodes:58287426 Branching = 1.54
Ply:23 Positions: 30 Avg Nodes:105041456 Branching = 1.80
Average BF: 1.61
1/Log(BF)=2.10


Komodo 5 CCT
Ply:15 Positions: 30 Avg Nodes: 3132997 Branching = 1.74
Ply:16 Positions: 30 Avg Nodes: 5471869 Branching = 1.75
Ply:17 Positions: 30 Avg Nodes: 9833793 Branching = 1.80
Ply:18 Positions: 30 Avg Nodes:16946370 Branching = 1.72
Ply:19 Positions: 30 Avg Nodes:28120847 Branching = 1.66
Ply:20 Positions: 30 Avg Nodes:57150190 Branching = 2.03
Ply:21 Positions: 30 Avg Nodes:93519346 Branching = 1.64
Average BF: 1.76
1/Log(BF)=1.77


Shredder 6
Ply: 8 Positions: 30 Avg Nodes: 515591 Branching = 2.68
Ply: 9 Positions: 30 Avg Nodes: 1347856 Branching = 2.61
Ply:10 Positions: 30 Avg Nodes: 3997429 Branching = 2.97
Ply:11 Positions: 30 Avg Nodes: 8540293 Branching = 2.14
Ply:12 Positions: 30 Avg Nodes:19868716 Branching = 2.33
Ply:13 Positions: 30 Avg Nodes:51275681 Branching = 2.58
Ply:14 Positions: 30 Avg Nodes:119957110 Branching = 2.34
Average BF: 2.51
1/Log(BF)=1.09

[Ajedrecista]

Hello Kai:

Shredder GUI has a nice feature that it shows BF of the engines analyzing an EPD file. I fed a neutral EPD file of 30 middlegame positions without solutions bm or am, to such depths that on average an engine analyzes for around one minute or a bit more each position on an i7 core. So BFs are shown for relevant plies, where engines spend from seconds to minutes.

I took three top engines, and an oldie, Shredder 6PB from 2002. If BF is the branching factor, then 1/Log(BF) is proportional to the depth the engine searches.

Houdini 3
Ply:15 Positions: 30 Avg Nodes: 4474464 Branching = 1.54
Ply:16 Positions: 30 Avg Nodes: 9993292 Branching = 2.23
Ply:17 Positions: 30 Avg Nodes:16583899 Branching = 1.66
Ply:18 Positions: 30 Avg Nodes:29529725 Branching = 1.78
Ply:19 Positions: 30 Avg Nodes:59452946 Branching = 2.01
Ply:20 Positions: 30 Avg Nodes:100502642 Branching = 1.69
Ply:21 Positions: 30 Avg Nodes:226412605 Branching = 2.25
Average BF: 1.86
1/Log(BF)=1.61


Stockfish 3
Ply:17 Positions: 30 Avg Nodes: 5738272 Branching = 1.51
Ply:18 Positions: 30 Avg Nodes: 9495564 Branching = 1.65
Ply:19 Positions: 30 Avg Nodes:14927319 Branching = 1.57
Ply:20 Positions: 30 Avg Nodes:25380846 Branching = 1.70
Ply:21 Positions: 30 Avg Nodes:37913346 Branching = 1.49
Ply:22 Positions: 30 Avg Nodes:58287426 Branching = 1.54
Ply:23 Positions: 30 Avg Nodes:105041456 Branching = 1.80
Average BF: 1.61
1/Log(BF)=2.10


Komodo 5 CCT
Ply:15 Positions: 30 Avg Nodes: 3132997 Branching = 1.74
Ply:16 Positions: 30 Avg Nodes: 5471869 Branching = 1.75
Ply:17 Positions: 30 Avg Nodes: 9833793 Branching = 1.80
Ply:18 Positions: 30 Avg Nodes:16946370 Branching = 1.72
Ply:19 Positions: 30 Avg Nodes:28120847 Branching = 1.66
Ply:20 Positions: 30 Avg Nodes:57150190 Branching = 2.03
Ply:21 Positions: 30 Avg Nodes:93519346 Branching = 1.64
Average BF: 1.76
1/Log(BF)=1.77


Shredder 6
Ply: 8 Positions: 30 Avg Nodes: 515591 Branching = 2.68
Ply: 9 Positions: 30 Avg Nodes: 1347856 Branching = 2.61
Ply:10 Positions: 30 Avg Nodes: 3997429 Branching = 2.97
Ply:11 Positions: 30 Avg Nodes: 8540293 Branching = 2.14
Ply:12 Positions: 30 Avg Nodes:19868716 Branching = 2.33
Ply:13 Positions: 30 Avg Nodes:51275681 Branching = 2.58
Ply:14 Positions: 30 Avg Nodes:119957110 Branching = 2.34
Average BF: 2.51
1/Log(BF)=1.09

Thank you very much! Indeed I thought that BF(SF 3) < BF(Houdini 3) < BF(Komodo CCT) < BF(Shredder 6) before your experiment, but it was easy to be right. Other thing is quantify my guess, which is more difficult... but you have done it!

It will be interesting if you can expand your experiment to Critter 1.6a, Rybka 4.1 (top engines) and other oldie: Zappa Mexico II. These are random choices, but you could do a list with more engines (or even with an EPD file that contains more positions, just to reduce the variance of the experiment) if you have spare time. Thanks again.

Regards from Spain.

Ajedrecista.

[IWB]

Interesting,

I just run a little test with Houdini on just one core and different hash sizes and the time to depth is differrent with changing hash. So I assume that the BF is different there as well ...

Bye
Ingo

Shredder GUI has a nice feature that it shows BF of the engines analyzing an EPD file. I fed a neutral EPD file of 30 middlegame positions without solutions bm or am, to such depths that on average an engine analyzes for around one minute or a bit more each position on an i7 core. So BFs are shown for relevant plies, where engines spend from seconds to minutes.

I took three top engines, and an oldie, Shredder 6PB from 2002. If BF is the branching factor, then 1/Log(BF) is proportional to the depth the engine searches.

Houdini 3
Ply:15 Positions: 30 Avg Nodes: 4474464 Branching = 1.54
Ply:16 Positions: 30 Avg Nodes: 9993292 Branching = 2.23
Ply:17 Positions: 30 Avg Nodes:16583899 Branching = 1.66
Ply:18 Positions: 30 Avg Nodes:29529725 Branching = 1.78
Ply:19 Positions: 30 Avg Nodes:59452946 Branching = 2.01
Ply:20 Positions: 30 Avg Nodes:100502642 Branching = 1.69
Ply:21 Positions: 30 Avg Nodes:226412605 Branching = 2.25
Average BF: 1.86
1/Log(BF)=1.61


Stockfish 3
Ply:17 Positions: 30 Avg Nodes: 5738272 Branching = 1.51
Ply:18 Positions: 30 Avg Nodes: 9495564 Branching = 1.65
Ply:19 Positions: 30 Avg Nodes:14927319 Branching = 1.57
Ply:20 Positions: 30 Avg Nodes:25380846 Branching = 1.70
Ply:21 Positions: 30 Avg Nodes:37913346 Branching = 1.49
Ply:22 Positions: 30 Avg Nodes:58287426 Branching = 1.54
Ply:23 Positions: 30 Avg Nodes:105041456 Branching = 1.80
Average BF: 1.61
1/Log(BF)=2.10


Komodo 5 CCT
Ply:15 Positions: 30 Avg Nodes: 3132997 Branching = 1.74
Ply:16 Positions: 30 Avg Nodes: 5471869 Branching = 1.75
Ply:17 Positions: 30 Avg Nodes: 9833793 Branching = 1.80
Ply:18 Positions: 30 Avg Nodes:16946370 Branching = 1.72
Ply:19 Positions: 30 Avg Nodes:28120847 Branching = 1.66
Ply:20 Positions: 30 Avg Nodes:57150190 Branching = 2.03
Ply:21 Positions: 30 Avg Nodes:93519346 Branching = 1.64
Average BF: 1.76
1/Log(BF)=1.77


Shredder 6
Ply: 8 Positions: 30 Avg Nodes: 515591 Branching = 2.68
Ply: 9 Positions: 30 Avg Nodes: 1347856 Branching = 2.61
Ply:10 Positions: 30 Avg Nodes: 3997429 Branching = 2.97
Ply:11 Positions: 30 Avg Nodes: 8540293 Branching = 2.14
Ply:12 Positions: 30 Avg Nodes:19868716 Branching = 2.33
Ply:13 Positions: 30 Avg Nodes:51275681 Branching = 2.58
Ply:14 Positions: 30 Avg Nodes:119957110 Branching = 2.34
Average BF: 2.51
1/Log(BF)=1.09

[Laskos]

Thank you very much! Indeed I thought that BF(SF 3) < BF(Houdini 3) < BF(Komodo CCT) < BF(Shredder 6) before your experiment, but it was easy to be right. Other thing is quantify my guess, which is more difficult... but you have done it!

It will be interesting if you can expand your experiment to Critter 1.6a, Rybka 4.1 (top engines) and other oldie: Zappa Mexico II. These are random choices, but you could do a list with more engines (or even with an EPD file that contains more positions, just to reduce the variance of the experiment) if you have spare time. Thanks again.

Regards from Spain.

Ajedrecista.

Actually BF(Komodo CCT)<BF(Houdini 3), which is a bit surprising. I tested another three engines, and the results are as expected:

Rybka 4.1
Ply:11 Positions: 30 Avg Nodes: 265429 Branching = 2.14
Ply:12 Positions: 30 Avg Nodes: 591177 Branching = 2.23
Ply:13 Positions: 30 Avg Nodes: 1041122 Branching = 1.76
Ply:14 Positions: 30 Avg Nodes: 2323306 Branching = 2.23
Ply:15 Positions: 30 Avg Nodes: 4232348 Branching = 1.82
Ply:16 Positions: 30 Avg Nodes: 7253956 Branching = 1.71
Ply:17 Positions: 30 Avg Nodes:13145490 Branching = 1.81
Average BF: 1.95
1/Log(BF)=1.50


Zappa Mexico II
Ply: 9 Positions: 30 Avg Nodes: 1037902 Branching = 1.90
Ply:10 Positions: 30 Avg Nodes: 2265595 Branching = 2.18
Ply:11 Positions: 30 Avg Nodes: 4888491 Branching = 2.16
Ply:12 Positions: 30 Avg Nodes:10434379 Branching = 2.13
Ply:13 Positions: 30 Avg Nodes:25248750 Branching = 2.42
Ply:14 Positions: 30 Avg Nodes:54789787 Branching = 2.17
Average BF: 2.15
1/Log(BF)=1.30


Fruit 2.1
Ply: 8 Positions: 30 Avg Nodes: 660395 Branching = 2.80
Ply: 9 Positions: 30 Avg Nodes: 1506482 Branching = 2.28
Ply:10 Positions: 30 Avg Nodes: 3549530 Branching = 2.36
Ply:11 Positions: 30 Avg Nodes: 8168693 Branching = 2.30
Ply:12 Positions: 30 Avg Nodes:20698649 Branching = 2.53
Ply:13 Positions: 30 Avg Nodes:45804511 Branching = 2.21
Ply:14 Positions: 30 Avg Nodes:120643226 Branching = 2.63
Average BF: 2.44
1/Log(BF)=1.12


EBF is almost chronological: SF<Komodo CCT<Houdini 3<Rybka 4<Zappa Mexico<Fruit 2.1<Shredder 6.

Ingo: hash used is 512MB, it fills in half to one-quarter of the time allotted, as it usually happens in LTC games.

The rule of thumb for top engines seems roughly taking the square root of branching factor every 15 years or so. So, expect a BF of 1.3 or so in 2028 for a top engine.

[Werewolf]

I just don't understand how these engines can play a strong game with such a low BF.
'5' I understand.
'3' is plausible, if somewhat ambitious.
But 1-2 is in incredible.

That's as good as my own human OTB chess.

[Ajedrecista]

Hello again:

Actually BF(Komodo CCT)<BF(Houdini 3), which is a bit surprising. I tested another three engines, and the results are as expected:

Sure. I got confused by BF and 1/[ln(BF)]. I also did not expect BF(Komodo CCT) < BF(Houdini 3).

Rybka 4.1
Ply:11 Positions: 30 Avg Nodes: 265429 Branching = 2.14
Ply:12 Positions: 30 Avg Nodes: 591177 Branching = 2.23
Ply:13 Positions: 30 Avg Nodes: 1041122 Branching = 1.76
Ply:14 Positions: 30 Avg Nodes: 2323306 Branching = 2.23
Ply:15 Positions: 30 Avg Nodes: 4232348 Branching = 1.82
Ply:16 Positions: 30 Avg Nodes: 7253956 Branching = 1.71
Ply:17 Positions: 30 Avg Nodes:13145490 Branching = 1.81
Average BF: 1.95
1/Log(BF)=1.50


Zappa Mexico II
Ply: 9 Positions: 30 Avg Nodes: 1037902 Branching = 1.90
Ply:10 Positions: 30 Avg Nodes: 2265595 Branching = 2.18
Ply:11 Positions: 30 Avg Nodes: 4888491 Branching = 2.16
Ply:12 Positions: 30 Avg Nodes:10434379 Branching = 2.13
Ply:13 Positions: 30 Avg Nodes:25248750 Branching = 2.42
Ply:14 Positions: 30 Avg Nodes:54789787 Branching = 2.17
Average BF: 2.15
1/Log(BF)=1.30


Fruit 2.1
Ply: 8 Positions: 30 Avg Nodes: 660395 Branching = 2.80
Ply: 9 Positions: 30 Avg Nodes: 1506482 Branching = 2.28
Ply:10 Positions: 30 Avg Nodes: 3549530 Branching = 2.36
Ply:11 Positions: 30 Avg Nodes: 8168693 Branching = 2.30
Ply:12 Positions: 30 Avg Nodes:20698649 Branching = 2.53
Ply:13 Positions: 30 Avg Nodes:45804511 Branching = 2.21
Ply:14 Positions: 30 Avg Nodes:120643226 Branching = 2.63
Average BF: 2.44
1/Log(BF)=1.12


EBF is almost chronological: SF<Komodo CCT<Houdini 3<Rybka 4<Zappa Mexico<Fruit 2.1<Shredder 6.

Ingo: hash used is 512MB, it fills in half to one-quarter of the time allotted, as it usually happens in LTC games.

The rule of thumb for top engines seems roughly taking the square root of branching factor every 15 years or so. So, expect a BF of 1.3 or so in 2028 for a top engine.

Thanks again for your time. The decreasing trend of BF seems logical to me due to improved/more aggressive pruning algorithms in search (I hope I am right because I do not know how to write a chess engine!).

Regards from Spain.

Ajedrecista.

[lucasart]

Shredder GUI has a nice feature that it shows BF of the engines analyzing an EPD file.

How does Shredder determine the average branching factor? As part of the UCI protocol engines communicate their node count, and depth, but that's not enough IMO. The problem I see is that:
* the depth is the nominal depth of the search (excluding QS)
* the node count is total, including QS nodes

So in reality, the branching factors are even lower!

[IWB]

Ingo: hash used is 512MB, it fills in half to one-quarter of the time allotted, as it usually happens in LTC games.

Yes, that is a reasonable Hash size, no doubt about that. I just wanted to point out that with a different Hash size the BF might be different.

Have a look here:


This is H3 with just one thread. Starting position. The front green line is the depth, the 64 to 8192 is the hash size and the numbers are the time to depth in seconds. Between the blue and the red I got the "hash full (100%) message. The green line below is the ranking in average time to depth. I havent recorded the number but recognised that (eg) with 64 MB the depth 27 is reached with less absolut nodes than with 8192MB Hash. This means that depending of the hash size the branching factor varies ...

ASnd this is just H3, 1 Thread. More threads and more engines and it gets more difficult

Anyhow, interesting calculation you have done.

BYe
Ingo

[Don]

I don't think it means anything though. But it is interesting. We know that SF had a very low BF and there are some simple mods we could do to Komodo to make the BF lower while having very little impact on the ELO.

We have long suspected this could be related to scalability but we are far from proving that. However SF is one of the more scalable programs and it could be related to the low BF. I would take a huge amount of CPU power to do the kind of experiments we would like to do to really understand scalability.

Thank you very much! Indeed I thought that BF(SF 3) < BF(Houdini 3) < BF(Komodo CCT) < BF(Shredder 6) before your experiment, but it was easy to be right. Other thing is quantify my guess, which is more difficult... but you have done it!

It will be interesting if you can expand your experiment to Critter 1.6a, Rybka 4.1 (top engines) and other oldie: Zappa Mexico II. These are random choices, but you could do a list with more engines (or even with an EPD file that contains more positions, just to reduce the variance of the experiment) if you have spare time. Thanks again.

Regards from Spain.

Ajedrecista.

Actually BF(Komodo CCT)<BF(Houdini 3), which is a bit surprising. I tested another three engines, and the results are as expected:

Rybka 4.1
Ply:11 Positions: 30 Avg Nodes: 265429 Branching = 2.14
Ply:12 Positions: 30 Avg Nodes: 591177 Branching = 2.23
Ply:13 Positions: 30 Avg Nodes: 1041122 Branching = 1.76
Ply:14 Positions: 30 Avg Nodes: 2323306 Branching = 2.23
Ply:15 Positions: 30 Avg Nodes: 4232348 Branching = 1.82
Ply:16 Positions: 30 Avg Nodes: 7253956 Branching = 1.71
Ply:17 Positions: 30 Avg Nodes:13145490 Branching = 1.81
Average BF: 1.95
1/Log(BF)=1.50


Zappa Mexico II
Ply: 9 Positions: 30 Avg Nodes: 1037902 Branching = 1.90
Ply:10 Positions: 30 Avg Nodes: 2265595 Branching = 2.18
Ply:11 Positions: 30 Avg Nodes: 4888491 Branching = 2.16
Ply:12 Positions: 30 Avg Nodes:10434379 Branching = 2.13
Ply:13 Positions: 30 Avg Nodes:25248750 Branching = 2.42
Ply:14 Positions: 30 Avg Nodes:54789787 Branching = 2.17
Average BF: 2.15
1/Log(BF)=1.30


Fruit 2.1
Ply: 8 Positions: 30 Avg Nodes: 660395 Branching = 2.80
Ply: 9 Positions: 30 Avg Nodes: 1506482 Branching = 2.28
Ply:10 Positions: 30 Avg Nodes: 3549530 Branching = 2.36
Ply:11 Positions: 30 Avg Nodes: 8168693 Branching = 2.30
Ply:12 Positions: 30 Avg Nodes:20698649 Branching = 2.53
Ply:13 Positions: 30 Avg Nodes:45804511 Branching = 2.21
Ply:14 Positions: 30 Avg Nodes:120643226 Branching = 2.63
Average BF: 2.44
1/Log(BF)=1.12


EBF is almost chronological: SF<Komodo CCT<Houdini 3<Rybka 4<Zappa Mexico<Fruit 2.1<Shredder 6.

Ingo: hash used is 512MB, it fills in half to one-quarter of the time allotted, as it usually happens in LTC games.

The rule of thumb for top engines seems roughly taking the square root of branching factor every 15 years or so. So, expect a BF of 1.3 or so in 2028 for a top engine.

[Daniel Shawul]

Why should qsearch nodes be excluded from EBF calculations or are you suggesting the depth be taken to MAX_PLY if one check-evade route reaches there? In literature EBF is defined as the equivalent depth a uniform tree would have so that it can contain all the nodes explored by any search methodology (alpha-beta, SSS, A* etc).

Code: Select all

    EBF = (Total nodes searched) ^ (1/d)

The one we know as sqrt(d) for alpha-beta is the limit of the above at Infinite depth.