Question about branching factor and about reported depth.

[George Tsavdaris]

I have seen knowledgeable people(Dann Corbit, Prof. Hyatt etc) on this matter to say that todays engines have a mean branching factor of about 2.0.
I wonder how this is possible since with the following reasoning i'm leading to a dead end:

Mean branching factor = 2.0 -> Engines are expanding about 2 more moves for each move. And let's assume that Chess has a branching factor of about 35, that is there are about 35 possible moves in every position.

So they take the examined position(the root), and then for ply=1 they evaluate 35 moves, decide which 2 of them are better and expand these 2 nodes for further searching.
For ply=2 they evaluate 35·2 positions and they expand 2 more nodes(moves) for each node so they have now 4 nodes to expand.
For ply=3 they search 35·2^2 positions and they expand 8 nodes .... and for ply=N they search 35·2^(N-1) nodes.

So when they report that they have examined ply N they have searched so far: 35 + 35·2 + 35·2^2 + ... + 2^(N-1) = 35·(2^N-1) nodes.
So for some values we have:
Ply=5 --> 1 085
Ply=6 --> 2 205
Ply=7 --> 4 445
Ply=8 --> 8 925
Ply=9 --> 17 885
Ply=10 --> 35 805
.............................
Ply=20 --> 36 700 125

But with current nodes per second speeds(1 to 10 million per s) searching to ply 20 would just take about 3 to 6 seconds and of course as we know this isn't true and it takes much longer generally.

■ So what i'm missing here?

I guess it's the way the search of the engines progresses. So?


■ So we come into my second question of what exactly the reported ply=15 for a move means. Can anyone describe in detail of how the program started to search from the root and what evaluations it has made and what it did to reach ply 1, and then how it progressed to reach ply 2 and etc in order to reach ply 15?


As Steve would say: ignorant regards.

[bob]

I have seen knowledgeable people(Dann Corbit, Prof. Hyatt etc) on this matter to say that todays engines have a mean branching factor of about 2.0.
I wonder how this is possible since with the following reasoning i'm leading to a dead end:

Branching factor has not changed in 40 years, because the rules of the game have not changed. "Effective Branching Factor" is what you are grasping for here, and that is the right term. In general, without alpha/beta at all, the game has a branching factor of about 38, and each additional ply would take 38x longer than the previous ply. Alpha/Beta drops this to roughly sqrt(38).

Mean branching factor = 2.0 -> Engines are expanding about 2 more moves for each move. And let's assume that Chess has a branching factor of about 35, that is there are about 35 possible moves in every position.

So they take the examined position(the root), and then for ply=1 they evaluate 35 moves, decide which 2 of them are better and expand these 2 nodes for further searching.
For ply=2 they evaluate 35·2 positions and they expand 2 more nodes(moves) for each node so they have now 4 nodes to expand.
For ply=3 they search 35·2^2 positions and they expand 8 nodes .... and for ply=N they search 35·2^(N-1) nodes.

So when they report that they have examined ply N they have searched so far: 35 + 35·2 + 35·2^2 + ... + 2^(N-1) = 35·(2^N-1) nodes.
So for some values we have:
Ply=5 --> 1 085
Ply=6 --> 2 205
Ply=7 --> 4 445
Ply=8 --> 8 925
Ply=9 --> 17 885
Ply=10 --> 35 805
.............................
Ply=20 --> 36 700 125

But with current nodes per second speeds(1 to 10 million per s) searching to ply 20 would just take about 3 to 6 seconds and of course as we know this isn't true and it takes much longer generally.

■ So what i'm missing here?

I guess it's the way the search of the engines progresses. So?


■ So we come into my second question of what exactly the reported ply=15 for a move means. Can anyone describe in detail of how the program started to search from the root and what evaluations it has made and what it did to reach ply 1, and then how it progressed to reach ply 2 and etc in order to reach ply 15?


As Steve would say: ignorant regards.

This is a problem to visualize. Branching Factor is simply the number of moves at any position. For chess, this is generally cited as 38. And for pure minimax trees, you can derive this BF from either counting the nodes for depth = N, and then for depth = N+1, and divide the latter by the former, and you get 38. Or you can measure the time for iteration N and N+1 and again divide, and again get 38.

Alpha/Beta is the first wrinkle however. It reduces the "effective branching factor" from 38 to sqrt(38). Knuth/Moore "An analysis of alpha/beta pruning" explains why this is and gives the mathematical proof.

Now, once you go down this "effective branching factor" road, things get very muddy. For example, if you do significant extensions in your search, then iteration N+1 might take longer than expected since you are making the tree explode a bit. If you do any sort of pruning such as:

(1) null-move (reduces depth on some branches by 2 extra plies, reducing the size of that sub-tree;
(2) reductions (LMR/etc) which reduces other moves and again shrinks the sub-tree.
(3) forward pruning which simply throws some moves away and never searches them, which obviously reduces the EBF and the actual BF since not all moves are searched.

So, in today's programs, the actual BF is not changing. The EBF is, but not because of a change in the real BF, but rather because not all branches are searched to the nominal depth. In a 20 ply search, many branches are only searched to 8-10 plies, sometimes less. For example, you search the move at ply 1, then at ply 2 you reduce a move by 2 plies, ditto at ply 3, ply 4, ply 5, and suddenly your remaiing depth is 20 - 5 - 8 (5 for getting 5 plies deep, 8 for the four 2-ply reductions. You are at ply 5 with only 7 plies left. Every additional ply reduces some branches by a total of 3.

What this means is that the time per iteration does not increase with respect to the usual branching factor because that 20 ply search really doesn't go 20 plies deep everywhere.

[Sven]

One should also mention that using a transposition table saves a lot of nodes and further reduces EBF since many subtree searches are replaced by a single hash table lookup.

Sven

[Sven]

So they take the examined position(the root), and then for ply=1 they evaluate 35 moves, decide which 2 of them are better and expand these 2 nodes for further searching.
For ply=2 they evaluate 35·2 positions and they expand 2 more nodes(moves) for each node so they have now 4 nodes to expand.
For ply=3 they search 35·2^2 positions and they expand 8 nodes .... and for ply=N they search 35·2^(N-1) nodes.

So when they report that they have examined ply N they have searched so far: 35 + 35·2 + 35·2^2 + ... + 2^(N-1) = 35·(2^N-1) nodes.
So for some values we have:
Ply=5 --> 1 085
Ply=6 --> 2 205
Ply=7 --> 4 445
Ply=8 --> 8 925
Ply=9 --> 17 885
Ply=10 --> 35 805
.............................
Ply=20 --> 36 700 125

But with current nodes per second speeds(1 to 10 million per s) searching to ply 20 would just take about 3 to 6 seconds and of course as we know this isn't true and it takes much longer generally.

In addition to Bob's reply, just a note about your calculation. You have to consider qsearch, too. Most nodes (80% is typical) are qsearch nodes. So your calculation only shows full search nodes + leaves, where the leaves are usually qsearch nodes (not considering checks here). If 20% are full search nodes and with an EBF of 2.0 the number of leaves is about equal to the number of full search nodes then your node count must be multiplied by a factor of 5/2.

In your 20 ply example, you get 36700125 * 5/2 = 91750312.5, let's say 90 Mnodes. With 1 Mnodes/sec this requires 90 sec and with 10 Mnodes/sec 9 sec, which I guess is closer to your expectations.

EDIT: With 38 instead of 35, you even get about 9% more nodes, so 98 resp. 10 seconds.
Another issue is that sometimes the first few plies do not exactly match that EBF pattern (e.g. because some search techniques are not applied here), so you can easily get totally different numbers which is highly position dependent. Therefore the EBF may be a tool to estimate the number of nodes for one additional ply of search but it is not always possible to get a good estimate for the absolute total number of nodes.

Sven

[Uri Blass]

I have seen knowledgeable people(Dann Corbit, Prof. Hyatt etc) on this matter to say that todays engines have a mean branching factor of about 2.0.
I wonder how this is possible since with the following reasoning i'm leading to a dead end:

Mean branching factor = 2.0 -> Engines are expanding about 2 more moves for each move. And let's assume that Chess has a branching factor of about 35, that is there are about 35 possible moves in every position.

So they take the examined position(the root), and then for ply=1 they evaluate 35 moves, decide which 2 of them are better and expand these 2 nodes for further searching.
For ply=2 they evaluate 35·2 positions and they expand 2 more nodes(moves) for each node so they have now 4 nodes to expand.
For ply=3 they search 35·2^2 positions and they expand 8 nodes .... and for ply=N they search 35·2^(N-1) nodes.

So when they report that they have examined ply N they have searched so far: 35 + 35·2 + 35·2^2 + ... + 2^(N-1) = 35·(2^N-1) nodes.
So for some values we have:
Ply=5 --> 1 085
Ply=6 --> 2 205
Ply=7 --> 4 445
Ply=8 --> 8 925
Ply=9 --> 17 885
Ply=10 --> 35 805
.............................
Ply=20 --> 36 700 125

But with current nodes per second speeds(1 to 10 million per s) searching to ply 20 would just take about 3 to 6 seconds and of course as we know this isn't true and it takes much longer generally.

■ So what i'm missing here?

I guess it's the way the search of the engines progresses. So?


■ So we come into my second question of what exactly the reported ply=15 for a move means. Can anyone describe in detail of how the program started to search from the root and what evaluations it has made and what it did to reach ply 1, and then how it progressed to reach ply 2 and etc in order to reach ply 15?


As Steve would say: ignorant regards.

I think that 2 is only approximation and the practical number is bigger.

If you change your 2 to 2.3 then you get more logical number

35*(2.3+2.3^2+....2.3^19) for 20 plies

programs also do not decide which 2 to expend in every node but practically decide which lines to search to smaller depth and how much smaller so practically 20 plies means that the program searched 8,9,10,11 plies in many lines.

Uri

[bob]

One should also mention that using a transposition table saves a lot of nodes and further reduces EBF since many subtree searches are replaced by a single hash table lookup.

Sven

Almost everything you do affects EBF. Better move ordering, for example. There is room for improvement everywhere.

[jwes]

One should also mention that using a transposition table saves a lot of nodes and further reduces EBF since many subtree searches are replaced by a single hash table lookup.

Sven

Almost everything you do affects EBF. Better move ordering, for example. There is room for improvement everywhere.

Using reductions instead of extensions makes your EBF appear better.

[bob]

One should also mention that using a transposition table saves a lot of nodes and further reduces EBF since many subtree searches are replaced by a single hash table lookup.

Sven

Almost everything you do affects EBF. Better move ordering, for example. There is room for improvement everywhere.

Using reductions instead of extensions makes your EBF appear better.

Some things help, some hurt. Reductions, pruning, null-move all improve EBF. Extensions hurt. Used to be all we did were extensions. Now we have more than offset that with the things that improve EBF to the point where we are seeing these ~2.0 numbers today.