Branching Factor of top engines

Discussion of anything and everything relating to chess playing software and machines.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
Laskos
Posts: 10182
Joined: Wed Jul 26, 2006 8:21 pm
Full name: Kai Laskos

Re: Branching factors of top engines.

Post by Laskos » Sun Nov 13, 2016 3:08 pm

Ajedrecista wrote: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.
I have computed them the same way as before for the engines I have:


Stockfish 8:
Ply:17 Positions: 30 Avg Nodes: 1512435 Branching = 1.56
Ply:18 Positions: 30 Avg Nodes: 2447825 Branching = 1.62
Ply:19 Positions: 30 Avg Nodes: 3595248 Branching = 1.47
Ply:20 Positions: 30 Avg Nodes: 5546744 Branching = 1.54
Ply:21 Positions: 30 Avg Nodes: 8360659 Branching = 1.51
Ply:22 Positions: 30 Avg Nodes:12264578 Branching = 1.47
Ply:23 Positions: 30 Avg Nodes:18146985 Branching = 1.48
Average EBF: 1.52

Komodo 10.2:
Ply:17 Positions: 30 Avg Nodes: 2890119 Branching = 1.48
Ply:18 Positions: 30 Avg Nodes: 4878235 Branching = 1.69
Ply:19 Positions: 30 Avg Nodes: 8182323 Branching = 1.68
Ply:20 Positions: 30 Avg Nodes:11910374 Branching = 1.46
Ply:21 Positions: 30 Avg Nodes:19221050 Branching = 1.61
Ply:22 Positions: 30 Avg Nodes:30120713 Branching = 1.57
Ply:23 Positions: 30 Avg Nodes:43578145 Branching = 1.45
Average EBF: 1.56

Shredder 13:
Ply:17 Positions: 30 Avg Nodes: 1682238 Branching = 1.44
Ply:18 Positions: 30 Avg Nodes: 2603995 Branching = 1.55
Ply:19 Positions: 30 Avg Nodes: 3714403 Branching = 1.43
Ply:20 Positions: 30 Avg Nodes: 6173892 Branching = 1.66
Ply:21 Positions: 30 Avg Nodes: 9233808 Branching = 1.50
Ply:22 Positions: 30 Avg Nodes:13925217 Branching = 1.51
Ply:23 Positions: 30 Avg Nodes:20753807 Branching = 1.49
Average EBF: 1.51

Andscacs 0.88:
Ply:16 Positions: 30 Avg Nodes: 2459230 Branching = 1.75
Ply:17 Positions: 30 Avg Nodes: 3535961 Branching = 1.44
Ply:18 Positions: 30 Avg Nodes: 5131742 Branching = 1.45
Ply:19 Positions: 30 Avg Nodes: 7992768 Branching = 1.56
Ply:20 Positions: 30 Avg Nodes:11477281 Branching = 1.44
Ply:21 Positions: 30 Avg Nodes:17255380 Branching = 1.50
Ply:22 Positions: 30 Avg Nodes:28672315 Branching = 1.66
Average EBF: 1.54


They all seem to clump around 1.53.

User avatar
Ajedrecista
Posts: 1417
Joined: Wed Jul 13, 2011 7:04 pm
Location: Madrid, Spain.
Contact:

Re: Branching factors of top engines.

Post by Ajedrecista » Sun Nov 13, 2016 4:16 pm

Hello:

Thank you very much. I did not expect any results in such a short time. It is also curious to see all those engines with very similar branching factors!

Regards from Spain.

Ajedrecista.

bob
Posts: 20887
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Branching factor of top engines.

Post by bob » Mon Nov 14, 2016 2:55 am

Sven Schüle wrote:
Werewolf wrote: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.
Your human OTB chess search tree is quite different. You are not searching to a depth that is anywhere near today's engine search depth, and you are not searching many lines very deep as well. Your human search tree probably has few lines going 10 or more plies deep while most lines are maybe just four, five, six plies deep. As a human you also need way more than a few hundred nanoseconds for each single position (not even counting the fact that human analysis is often not as systematic and logical as an engine's search algorithm).

Engine strength with an average BF of roughly 2 is based on deep search which is reached through speed and clever algorithms, but also on not "overlooking" a lot of important lines.

Sven
Also, EBF is NOT "BF". That is with an EBF of 1.8 you are NOT just searching 1.8 moves on average at every position. Most of that savings is not in searching fewer moves, but is from searching moves less deeply.

Sven
Posts: 3833
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Branching factor of top engines.

Post by Sven » Mon Nov 14, 2016 8:06 am

bob wrote:
Sven Schüle wrote:
Werewolf wrote: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.
Your human OTB chess search tree is quite different. You are not searching to a depth that is anywhere near today's engine search depth, and you are not searching many lines very deep as well. Your human search tree probably has few lines going 10 or more plies deep while most lines are maybe just four, five, six plies deep. As a human you also need way more than a few hundred nanoseconds for each single position (not even counting the fact that human analysis is often not as systematic and logical as an engine's search algorithm).

Engine strength with an average BF of roughly 2 is based on deep search which is reached through speed and clever algorithms, but also on not "overlooking" a lot of important lines.

Sven
Also, EBF is NOT "BF". That is with an EBF of 1.8 you are NOT just searching 1.8 moves on average at every position. Most of that savings is not in searching fewer moves, but is from searching moves less deeply.
Please note that you have replied to a post that is several years old.

Apart from that, you are right of course, back then I used "BF" where I obviously meant "EBF".

bob
Posts: 20887
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Branching factor of top engines.

Post by bob » Mon Nov 14, 2016 6:52 pm

Sven Schüle wrote:
bob wrote:
Sven Schüle wrote:
Werewolf wrote: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.
Your human OTB chess search tree is quite different. You are not searching to a depth that is anywhere near today's engine search depth, and you are not searching many lines very deep as well. Your human search tree probably has few lines going 10 or more plies deep while most lines are maybe just four, five, six plies deep. As a human you also need way more than a few hundred nanoseconds for each single position (not even counting the fact that human analysis is often not as systematic and logical as an engine's search algorithm).

Engine strength with an average BF of roughly 2 is based on deep search which is reached through speed and clever algorithms, but also on not "overlooking" a lot of important lines.

Sven
Also, EBF is NOT "BF". That is with an EBF of 1.8 you are NOT just searching 1.8 moves on average at every position. Most of that savings is not in searching fewer moves, but is from searching moves less deeply.
Please note that you have replied to a post that is several years old.

Apart from that, you are right of course, back then I used "BF" where I obviously meant "EBF".
I noticed the data. But I read it since it popped back up.

BTW we REALLY should come up with a better / more descriptive term for this than effective branching factor since it is somewhat vague and confusing.

Paloma
Posts: 916
Joined: Thu Dec 25, 2008 8:07 pm

Re: Branching factor of top engines.

Post by Paloma » Mon Nov 14, 2016 7:58 pm

What the f... is EBF ?
BF
is BranchingFactor, but EBF ??

User avatar
Laskos
Posts: 10182
Joined: Wed Jul 26, 2006 8:21 pm
Full name: Kai Laskos

Re: Branching factors of top engines.

Post by Laskos » Tue Nov 15, 2016 9:40 am

Ajedrecista wrote:Hello:

Thank you very much. I did not expect any results in such a short time. It is also curious to see all those engines with very similar branching factors!

Regards from Spain.

Ajedrecista.
Fire 5 seems to have an unusual behavior, from time to time it seems to count 2 plies as one:

Engine: Fire 5 x64 (1024 MB)
by Norman Schmidt
Ply: 0 Positions:150 Avg Nodes: 0 Branching = 0.00
Ply: 8 Positions:150 Avg Nodes: 85467 Branching = 0.00
Ply: 9 Positions:150 Avg Nodes: 166278 Branching = 1.95
Ply:10 Positions:150 Avg Nodes: 306407 Branching = 1.84
Ply:11 Positions:150 Avg Nodes: 936435 Branching = 3.06
Ply:12 Positions:150 Avg Nodes: 1565313 Branching = 1.67
Ply:13 Positions:150 Avg Nodes: 2573052 Branching = 1.64
Ply:14 Positions:150 Avg Nodes: 3957811 Branching = 1.54
Ply:15 Positions:150 Avg Nodes: 9387960 Branching = 2.37
Ply:16 Positions:150 Avg Nodes:15055031 Branching = 1.60
Ply:17 Positions:150 Avg Nodes:22429311 Branching = 1.49

Sven
Posts: 3833
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Branching factor of top engines.

Post by Sven » Tue Nov 15, 2016 12:16 pm

Paloma wrote:What the f... is EBF ?
BF
is BranchingFactor, but EBF ??
EBF = Effective Branching Factor (can be calculated from concrete samples of tree search performed by a concrete chess engine)

BF = Branching Factor (defined more or less through the rules of the game, independent from any search algorithms/concepts like alpha-beta, pruning, reductions etc.)

EBF of today's top engines is usually below 2.0, BF of chess is around 36-38 (?) in "average middlegame positions".

Paloma
Posts: 916
Joined: Thu Dec 25, 2008 8:07 pm

Re: Branching factor of top engines.

Post by Paloma » Tue Nov 15, 2016 4:35 pm

Thanks Sven

User avatar
Laskos
Posts: 10182
Joined: Wed Jul 26, 2006 8:21 pm
Full name: Kai Laskos

Re: Branching factors of top engines.

Post by Laskos » Mon Dec 05, 2016 7:44 pm

Laskos wrote:
Ajedrecista wrote: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.
I have computed them the same way as before for the engines I have:


Stockfish 8:
Ply:17 Positions: 30 Avg Nodes: 1512435 Branching = 1.56
Ply:18 Positions: 30 Avg Nodes: 2447825 Branching = 1.62
Ply:19 Positions: 30 Avg Nodes: 3595248 Branching = 1.47
Ply:20 Positions: 30 Avg Nodes: 5546744 Branching = 1.54
Ply:21 Positions: 30 Avg Nodes: 8360659 Branching = 1.51
Ply:22 Positions: 30 Avg Nodes:12264578 Branching = 1.47
Ply:23 Positions: 30 Avg Nodes:18146985 Branching = 1.48
Average EBF: 1.52

Komodo 10.2:
Ply:17 Positions: 30 Avg Nodes: 2890119 Branching = 1.48
Ply:18 Positions: 30 Avg Nodes: 4878235 Branching = 1.69
Ply:19 Positions: 30 Avg Nodes: 8182323 Branching = 1.68
Ply:20 Positions: 30 Avg Nodes:11910374 Branching = 1.46
Ply:21 Positions: 30 Avg Nodes:19221050 Branching = 1.61
Ply:22 Positions: 30 Avg Nodes:30120713 Branching = 1.57
Ply:23 Positions: 30 Avg Nodes:43578145 Branching = 1.45
Average EBF: 1.56

Shredder 13:
Ply:17 Positions: 30 Avg Nodes: 1682238 Branching = 1.44
Ply:18 Positions: 30 Avg Nodes: 2603995 Branching = 1.55
Ply:19 Positions: 30 Avg Nodes: 3714403 Branching = 1.43
Ply:20 Positions: 30 Avg Nodes: 6173892 Branching = 1.66
Ply:21 Positions: 30 Avg Nodes: 9233808 Branching = 1.50
Ply:22 Positions: 30 Avg Nodes:13925217 Branching = 1.51
Ply:23 Positions: 30 Avg Nodes:20753807 Branching = 1.49
Average EBF: 1.51

Andscacs 0.88:
Ply:16 Positions: 30 Avg Nodes: 2459230 Branching = 1.75
Ply:17 Positions: 30 Avg Nodes: 3535961 Branching = 1.44
Ply:18 Positions: 30 Avg Nodes: 5131742 Branching = 1.45
Ply:19 Positions: 30 Avg Nodes: 7992768 Branching = 1.56
Ply:20 Positions: 30 Avg Nodes:11477281 Branching = 1.44
Ply:21 Positions: 30 Avg Nodes:17255380 Branching = 1.50
Ply:22 Positions: 30 Avg Nodes:28672315 Branching = 1.66
Average EBF: 1.54


They all seem to clump around 1.53.
Houdini 5
Ply:16 Positions: 30 Avg Nodes: 4409139 Branching = 1.48
Ply:17 Positions: 30 Avg Nodes: 6740606 Branching = 1.53
Ply:18 Positions: 30 Avg Nodes:10977105 Branching = 1.63
Ply:19 Positions: 30 Avg Nodes:17375097 Branching = 1.58
Ply:20 Positions: 30 Avg Nodes:31714105 Branching = 1.83
Ply:21 Positions: 30 Avg Nodes:50846861 Branching = 1.60
Average EBF: 1.60

Post Reply