effective branching factor of chess programs

[Uri Blass]

I think that it may be interesting to have a table with the effective branching factor of different programs at different depths.

It is possible to take many random positions from games and for every depth n and engine X and position P have f(X,P,n)=number of nodes to get a pv at depth n by engine X at position P and use this information to calculate effective branching factor for different programs at differet depths.

It may be interesting to know for different programs if the effective branching factor goes up or goes down and also the worst case of branching factor for different programs.

I suggest to use number of nodes and not time because there is a problem in measuring time for small depths and we usually cannot have accurate times for depth 1 or depth 2 or even for depth 7.

[Desperado]

Hello Uri,

nice idea, but i think that using nodes wont work, simply because
there is no standard to count the nodes...
measuring time to depth may be a better comparison if we use a
minimum depth to measure more accurate (imho).

Michael

[Uri Blass]

Hello Uri,

nice idea, but i think that using nodes wont work, simply because
there is no standard to count the nodes...
measuring time to depth may be a better comparison if we use a
minimum depth to measure more accurate (imho).

Michael

The fact that there is no standard to count nodes is not very important as long as number of nodes is proportional to time.

It is not exactly proportional but the difference is usually small.

[Desperado]

well, at least my engine has no constant n/s proportion.
it can be very different depending on the position type.
let s say i have 30 000 000 to solution.
now i dont know:
- king chase midgame maybe i used 20s
- quiet open position maybe i used 14s
- or even closed position i used 17 s
-...

Further it depends on how to count these nodes. I think of
alpha-pruners like futility pruning. some of us count these
nodes some of us dont...

so, i mean there are to many if,if,if,.... to compare finally the results.

Time keeps time, there is no choice for implementation details.
Of course the time measured must be reliable(maybe like i already
mentioned with a fixed minimum depth).

On the other hand introducing a standard for nodecounting (additionally to
the nodecount everyone already has), would be a nice tool to compare
with other engines. Especially open sources can use this standard which
would further improve its intention to help developing a chess egine.

Michael

[Sven]

Even if the way of node counting of an engine is "non-standard", and even if the number of nodes depends heavily on the position type, the effective branching factor can be calculated independent from these two aspects since it is based on the ratio of nodes (or time, which is nearly equivalent as Uri stated) needed for two consecutive iterations.

If your node counting deviates from the usual way then this will not change from one iteration to the next, so you will get about the same EBF as if your node counting were "standard". A similar argument applies to the influence of the position type.

I think Uri's idea is good, and the results can be very interesting and also helpful for many programmers. Some points would have to be clarified, though:

1) Prior to each new search the hash table should be cleared, or even better, the engine should be restarted from scratch. Even though this may return results which are not perfectly realistic when compared to real game behaviour, I think this is the only way to get *comparable* results.

2) A script would be needed to drive the whole search process and to retrieve the node counts from the search output. Doing it manually will take a lot of time, is error-prone and tedious. The script would also do the final calculation and deliver results in a way suitable for further processing (e.g. CSV format).

3) By using PolyGlot it would be possible to include both WB and UCI engines.

Uri, what do you think about these points?

Sven

[Sven]

On the other hand introducing a standard for nodecounting (additionally to
the nodecount everyone already has), would be a nice tool to compare
with other engines.

The standard is already there: making a move during search increments the node count by one. That's all. Very simple to implement.

Sven

[Uri Blass]

I know that nodes per second is something that is different in different stages of the game but the question is nodes per second in a specific search.

If a program need 10,000,000 nodes to get depth 15 and
20,000,000 nodes to get depth 16 and if it needs 1 minute to get depth 15 then it usually need something close to 2 minutes to get depth 16

times at small depth may be influenced from some other jobs that the computer does at the beginning of the search and can be misleading(if the engine does some initialization before it starts the search then it may have a smaller branching factor at small depth because the initialization practically add some constant for all the times.

Here is the times of houdini(3 cpu) in the opening position.
I think that the difference between 2.849.000 nodes per second(depth 21) and 2,866,000(depth 22) nodes per second is relatively small.

FEN: rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1

Houdini_15_w32:
4/18 00:00 1.758 586.000 +0.05 Ng1f3 Ng8f6 Nb1c3 Nb8c6 d2d3 e7e6
5/18 00:00 2.057 685.000 +0.05 Ng1f3 Ng8f6 Nb1c3 Nb8c6 d2d3 e7e6
6/20 00:00 3.837 767.000 +0.05 Ng1f3 Ng8f6 Nb1c3 Nb8c6 d2d3 e7e6
7/20+ 00:00 5.988 748.000 +0.11 Ng1f3
7/20 00:00 6.455 806.000 +0.14 Ng1f3 Ng8f6 Nb1c3 Nb8c6 d2d4 e7e6 Bc1f4
8/20+ 00:00 10.491 953.000 +0.21 Ng1f3
8/27 00:00 21.343 927.000 +0.07 Ng1f3 Ng8f6 e2e4 Nb8c6 e4e5 Nf6g4 d2d4 d7d6
9/27+ 00:00 26.556 1.021.000 +0.14 Ng1f3
9/29 00:00 29.250 1.044.000 +0.17 Ng1f3 Ng8f6 e2e4 Nb8c6 Nb1c3 d7d5 e4xd5 Nf6xd5 d2d4 Bc8f5
10/29- 00:00 41.465 1.151.000 +0.10 Ng1f3 Ng8f6
10/29+ 00:00 80.117 1.456.000 +0.24 e2e4
10/29 00:00 111.106 1.564.000 +0.21 e2e4 e7e5 Ng1f3 Nb8c6 Nb1c3 Ng8f6 Bf1c4 a7a6 d2d3 b7b5
11/29- 00:00 128.872 1.610.000 +0.15 e2e4 e7e5
11/29 00:00 177.165 1.703.000 +0.10 e2e4 e7e5 Ng1f3 Nb8c6 Nb1c3 Ng8f6 Bf1c4 Nc6a5 Bc4d3 Na5c6 Qd1e2 b7b6 b2b3 Bf8c5 Nc3d5
12/29+ 00:00 228.455 1.813.000 +0.17 e2e4
12/29 00:00 384.612 2.056.000 +0.20 e2e4 e7e6 Nb1c3 d7d5 Ng1f3 Ng8f6 e4e5 Nf6e4 Qd1e2 Ne4xc3 d2xc3 Nb8c6 Bc1e3 b7b6 Qe2b5 Bc8b7
13/29 00:00 502.733 2.166.000 +0.20 e2e4 e7e6 Nb1c3 d7d5 Ng1f3 Ng8f6 e4e5 Nf6e4 Qd1e2 Ne4xc3 d2xc3 Nb8c6 Bc1e3 b7b6 Qe2b5 Bc8b7
14/29 00:00 820.739 2.286.000 +0.21 e2e4 e7e6 Nb1c3 d7d5 Ng1f3 Ng8f6 e4e5 Nf6e4 Qd1e2 Ne4xc3 d2xc3 Nb8c6 Bc1e3 b7b6 Qe2d2
15/29 00:01 1.395.688 2.444.000 +0.21 e2e4 e7e6 Nb1c3 d7d5 Ng1f3 Ng8f6 e4e5 Nf6e4 Qd1e2 Ne4xc3 d2xc3 Nb8c6 Bc1e3 b7b6 Qe2b5 Bc8b7 Ra1d1 Bf8e7
16/35- 00:01 3.791.428 2.666.000 +0.14 e2e4 e7e6
16/36 00:02 6.047.056 2.674.000 +0.09 e2e4 e7e5 Ng1f3 Nb8c6 Nb1c3 Ng8f6 Bf1c4 Bf8c5 d2d3 OO OO d7d6 Bc1e3 Bc5xe3 f2xe3 Bc8e6 Nc3d5 Nf6xd5 e4xd5
16/36 00:03 6.783.523 2.677.000 +0.18 Ng1f3 Ng8f6 d2d4 d7d5 Nb1c3 e7e6 e2e3 Nb8c6 Bf1d3 Bf8d6 OO OO e3e4 d5xe4 Nc3xe4 e6e5 Ne4xd6 Qd8xd6 d4xe5 Nc6xe5 Nf3xe5 Qd6xe5
17/36 00:03 8.387.880 2.686.000 +0.20 Ng1f3 Ng8f6 d2d4 d7d5 Nb1c3 e7e6 e2e3 Nb8c6 Bf1d3 Bf8e7 OO OO a2a3 Be7d6 h2h3 Qd8e7 Bc1d2 Bc8d7 Qd1e2
18/36 00:04 11.174.998 2.708.000 +0.17 Ng1f3 Ng8f6 d2d4 d7d5 Nb1c3 e7e6 e2e3 Nb8c6 Bf1d3 Bf8e7 OO OO a2a3 Be7d6 h2h3 Qd8e7 Bc1d2 Bc8d7 Nc3b5 Nf6e4 Nb5xd6 c7xd6
19/38 00:07 19.042.638 2.725.000 +0.13 Ng1f3 Ng8f6 d2d4 d7d5 Bc1f4 e7e6 e2e3 Bf8d6 Nb1c3 Bd6xf4 e3xf4 OO Nf3e5 Nb8c6 Bf1b5 Nc6xe5 d4xe5 Nf6e4 Nc3xe4 d5xe4 OO c7c6 Bb5c4
20/40 00:13 34.890.152 2.773.000 +0.13 Ng1f3 Ng8f6 d2d4 d7d5 Bc1f4 e7e6 e2e3 Bf8d6 Nb1c3 Bd6xf4 e3xf4 OO Bf1e2 Nb8c6 OO Bc8d7 Nf3e5 Qd8e7 Qd1d3 a7a6 h2h3 Nc6xe5 f4xe5
21/42 00:28 77.881.068 2.819.000 +0.13 Ng1f3 Ng8f6 d2d4 d7d5 Bc1f4 e7e6 e2e3 Bf8d6 Nb1c3 Bd6xf4 e3xf4 OO Bf1e2 Nb8c6 OO Bc8d7 a2a3 Qd8e7 Qd1d3 a7a6 h2h3 h7h6 Nf3e5 Nc6xe5 f4xe5
21/47 00:46 130.566.302 2.849.000 +0.17 e2e4 e7e5 Ng1f3 Nb8c6 Bf1b5 Ng8f6 OO Bf8e7 Nb1c3 OO d2d4 e5xd4 Nf3xd4 Be7c5 Bc1e3 Qd8e8 Nd4xc6 Bc5xe3 Nc6d4 Be3f4 g2g3 Bf4d6 Nd4f5 Nf6xe4 Nc3xe4 Qe8xe4 Nf5xd6 c7xd6 Qd1xd6 Qe4xc2
22/47 01:33 266.384.699 2.868.000 +0.18 e2e4 c7c5 Nb1c3 Nb8c6 Ng1f3 Ng8f6 d2d4 c5xd4 Nf3xd4 e7e6 Qd1d3 d7d5 e4xd5 Nf6xd5 Nc3xd5 e6xd5 Bf1e2 Bf8d6 Qd3e3+ Qd8e7 Qe3xe7+ Bd6xe7 Bc1e3 OO OOO Rf8e8 Rh1e1 Be7d6

[Desperado]

I know that nodes per second is something that is different in different stages of the game but the question is nodes per second in a specific search.

If a program need 10,000,000 nodes to get depth 15 and
20,000,000 nodes to get depth 16 and if it needs 1 minute to get depth 15 then it usually need something close to 2 minutes to get depth 16

times at small depth may be influenced from some other jobs that the computer does at the beginning of the search and can be misleading(if the engine does some initialization before it starts the search then it may have a smaller branching factor at small depth because the initialization practically add some constant for all the times.

Here is the times of houdini(3 cpu) in the opening position.
I think that the difference between 2.849.000 nodes per second(depth 21) and 2,866,000(depth 22) nodes per second is relatively small.

FEN: rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1

Houdini_15_w32:
4/18 00:00 1.758 586.000 +0.05 Ng1f3 Ng8f6 Nb1c3 Nb8c6 d2d3 e7e6
5/18 00:00 2.057 685.000 +0.05 Ng1f3 Ng8f6 Nb1c3 Nb8c6 d2d3 e7e6
6/20 00:00 3.837 767.000 +0.05 Ng1f3 Ng8f6 Nb1c3 Nb8c6 d2d3 e7e6
7/20+ 00:00 5.988 748.000 +0.11 Ng1f3
7/20 00:00 6.455 806.000 +0.14 Ng1f3 Ng8f6 Nb1c3 Nb8c6 d2d4 e7e6 Bc1f4
8/20+ 00:00 10.491 953.000 +0.21 Ng1f3
8/27 00:00 21.343 927.000 +0.07 Ng1f3 Ng8f6 e2e4 Nb8c6 e4e5 Nf6g4 d2d4 d7d6
9/27+ 00:00 26.556 1.021.000 +0.14 Ng1f3
9/29 00:00 29.250 1.044.000 +0.17 Ng1f3 Ng8f6 e2e4 Nb8c6 Nb1c3 d7d5 e4xd5 Nf6xd5 d2d4 Bc8f5
10/29- 00:00 41.465 1.151.000 +0.10 Ng1f3 Ng8f6
10/29+ 00:00 80.117 1.456.000 +0.24 e2e4
10/29 00:00 111.106 1.564.000 +0.21 e2e4 e7e5 Ng1f3 Nb8c6 Nb1c3 Ng8f6 Bf1c4 a7a6 d2d3 b7b5
11/29- 00:00 128.872 1.610.000 +0.15 e2e4 e7e5
11/29 00:00 177.165 1.703.000 +0.10 e2e4 e7e5 Ng1f3 Nb8c6 Nb1c3 Ng8f6 Bf1c4 Nc6a5 Bc4d3 Na5c6 Qd1e2 b7b6 b2b3 Bf8c5 Nc3d5
12/29+ 00:00 228.455 1.813.000 +0.17 e2e4
12/29 00:00 384.612 2.056.000 +0.20 e2e4 e7e6 Nb1c3 d7d5 Ng1f3 Ng8f6 e4e5 Nf6e4 Qd1e2 Ne4xc3 d2xc3 Nb8c6 Bc1e3 b7b6 Qe2b5 Bc8b7
13/29 00:00 502.733 2.166.000 +0.20 e2e4 e7e6 Nb1c3 d7d5 Ng1f3 Ng8f6 e4e5 Nf6e4 Qd1e2 Ne4xc3 d2xc3 Nb8c6 Bc1e3 b7b6 Qe2b5 Bc8b7
14/29 00:00 820.739 2.286.000 +0.21 e2e4 e7e6 Nb1c3 d7d5 Ng1f3 Ng8f6 e4e5 Nf6e4 Qd1e2 Ne4xc3 d2xc3 Nb8c6 Bc1e3 b7b6 Qe2d2
15/29 00:01 1.395.688 2.444.000 +0.21 e2e4 e7e6 Nb1c3 d7d5 Ng1f3 Ng8f6 e4e5 Nf6e4 Qd1e2 Ne4xc3 d2xc3 Nb8c6 Bc1e3 b7b6 Qe2b5 Bc8b7 Ra1d1 Bf8e7
16/35- 00:01 3.791.428 2.666.000 +0.14 e2e4 e7e6
16/36 00:02 6.047.056 2.674.000 +0.09 e2e4 e7e5 Ng1f3 Nb8c6 Nb1c3 Ng8f6 Bf1c4 Bf8c5 d2d3 OO OO d7d6 Bc1e3 Bc5xe3 f2xe3 Bc8e6 Nc3d5 Nf6xd5 e4xd5
16/36 00:03 6.783.523 2.677.000 +0.18 Ng1f3 Ng8f6 d2d4 d7d5 Nb1c3 e7e6 e2e3 Nb8c6 Bf1d3 Bf8d6 OO OO e3e4 d5xe4 Nc3xe4 e6e5 Ne4xd6 Qd8xd6 d4xe5 Nc6xe5 Nf3xe5 Qd6xe5
17/36 00:03 8.387.880 2.686.000 +0.20 Ng1f3 Ng8f6 d2d4 d7d5 Nb1c3 e7e6 e2e3 Nb8c6 Bf1d3 Bf8e7 OO OO a2a3 Be7d6 h2h3 Qd8e7 Bc1d2 Bc8d7 Qd1e2
18/36 00:04 11.174.998 2.708.000 +0.17 Ng1f3 Ng8f6 d2d4 d7d5 Nb1c3 e7e6 e2e3 Nb8c6 Bf1d3 Bf8e7 OO OO a2a3 Be7d6 h2h3 Qd8e7 Bc1d2 Bc8d7 Nc3b5 Nf6e4 Nb5xd6 c7xd6
19/38 00:07 19.042.638 2.725.000 +0.13 Ng1f3 Ng8f6 d2d4 d7d5 Bc1f4 e7e6 e2e3 Bf8d6 Nb1c3 Bd6xf4 e3xf4 OO Nf3e5 Nb8c6 Bf1b5 Nc6xe5 d4xe5 Nf6e4 Nc3xe4 d5xe4 OO c7c6 Bb5c4
20/40 00:13 34.890.152 2.773.000 +0.13 Ng1f3 Ng8f6 d2d4 d7d5 Bc1f4 e7e6 e2e3 Bf8d6 Nb1c3 Bd6xf4 e3xf4 OO Bf1e2 Nb8c6 OO Bc8d7 Nf3e5 Qd8e7 Qd1d3 a7a6 h2h3 Nc6xe5 f4xe5
21/42 00:28 77.881.068 2.819.000 +0.13 Ng1f3 Ng8f6 d2d4 d7d5 Bc1f4 e7e6 e2e3 Bf8d6 Nb1c3 Bd6xf4 e3xf4 OO Bf1e2 Nb8c6 OO Bc8d7 a2a3 Qd8e7 Qd1d3 a7a6 h2h3 h7h6 Nf3e5 Nc6xe5 f4xe5
21/47 00:46 130.566.302 2.849.000 +0.17 e2e4 e7e5 Ng1f3 Nb8c6 Bf1b5 Ng8f6 OO Bf8e7 Nb1c3 OO d2d4 e5xd4 Nf3xd4 Be7c5 Bc1e3 Qd8e8 Nd4xc6 Bc5xe3 Nc6d4 Be3f4 g2g3 Bf4d6 Nd4f5 Nf6xe4 Nc3xe4 Qe8xe4 Nf5xd6 c7xd6 Qd1xd6 Qe4xc2
22/47 01:33 266.384.699 2.868.000 +0.18 e2e4 c7c5 Nb1c3 Nb8c6 Ng1f3 Ng8f6 d2d4 c5xd4 Nf3xd4 e7e6 Qd1d3 d7d5 e4xd5 Nf6xd5 Nc3xd5 e6xd5 Bf1e2 Bf8d6 Qd3e3+ Qd8e7 Qe3xe7+ Bd6xe7 Bc1e3 OO OOO Rf8e8 Rh1e1 Be7d6

First, I dont want to disagree that this approach(ebf by nodecount) is usable of course.

But even in your given houdini example it requires at least a certain
(minimum) depth to get the nps _stable_.

All i want to point out is, that time to depth is the most independant
unit to compare things (imho). One dont have to think about all these proportions ... and maybe i just dont see the drawbacks with time to depth.

Michael

[Sven]

There is one more technical issue to be mentioned. The EBF should be calculated based on the number of nodes needed for complete iterations. The question is whether an engine prints that information, and when.

Fruit 2.1, for instance, prints a new "info" line whenever a new best move is found (search_update_best()) and also one more "info" line at the very end of the search (send_best_move()). But to my knowledge it does not print such information at the end of each *iteration*. Therefore the only output which can be used for a reliable EBF calculation of Fruit 2.1 is the final "info" line since all intermediate output can be misleading.

Using the intermediate output could speed up the whole process since you could use only one search to get the full set of data for one engine/position pair but it would require that all engines being compared are printing their node count after each iteration, which is not the case IMO.

So the only way to go would be to only use the final node count information printed by the engine when sending the best move and to perform a new search for each single search depth. BUT even then it is required that the engine provides this information, which has to be checked.

Sven

[Desperado]

The standard is already there: making a move during search increments the node count by one. That's all. Very simple to implement.

Sven

That s new to me. Most engines i know dont increment the nodecounter
with its moveDo() procedure. Usually the nodecounter is incremented
at the beginning of a search-function (but of course that is also no standard, but the most common case i think,or not ?!)
I even dont know any engine which is doing so...

Hmm, i dont know now if your statement is just a proposal or do
you refer to some kind of already existing specification ?

(if it is a proposal, my first impression is that this does not solve the
problem of "pre-" or "post-" counting nodes like the thing with futility pruning)

Michael