Branching Factor of top engines

[Laskos]

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

You took two extremes, but as you see, usually there are 20-30% differences for different hash tables. Even with bad luck, that 86% difference means (1.86)^(1/27)~1.023 for BF. This 2.3% difference in BF is still acceptable, so BF only weakly depends on the hash size. I used a hash of 512MB, and it was filled in half to a quarter of allotted time. This is pretty typical of what happens at LTC. Maybe I should repeat the test with 1GB hash, but I don't expect big changes, probably mostly statistical.

[Sven]

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.

It should be noted that the BF numbers given by Kai in his original posting (calculated by the Shredder GUI) are not based on that EBF formula above. They are simply taken as "nodes[d] / nodes[d-1]", where the BF value in the first line of each engine's table obviously refers to a "nodes[d-1]" value of a previous iteration that is not printed.

As to counting QS nodes or not counting them, I currently believe it does not make much of a difference. You can include or exclude them and get different numbers but in both cases the results should be comparable between different engines since the typical percentage of QS nodes among the total number of nodes should be fairly constant, at least for today's top engines (I recall some 80% where I assume these include QS root nodes at full-width horizon as well).

Sven

[IWB]

You took two extremes,

Yes, of course

...but as you see, usually there are 20-30% differences for different hash tables. Even with bad luck, that 86% difference means (1.86)^(1/27)~1.023 for BF. This 2.3% difference in BF is still acceptable, so BF only weakly depends on the hash size.

I can follow the mathematics, but still I am not 100% convinced that the different nodes used to reach different depth with different hash size have such a small impact (and 2.3% are negligible!) ... I have to make some more tests here.

I used a hash of 512MB, and it was filled in half to a quarter of allotted time. This is pretty typical of what happens at LTC. Maybe I should repeat the test with 1GB hash, but I don't expect big changes, probably mostly statistical.

Please use 2 GB, on my 4.4GHz i5 Houdini fills 512MB (Starting position) in 80s. In average the time per move for a 120/40+60/20+60rest is more at 3 min when time used completly and 80 move average per game. 2GB because with one thread this seems to be particular difficult for Houdini (for whatever reason) and I like to compare that with 256 MB or 8GB as these two where quite good ... (Yes , that are extremes again, I know )


Interesting thing you have here.

BYe
Ingo

[Daniel Shawul]

It should be noted that the BF numbers given by Kai in his original posting (calculated by the Shredder GUI) are not based on that EBF formula above. They are simply taken as "nodes[d] / nodes[d-1]", where the BF value in the first line of each engine's table obviously refers to a "nodes[d-1]" value of a previous iteration that is not printed.

Well I am not surprised as that seems to have made its way through chess community. I belive it is wrong for two reasons. First you don't have an estimate of the BF for the first iteration. Second the definition depends on IID being done with an increment of one. The very first researchers which had nothing to refer to did come up with similar formulas to compare search efficiency. A formula from the 60's (Slagel) is the 'depth ratio' defined as

Code: Select all

DR = log(N) / log(N_mm)

where N_mm refers the number of nodes searched by minimax. But from 75 onwards there is no doubt about the N^(1/d) formula is the accepted one. Except for the fact that N is taken as the number of leaf nodes because it is convenient to work with just b^d than \sum_i {b^d}. But I had to revert back to the text-book definition for LMR since the leaf nodes are too few..

As to counting QS nodes or not counting them, I currently believe it does not make much of a difference. You can include or exclude them and get different numbers but in both cases the results should be comparable between different engines since the typical percentage of QS nodes among the total number of nodes should be fairly constant, at least for today's top engines (I recall some 80% where I assume these include QS root nodes at full-width horizon as well).
Sven

Yes i had the formula implemented in Nebiyu two years ago and I see that qsearch nodes only have big effect in the first 2-3 iterations. EBF can start from 6-12 and fall down to 2 as the iterations progress.

[Laskos]

You took two extremes,

Yes, of course

...but as you see, usually there are 20-30% differences for different hash tables. Even with bad luck, that 86% difference means (1.86)^(1/27)~1.023 for BF. This 2.3% difference in BF is still acceptable, so BF only weakly depends on the hash size.

I can follow the mathematics, but still I am not 100% convinced that the different nodes used to reach different depth with different hash size have such a small impact (and 2.3% are negligible!) ... I have to make some more tests here.

I used a hash of 512MB, and it was filled in half to a quarter of allotted time. This is pretty typical of what happens at LTC. Maybe I should repeat the test with 1GB hash, but I don't expect big changes, probably mostly statistical.

Please use 2 GB, on my 4.4GHz i5 Houdini fills 512MB (Starting position) in 80s. In average the time per move for a 120/40+60/20+60rest is more at 3 min when time used completly and 80 move average per game. 2GB because with one thread this seems to be particular difficult for Houdini (for whatever reason) and I like to compare that with 256 MB or 8GB as these two where quite good ... (Yes , that are extremes again, I know )


Interesting thing you have here.

BYe
Ingo

Hi Ingo, I have repeated the test for Houdini 3, this time with 2GB hash and an average of 3-5 minutes of thinking time per position. The hash fills in a half to one quarter of the allotted time, and the result is very close to the old, shallower depth BF.

Houdini 3
Ply:16 Positions: 30 Avg Nodes: 8255150 Branching = 1.62
Ply:17 Positions: 30 Avg Nodes:17638161 Branching = 2.14
Ply:18 Positions: 30 Avg Nodes:30932455 Branching = 1.75
Ply:19 Positions: 30 Avg Nodes:48854066 Branching = 1.58
Ply:20 Positions: 30 Avg Nodes:93472563 Branching = 1.91
Ply:21 Positions: 30 Avg Nodes:198689470 Branching = 2.13
Ply:22 Positions: 30 Avg Nodes:391621195 Branching = 1.97
Ply:23 Positions: 30 Avg Nodes:751912694 Branching = 1.92
Average BF: 1.87
1/Log(BF)=1.60

The old result was

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

So, I don't see much influence on reasonable hash size, the BF goes as a power (1/depth) of the speed ratio (which varies slowly with the hash size, if it is reasonable).

[Laskos]

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.

Yes, it seem to give 67:33 at fixed depth. But the node count is 4-6 times lower to the same depth with LMR ON, which more than compensates this. And yet Komodo with LMR ON at fixed depth is significantly stronger than Shredder 6. Here probably the excellent evaluation function of Komodo, Houdini, etc. comes to play its role.

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.

I think all nowadays top engines have much better evals than 2002 engines. The fact that they can stand Shredder 6 at fixed depth with such aggressive prunning shows that.

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.

Yes, but BF as counted either by (Nodes)^(1/depth) or average of Nodes(d)/Nodes(d-1) as counted by Shredder GUI describes pretty well what happens with top engines on long periods of time. EBF goes as square root every 15 or so years, and that's amazing. And the sense of "ply" and "nodes" doesn't seem to depreciate with time too much, as shown by games at fixed depth.

[lucasart]

Daniel,

Just to clarify, the formula EBF = nodes^(1/d) is asymptotic, right?

In the textbook example of a perfectly balanced tree with b child per nodes and where each path root->leaf does exactly d moves, and assuming the engine counts the nodes normally (ie. increments the node count at the entry point of the search):

Code: Select all

nodes = 1 + b + b^2 + ... + b^(d-1) = (b^d-1)/(b-1) ~= (b^d)/(b-1)

(assuming that b^d >> 1, which is true asymptotically)

Now taking the d-th root of that:

Code: Select all

nodes^(1/d) ~= b/[(b-1)^(1/d)] ~= b

(again, asymptotically, (b-1)^(1/d) = 1)

PS: I know this is trivial, but I thought it deserved clarification. At first it took me a while to figure out how you solved (b^d - 1)/(b - 1) = nodes, but then I realized that you "cheated"

[Daniel Shawul]

There is nothing asymptotic about a formula but the input i.e whether using leaf or toal nodes. Number of leaf nodes is asymptotically the same as the total nodes as you have now worked out. In Nebiyu I actually calculate it using (b^d - 1)/(b-1) so i didn't cheat. And like I said for the LMR, the largest number of nodes occur around say 70% to the whole depth. So if you want to make simplifications like that you will need to determine that but it is just easy to use the total nodes.

Have you checked those references I gave you, rather than snipping them like nobody business. I recommend them for anyone to put ego in check (including me). You would think you understand alpha-beta but baahm you then understand 60s guys have the sincerest understanding of stuff.

[lucasart]

There is nothing asymptotic about a formula but the input i.e whether using leaf or toal nodes. Number of leaf nodes is asymptotically the same as the total nodes as you have now worked out. In Nebiyu I actually calculate it using (b^d - 1)/(b-1) so i didn't cheat. And like I said for the LMR, the largest number of nodes occur around say 70% to the whole depth. So if you want to make simplifications like that you will need to determine that but it is just easy to use the total nodes.

Have you checked those references I gave you, rather than snipping them like nobody business. I recommend them for anyone to put ego in check (including me). You would think you understand alpha-beta but baahm you then understand 60s guys have the sincerest understanding of stuff.

Look, I understand that you have huge respect for these people and their papers. But they are not gods: they are humans, and they make arbitrary decisions like we all do. Surely they know what they are doing, and they have their reasons for doing these decisions.

The notion of branching factor is:

(i) only properly defined in the case of a tree with the same number of child at every node. In the particular case where the tree is also balanced, then

Code: Select all

nodes=1+b+...+b^(d-1)=(b^d-1)/(b-1)

(ii) any extension of this definition is completely arbitrary. the fact that the author you mention have chosen

Code: Select all

EBF=nodes^(1/d)

is only compatible with a balanced tree with constant branching factor, in the asymptotic case, as I demonstrated above. they probably chose this formula because they are studying the asymptotic behaviour of algorithms anyway, and the formula happens to be simple, and the equation (b^d-1)/(b-1)=nodes cannot generally inverted analytically to find b=f(nodes).

Wikipedia's article is very poor and does not mention anything beyond (i), but the chess programming wiki does:
http://chessprogramming.wikispaces.com/Branching+Factor

Personally, I prefer this definition:

Code: Select all

EBF := sqrt(nodes(N) / nodes(N-2))

[Daniel Shawul]

Lucas you tend to offer opinions rather too quickly when you don't have enough background yourself. Also you seem to have utter disrespect for past reseach like you demonstrate here and the other day with LMR discussion. I guess chesswiki + cutechess + clop + testing makes one too proud to look in to past work, just saying . But don't expect me to take whatever you conjure as EBF definition seriously.
Just to end the conversation here is the code I use to calculate EBF in Nebiyu.

Code: Select all

	/*calculate EBF by bisection method*/
	double mynodes = (double)nodes; 
	double EBFleaf = pow(mynodes,1./search_depth),
		EBFmax = EBFleaf,EBFmin = 1,EBF,N;
	EBFmax = pow(mynodes,1./search_depth);
	EBFmin = 1;
	for(i = 0;i < 100;i++) {
		EBF = (EBFmin + EBFmax) / 2;
		N = (pow(EBF,search_depth + 1) - 1) / (EBF - 1);
		if(mynodes > N) EBFmin = EBF;
		else EBFmax = EBF;
	}
	print_fmt(" EBF=%4.2f",EBF);
	print_fmt("\n");