Hi,
I have just implemented some branching factor measurement in my chess engine, and I don't really understand the results..
I have calculated the EBF after each iteration by the standard formula: EBF = nodes[iteration] / nodes[iteration - 1].
This is my results:
Depth 1: 48
Depth 2: 2.16
Depth 3: 10.66
Depth 4: 1.57
Depth 5: 8.07
Depth 6: 1.64
Depth 7: 14.17
Depth 8: 2.01
Depth 9: 5.78
Depth 10: 3.88
I am using PVS alpha beta pruning in an iterative deepening framework, with aspiration windows, null move pruning, LMR, quiescence search and a transposition table. I tried running the test again without aspiration windows since I wondered if the results had something to do with the bounds, but I got the exact same pattern. I also tried taking the square root of the EBF as recommended on the wiki, but this only decreased all results, but not the pattern.
Is this a bug in my code, something with my calculations of EBF or normal?
Effective branching factor question
Moderators: hgm, Rebel, chrisw
-
- Posts: 174
- Joined: Thu Nov 26, 2020 10:06 am
- Full name: Niels Abildskov
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Effective branching factor question
This looks normal, it is related to odd/even differences in the alpha-beta search tree.
You could take the square root of nodes(iteration N) / nodes(iteration N-2). Take care not to include incomplete iterations (usually the last one is interrupted by timeout) and not to count nodes from previous iterations also for the current one.
An alternative formula is to take the N-th root of nodes(iteration N), with the same remarks as above.
Futhermore it may be helpful to take the average EBF from a couple of different positions (and later on always the same positions).
You could take the square root of nodes(iteration N) / nodes(iteration N-2). Take care not to include incomplete iterations (usually the last one is interrupted by timeout) and not to count nodes from previous iterations also for the current one.
An alternative formula is to take the N-th root of nodes(iteration N), with the same remarks as above.
Futhermore it may be helpful to take the average EBF from a couple of different positions (and later on always the same positions).
Sven Schüle (engine author: Jumbo, KnockOut, Surprise)