Branching Factor of top engines

[Don]

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.

I agree with Daniel here, the BF is basically the BF and has little to do with the quies.

Someone asked how can the BF be so low. Let's consider a brute force program which would have a branching factor of something like 6. Such a program will always see 1 ply deeper with each iteration without exception and it's easy to calculate whether it will see a given tactic if you understand the extension rules and other details of the search including how the quies might resolve things.

A program that is very agressive with LMR, null move pruning and other tricks and forward pruning is different though. When you add 1 extra ply to the search you are not guaranteed to see 1 ply of extra tactics. You are taking some liberties and HOPING that you see what is important 1 extra ply deeper. So even though you are doing 1 more ply of search, you are probably only really effectively getting the equivalent of 0.8 ply deeper. The 0.8 figure is arbitrary and probably wrong but illustrates the point. In other words we are cheating a little and so 1 ply is not really 1 ply.

Of course the better we do it, the more likely we are seeing everything a full width program would see at the same depth but in practice some position take an extra ply to solve. So even if your BF is 2.0 and that seems pretty impressive on paper, at least a little of that is a cleverly concealed sham.

[Laskos]

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!

Yes, I think that's correct. The depth is the nominal depth of the search without QS, the node count is total.

[Laskos]

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.

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

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

[lucasart]

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.

This formula is no more than a convention. What id 'd' here ?

The problem is that d is the nominal depth of the search:
* nominal: in the presence of forward pruning method (especially search reductions), this branching factor has little to do with the average child per node. so when we compare an engine without LMR to an engine with LMR, we're comparing apples and pears. Some lines will be search at depth d, some even more (extensions), but the vast majority will not even be search at depth d/2.
* search: even without any forward pruning, and assuming the search is a simple alpha/beta, if engine A has a qsearch that goes twice deeper than engine b, it gets an incorrectly high EBF by your formula. The problem is that d is largly underestimated and should be something like d + average(qs depth at stand_pat_node) or something like that.

So it's really a formulaic extrapolation of something that is established and true in a different case (balanced tree fixed depth). You can view it as a convention/definition, but in particular, it's likely to depend on the depth, and it will be hard to have a +/- constant number for each engine (due to the above effects). So we can always run the same set of positionf at the same depth by several engines and compare the result of the formula, but we shouldn't try to extrapolate a general constant by engine out of it. That was my point.

[lucasart]

Slightly off topic: wasn't Fruit the first engine to have an EBF ~= 2 (by this measure) ?
(due to the history pruning)

[Daniel Shawul]

Get a grip, there is no debate here because the one i gave you is the text book definition that was used during the decades to prove optimality of alpha-beta by many researchers. If one researcher had to use a different one, there would be no communication or agreement. There are so many wrong definitions spread around here in chess forums, such as comparing two nodes counts on two IID iterations ,that are completely wrong. I tried to clear this up some time ago by giving many references, but chess-wiki still had those (not that i am complaining). For alpha-beta analysis, N is actually defined as the number of leaf nodes, which is close but not quite the same as the total nodes. But it is asymptotically the same as the total nodes so it is ok to use it there. But recently I had problems using that conventional definition when trying to analyse LMR! The reason is that at the leaves exactly one node is searched. So I had to revert back to the original text book definition even though all the alpha-beta literature uses number of leaf nodes.

Suggesting to use the qsearch depth is ridiculous because your branching factor will be so law to be non-existent with that definition. The 'd' in sqrt(d) is a typo as you already know but you should know many literature use 'd' for width (degree) too which is why i was inclined to make the mistake.

[lucasart]

Get a grip, there is no debate here because the one i gave you is the text book definition that was used during the decades to prove optimality of alpha-beta by many researchers. If one researcher had to use a different one, there would be no communication or agreement. There are so many wrong definitions spread around here in chess forums, such as comparing two nodes counts on two IID iterations ,that are completely wrong. I tried to clear this up some time ago by giving many references, but chess-wiki still had those (not that i am complaining). For alpha-beta analysis, N is actually defined as the number of leaf nodes, which is close but not quite the same as the total nodes. But it is asymptotically the same as the total nodes so it is ok to use it there. But recently I had problems using that conventional definition when trying to analyse LMR! The reason is that at the leaves exactly one node is searched. So I had to revert back to the original text book definition even though all the alpha-beta literature uses number of leaf nodes.

Suggesting to use the qsearch depth is ridiculous because your branching factor will be so law to be non-existent with that definition. The 'd' in sqrt(d) is a typo as you already know but you should know many literature use 'd' for width (degree) too which is why i was inclined to make the mistake.

OK, so it's a generally accepted convention. I will therefore accept it too.

Let's forget about the qsearch part. What botheres me is that comparing a simply alpha/beta with the same alpha/beta + aggressive LMR, is somewhat dubious. It's not wrong, because it's a convention/definition, but at least it gives the reader a "misleading impression".

For example, let's say that in OTB chess, I think of a variation of 10 plies and a couple of 5 plies ones, before I make a move. So by that measure, I did a d=10 search and my EBF is:

Code: Select all

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

That's one way to look at it, but another way is to say that i did not do a d=10 plies search and used some very aggressive move count pruning and LMR.

[Daniel Shawul]

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.

I am being anal about this definition after looking at past work in alpha-beta in the last week. There it is defined on the first page since it is important to what is to follow. I feel like using some conjured up definition like ratio of nodes between two IIDs is a de-service to those great people. I will give you some links in chronological order that you might hopefully enjoy.

http://repository.cmu.edu/cgi/viewconte ... xt=compsci
http://wiki.cs.pdx.edu/wurzburg2009/nfp/abmin.pdf
http://www-desir.lip6.fr/~herpsonc/docs ... baudet.pdf
http://wiki.cs.pdx.edu/wurzburg2009/nfp/abavg.pdf
http://www-public.it-sudparis.eu/~gibso ... oore75.pdf