Branching Factor of top engines

[lucasart]

It doesn't matter how long you search one variation (be selective) about it. Your nominal depth is the one you started out the search with d. So with this method you are able to compare many different algorithms which if you conjure up some other you can't. Your example is for humans who don't use IID, but if you assume you started out to search 5 plies but went on extending that one line to 10 then your EBF is

Code: Select all

EBF = (10+5+5)^(1/5)

so it doesn't matter how long you extend one line.

There are two ways to look at this example:
* either you consider that d=10, and aggressive forward pruning methods were used. In computer terms, my brain used move count pruning after 3 moves at the root, and after 1 move at every node visited by the search here. It also used a 1 ply reduction at each node of the 5-ply variation, which are nominally 10 plies, but end up being 5 because of reduction piling up in these two branches.
* or you consider that I did a 5 ply search, and extended just one variation by 5 plies.

In both cases, the formula gives very different results.

The same reasoning could be applied to the qsearch. If the max QS depth is 10 (ie. 10 plies starting from a leaf of the search), we can either consider that depth=d+10, or that the real depth is still d, and these are extensions to be discarded.

I think LMR exposes a way to abuse this (overly basic) definition of EBF. So people go around and parade with their low EBF, and how it has improved frol 5-6 to 1.7 over the years. That's a apple to pear comparison, IMO.

In the past engines used lots of extensions. Nowadays they use non reductions, which is a relative extension...

[Daniel Shawul]

Hey you can use d=100 and announce it and you still would be able to compare algorithms! The point you miss is you are defining your d based on your algorithm's result ,which is wrong, longest line. Atleast average depth makes a bit more sense as that would be equivalent to the root depth d. Algorithm complexity is measured for the same amount of work. Take searching for instance. You know what the end result is (perfectly sorted), so you compare how many operations quicksort and bubble sort take. The same for chess, i.e your search depth d represents the work, then you go about determining how much nodes each algorithm takes. e.g. Minimax b^d, and alpha-beta b&(d/2). Just because the alpha-beta algorithm also decided to extends some lines doesn't change this definition. I think what you need is time to digest this and offer opinions afterwards. Other wise you become like the guy you so clearly abhore

[Mike S.]

Thanks! - The following results are from:

Intel i5-3210M dualcore CPU, 2.5...2.9 GHz, 4 threads, 512 MB hash

I used 24 typical test positions where I did remove the solutions from.

Code: Select all

Stockfish 3:

  Ply:13   Positions: 24   Avg Nodes:  534983   Branching = 1.53
  Ply:14   Positions: 24   Avg Nodes:  890472   Branching = 1.66
  Ply:15   Positions: 24   Avg Nodes: 1408187   Branching = 1.58
  Ply:16   Positions: 24   Avg Nodes: 2542482   Branching = 1.81
  Ply:17   Positions: 24   Avg Nodes: 3645244   Branching = 1.43
  Ply:18   Positions: 24   Avg Nodes: 5995531   Branching = 1.64
  Ply:19   Positions: 24   Avg Nodes: 9162520   Branching = 1.53
  
  Ø 13-19: Branching = 1.59
  -------------------------

Houdini 1.5a2d:

  Ply:13   Positions: 24   Avg Nodes: 2318969   Branching = 2.20
  Ply:14   Positions: 24   Avg Nodes: 3533411   Branching = 1.52
  Ply:15   Positions: 24   Avg Nodes: 6277197   Branching = 1.78
  Ply:16   Positions: 24   Avg Nodes:10923726   Branching = 1.74
  Ply:17   Positions: 24   Avg Nodes:22735039   Branching = 2.08
  Ply:18   Positions: 24   Avg Nodes:37262728   Branching = 1.64
  Ply:19   Positions: 24   Avg Nodes:92113147   Branching = 2.47
  
  Ø 13-19: Branching = 1.89
  -------------------------

Fire 2.2 SK94z:

  Ply:13   Positions: 24   Avg Nodes: 1457645   Branching = 2.13
  Ply:14   Positions: 24   Avg Nodes: 3025788   Branching = 2.08
  Ply:15   Positions: 24   Avg Nodes: 5554708   Branching = 1.84
  Ply:16   Positions: 24   Avg Nodes: 9231240   Branching = 1.66
  Ply:17   Positions: 24   Avg Nodes:17663670   Branching = 1.91
  Ply:18   Positions: 24   Avg Nodes:33728006   Branching = 1.91
  Ply:19   Positions: 24   Avg Nodes:69387505   Branching = 2.06
  
  Ø 13-19: Branching = 1.94
  -------------------------

Critter 1.6a:

  Ply:11   Positions: 23   Avg Nodes:  423230   Branching = 2.07
  Ply:12   Positions: 24   Avg Nodes: 1034393   Branching = 2.44
  Ply:13   Positions: 24   Avg Nodes: 2028984   Branching = 1.96
  Ply:14   Positions: 24   Avg Nodes: 4671234   Branching = 2.30
  Ply:15   Positions: 24   Avg Nodes: 8611944   Branching = 1.84
  Ply:16   Positions: 24   Avg Nodes:13578797   Branching = 1.58
  Ply:17   Positions: 24   Avg Nodes:30989496   Branching = 2.28
  
  Ø 11-17: Branching = 2.05
  -------------------------

[Uri Blass]

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.

Still, the BF of top engines went from 6 in 1980es to 3 in late 1990es and to 1.6-1.8 nowadays. It seems to be a rule of thumb that it goes square root every 15 years or so (so the depth is doubled every 15 years on same hardware). And the aggressive pruning doesn't miss much on the way, it's very smartly done. The progress in search is real, it's not only hardware related as some imply about engines' progress.

Yes, a couple of years ago Bob Hyatt and I had a big discussion on this, he was saying it was mostly hardware and I was saying that software improved as much as hardware if not more.

The pruning definitely takes its toll but it's amazing how little it misses. I think most of the progress I have made with Komodo in the last 2 versions had to do with making it prune and reduce safer without hurting the BF - and in fact I think it now prunes more aggressively at the same time.

I agree that software improved not less than hardware but
I do not think that the pruning miss so little(inspite of the fact that it is clearly productive to playing strength).

You probably do not need a lot of plies to have depth d(with no pruning) wins against depth d+1 with the pruning that you have
and I guess that depth 9 with no pruning is going to win against depth 10 with all the pruning that you have.

It may be interesting to have some rating list of different small depths when you test every depth with 3 options:
1)normal
2)no pruning but extensions are still the same.
3)no pruning and no extensions(qsearch is the same and I do not consider it as extension because programs do not know to evaluate positions that are not quiet positions).

[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

Thanks for this picture. As you see, the differences are about 20-30% for different hash sizes to depth 27. That means (1.3)^(1/27)~1.01 scaling variation of the BF. A difference of 0.01 is smaller than my statistical error.

First of all and gain, you assumtion is a very reasonable and practicable one for a longer game.

I did not understand where you get the 30% from. At d27 between 8GB and 2GB you have 86%. The line 17 is the average over all depth and there you see about 60 % between the fastest and the slowest one. Maybe there is a particular depth where the difference might be bigger than 89% but I am too lazy to search for that.
Anyhow, what is even more puzzling is, that depending on the hash size you get different node counts to reach a particular depth (I recognized this but did not record it as it was not imporant for the initial question I made the chart for, bad luck). This will influence the BF maybe more. If or how much of it is significant is a different question ...

And gain, your assumtion are very reasonable for practical play. I agree completly with that.

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.

Still, the BF of top engines went from 6 in 1980es to 3 in late 1990es and to 1.6-1.8 nowadays. It seems to be a rule of thumb that it goes square root every 15 years or so (so the depth is doubled every 15 years on same hardware). And the aggressive pruning doesn't miss much on the way, it's very smartly done. The progress in search is real, it's not only hardware related as some imply about engines' progress.

Yes, a couple of years ago Bob Hyatt and I had a big discussion on this, he was saying it was mostly hardware and I was saying that software improved as much as hardware if not more.

The pruning definitely takes its toll but it's amazing how little it misses. I think most of the progress I have made with Komodo in the last 2 versions had to do with making it prune and reduce safer without hurting the BF - and in fact I think it now prunes more aggressively at the same time.

I agree that software improved not less than hardware but
I do not think that the pruning miss so little(inspite of the fact that it is clearly productive to playing strength).

Let me be clear on this. The pruning definitely hurts the play of the program at fixed depth and it's a non-trivial amount. I evidently didn't make that part clear.

You probably do not need a lot of plies to have depth d(with no pruning) wins against depth d+1 with the pruning that you have
and I guess that depth 9 with no pruning is going to win against depth 10 with all the pruning that you have.

It may be interesting to have some rating list of different small depths when you test every depth with 3 options:
1)normal
2)no pruning but extensions are still the same.
3)no pruning and no extensions(qsearch is the same and I do not consider it as extension because programs do not know to evaluate positions that are not quiet positions).

[Laskos]

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.

Still, the BF of top engines went from 6 in 1980es to 3 in late 1990es and to 1.6-1.8 nowadays. It seems to be a rule of thumb that it goes square root every 15 years or so (so the depth is doubled every 15 years on same hardware). And the aggressive pruning doesn't miss much on the way, it's very smartly done. The progress in search is real, it's not only hardware related as some imply about engines' progress.

Yes, a couple of years ago Bob Hyatt and I had a big discussion on this, he was saying it was mostly hardware and I was saying that software improved as much as hardware if not more.

The pruning definitely takes its toll but it's amazing how little it misses. I think most of the progress I have made with Komodo in the last 2 versions had to do with making it prune and reduce safer without hurting the BF - and in fact I think it now prunes more aggressively at the same time.

I agree that software improved not less than hardware but
I do not think that the pruning miss so little(inspite of the fact that it is clearly productive to playing strength).

Let me be clear on this. The pruning definitely hurts the play of the program at fixed depth and it's a non-trivial amount. I evidently didn't make that part clear.

I just let play overnight Shredder 6PB against Houdini 3 at fixed depth 11. Houdini 3 on average searched 200,000 or so nodes, Shredder 6PB 10,000,000. The result was 66:34 for Houdini, at this fixed depth. These 11 plies of Houdini were as valuable as those of the ancient Shredder 6, although the pruning is much more aggressive in Houdini. The pruning seems only mildly to hurt the play, it is amazingly clever. Komodo 5 at fixed depth is as strong as Houdini 3, so the same goes to Komodo.

[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.

Still, the BF of top engines went from 6 in 1980es to 3 in late 1990es and to 1.6-1.8 nowadays. It seems to be a rule of thumb that it goes square root every 15 years or so (so the depth is doubled every 15 years on same hardware). And the aggressive pruning doesn't miss much on the way, it's very smartly done. The progress in search is real, it's not only hardware related as some imply about engines' progress.

Yes, a couple of years ago Bob Hyatt and I had a big discussion on this, he was saying it was mostly hardware and I was saying that software improved as much as hardware if not more.

The pruning definitely takes its toll but it's amazing how little it misses. I think most of the progress I have made with Komodo in the last 2 versions had to do with making it prune and reduce safer without hurting the BF - and in fact I think it now prunes more aggressively at the same time.

I agree that software improved not less than hardware but
I do not think that the pruning miss so little(inspite of the fact that it is clearly productive to playing strength).

Let me be clear on this. The pruning definitely hurts the play of the program at fixed depth and it's a non-trivial amount. I evidently didn't make that part clear.

I just let play overnight Shredder 6PB against Houdini 3 at fixed depth 11. Houdini 3 on average searched 200,000 or so nodes, Shredder 6PB 10,000,000. The result was 66:34 for Houdini, at this fixed depth. These 11 plies of Houdini were as valuable as those of the ancient Shredder 6, although the pruning is much more aggressive in Houdini. The pruning seems only mildly to hurt the play, it is amazingly clever. Komodo 5 at fixed depth is as strong as Houdini 3, so the same goes to Komodo.

I think there is an option to turn off LMR in Komodo CCT. If you do this and run fixed depth matches you will see that it does hurt the program by a very non-trivial amount. However I believe that top programs are far superior anyway, with or without LMR.

In my opinion the evaluation function is the least respected part of chess programs these days and only a few programs have truly excellent ones and what you are seeing is primarily superior evaluation.

Other than LMR, the forward pruning that Komodo does is amazingly good and that actually has little impact on strength, it's just a big speed boost. And we do pretty aggressive pruning. I assume it is like that for Houdini and other programs too.

I would like to see that test done with Stockifsh, a program which is substantially weaker than Houdini, Komodo or Critter at the same depth.

There is a certain sense in which depth is just an arbitrary number though. It has a specific meaning as an absolute threshold between the "quies" and "main" search but with extensions, reduction, and various forms of razoring and other forward pruning techniques you can get significantly difference searches reporting the same depth.

[Sven]

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

[Don]

The rule of thumb used to be that if you double the hash table size, the search speed gets 7% faster. That was a long time ago and I don't know what it is with modern program. Of course that rule of thumb does not apply when the hash table size is already adequate - or does not fill up.

So clearly that could have an impact on the branching factor. Once the hash table fills then expect the BF to sharply increase.

The other issue is that in general larger hash tables have a negative impact on the performance of chess programs due to cache contention issues - although that impact is hardly a factor at relatively small hash table sizes and with each generation of CPU improvement are made. This might actually serve to make the branching factor look especially good even if the performance is slightly less because you are suppressing the speed at low depths while getting great hash table utilization at high depths.