Branching Factor?

[H.G.Muller]

I often read the claim that the use of null-move pruning reduces the branching factor of a chess engine from 6-7 of plain alpha-beta to 3-4. On deeper analysis, it seems to me that this cannot be true:

If a search truly has a smaller branching factor, the number of plies it reaches for a given number of nodes would be a certain factor higher than that of the other search. In particular, if the branching factor drops from 6 to 4, the ratio of the search depths should be log 6/log 4 = 1.3, i.e. where one program searches 10 ply, the other searches 13, but when one searches 20, the other searches 26. The depthe advantage of the program with the lowest branching factor grows without bound if the search depth increases.

However, regular (as opposed to recursive) null-move pruning can never do that. An NMP tree of nominal depth N has some (in fact most) branches that run to depth N-R, and some branches that run to depth N. This tree definitely has fewer nodes than a fixed-depth search of depth N. But with nominal depth N+R the reduced branches all go to depth N, and the unpruned branches go to N+R. This tree is definitely bigger than a flat N-ply search. So the number of plies you gain from NMP can never be more than R.

So in the end NMP cannot lead to a reduction of the branching factor. It merely reduces the prefactor. For low depths this might create the suggestion of a lower branching ratio, because the pre-factor itself is (at these low depths) depth dependent: the fraction of branches that contain a null move is well below 100% initially, but as the depth increases, it becomes more and more likely that a null move could be employed somewhere along the path. But as soon as every path (except the PV) has a null move in it, the prefactor saturates and becomes depth independent again. Thus from that point on, also the apparent branching factor should return to its normal alpha-beta value of 6-7, limiting the advantage of NMP in plies to somewhere between 0 and R.

Does the claim of reduced branching factor only apply to recursive null-move pruning?

[Gerd Isenberg]

Does the claim of reduced branching factor only apply to recursive null-move pruning?

I think yes - the reduced branching factor is due to recursive null-move pruning.

http://www.seanet.com/~brucemo/topics/nullmove.htm

[Uri Blass]

certainly it is because of recursive null move pruning.

The main question is if recursive null move pruning better than non recursive null move pruning.

I never tested non reciursive null move pruning so I do not know.

It may be interesting if people tested non recursive null move pruning to compare with recursive null move pruning.

Uri

[Gerd Isenberg]

Yes, one may introduce a counter which is incremeted if making null-move and decremented if unmaking nullmove, to allow only one or in general N null-move(s) per path.

Even with non recursive null-move, isn't there a small exponential gain? Since with each iteration we introduce one additional ply for nmp and somehow the probability that nmp save nodes per path increase?

[H.G.Muller]

With non-recursive NMP the gain saturates, because a branch can never be shortened by more than R plies. So after virtually all branches have incorporated a null move a tree of nominal depth N actually looks like a flat tree of depth N-R. (with only the PV, and perhaps a few of the branches that branched off very late extending to depth N). Such a tree would have

C * B**(N-R) = C/B**R * B**N

nodes. This is a lower limit, so asymptotically the tree size will have to go up with the same exponent B as the unreduced tree.

[Stan Arts]

Hi,

Imho there are a lot of side effects, for example the R reduced search is being done with a closed window around beta that could in some cases return faster then a regular search to N-R.
The higher searchdepth overal should give N a higher quality with better moveordening and branchingfactor then a regular alpha-beta search to N.
Also doing a nullmove in a line effectively doesn't make it brute force anymore because you skipped a move. In my tests it was something like with a single R=2 (with no verification or other tricks) it needed 4 extra ply to resolve a middlegame zugzwang, so you seem to reduce brute force depth further then the R used. So imho by those effects N+R is not the limit for non-recursive nullmove. (and that you really do improve branchingfactor)

Atleast I notice with my program (with a form of non-recursive nullmove) the branchingfactor (bad, but much better then with alpha-beta only) does not increase much when searching to big depths and for very long. (hours)

Maybe I can do some tests in the comming days.

Groeten,
Stan

[H.G.Muller]

Imho there are a lot of side effects, for example the R reduced search is being done with a closed window around beta that could in some cases return faster then a regular search to N-R.

Interesting point, that I did indeed not take into account. The null move is also searched with a null window. In a PVS search this would not make a difference, because all refutation branches already have a null window from the start, even before null-move pruning. So NMP might trim the tree more towards a PVS size, even in case a plain alpha-beta is used. The difference should not be that large, however.

The assumptions I made was that move sorting was perfect, i.e. that in any cut node the cut-move would be tried first, and be chosen as a null move whenever possible, without wasting time on null-move searches when they are not providing a cutoff. In practice that might not be realistic, and a plain alpha-beta search might tend to suffer more from this than an NMP search.

[bob]

Let me add, for my first post here, that this is actually "mangling" a well-known term. "branching factor".

Null move absolutely can _not_ reduce the branching factor of the tree. The only thing that can do that is classic forward pruning. Null move does reduce the "effective branching factor" which is normally computed as

EBF = (time for iteration N) / (time for iteration N-1)

and since null-move reduces the overall size of the tree, the search time is reduced, and the "effective branching factor" is reduced accordingly.

It is easy to measure the improvement using Crafty. Just add "selective 0/0" as a command before searching a position, then search the same position without that command and compare the times or use the iteration statistics to compute the EBF for each new iteration. sel 0/0 totally disables null-move.

Add null-move and late-move reductions and EBFs of 2 or lower are quite common... which is remarkable.

[H.G.Muller]

OK, so I was referring to the EBF. But I still don't see how a non-recursive null-move pruning could reduce the asymptotic EBF (in the limit for very large N). NMP can at most take R plies of (nearly) every line, which result in a constant saving factor independent of N, and thus does not affect the EBF.

A minimal tree will have a PV and all lines branching from it will be "refutation trees" of alternating all nodes and cut nodes. With perfect move sorting the cut nodes will only try a single move.

This should not be dependent on manipulations with the window. A null window in the refutation branches makes you more tolerant in the cut nodes, enhancing the probability that a non-best move will still be able to produce the cutoff. But that is only important in the case of imperfect move sorting.

So should the conclusion really be that the improvement of the EBF occurs in the cut nodes, that on the average find the cut move after fewer tries with NMP because the null move is the cut move more often than any other move that seems a likely cut move, and is always tried first?

[diepeveen]

I often read the claim that the use of null-move pruning reduces the branching factor of a chess engine from 6-7 of plain alpha-beta to 3-4. On deeper analysis, it seems to me that this cannot be true:

If a search truly has a smaller branching factor, the number of plies it reaches for a given number of nodes would be a certain factor higher than that of the other search. In particular, if the branching factor drops from 6 to 4, the ratio of the search depths should be log 6/log 4 = 1.3, i.e. where one program searches 10 ply, the other searches 13, but when one searches 20, the other searches 26. The depthe advantage of the program with the lowest branching factor grows without bound if the search depth increases.

However, regular (as opposed to recursive) null-move pruning can never do that. An NMP tree of nominal depth N has some (in fact most) branches that run to depth N-R, and some branches that run to depth N. This tree definitely has fewer nodes than a fixed-depth search of depth N. But with nominal depth N+R the reduced branches all go to depth N, and the unpruned branches go to N+R. This tree is definitely bigger than a flat N-ply search. So the number of plies you gain from NMP can never be more than R.

So in the end NMP cannot lead to a reduction of the branching factor. It merely reduces the prefactor. For low depths this might create the suggestion of a lower branching ratio, because the pre-factor itself is (at these low depths) depth dependent: the fraction of branches that contain a null move is well below 100% initially, but as the depth increases, it becomes more and more likely that a null move could be employed somewhere along the path. But as soon as every path (except the PV) has a null move in it, the prefactor saturates and becomes depth independent again. Thus from that point on, also the apparent branching factor should return to its normal alpha-beta value of 6-7, limiting the advantage of NMP in plies to somewhere between 0 and R.

Does the claim of reduced branching factor only apply to recursive null-move pruning?

Diep and Quest have a branching factor of 2.8 when just using nullmove+hashtable. Hashtable is a very important factor to consider using besides double nullmove.

Vincent

[diepeveen]

Let me add, for my first post here, that this is actually "mangling" a well-known term. "branching factor".

Null move absolutely can _not_ reduce the branching factor of the tree. The only thing that can do that is classic forward pruning. Null move does reduce the "effective branching factor" which is normally computed as

EBF = (time for iteration N) / (time for iteration N-1)

and since null-move reduces the overall size of the tree, the search time is reduced, and the "effective branching factor" is reduced accordingly.

It is easy to measure the improvement using Crafty. Just add "selective 0/0" as a command before searching a position, then search the same position without that command and compare the times or use the iteration statistics to compute the EBF for each new iteration. sel 0/0 totally disables null-move.

Add null-move and late-move reductions and EBFs of 2 or lower are quite common... which is remarkable.

how many plies do you get with crafty when using some sort of history pruning at 8 chips?

Vincent

[diepeveen]

OK, so I was referring to the EBF. But I still don't see how a non-recursive null-move pruning could reduce the asymptotic EBF (in the limit for very large N). NMP can at most take R plies of (nearly) every line, which result in a constant saving factor independent of N, and thus does not affect the EBF.

A minimal tree will have a PV and all lines branching from it will be "refutation trees" of alternating all nodes and cut nodes. With perfect move sorting the cut nodes will only try a single move.

This should not be dependent on manipulations with the window. A null window in the refutation branches makes you more tolerant in the cut nodes, enhancing the probability that a non-best move will still be able to produce the cutoff. But that is only important in the case of imperfect move sorting.

So should the conclusion really be that the improvement of the EBF occurs in the cut nodes, that on the average find the cut move after fewer tries with NMP because the null move is the cut move more often than any other move that seems a likely cut move, and is always tried first?

Technically spoken the b.f. is far better than most claim here, because if you use nullmove basically that entire search is trying to 'refute' this position with some sort of replacement search.

So you could argue that those nodes you could not count in your branching factor if b.f. is defined as the number of nodes.

However i just care for search times.

In which case the improvement is basically the reduction factor, not so much the refutation search itself.

[bob]

How many plies in what time control? I'd suspect that at the WCCC we are going to be seeing 17-18-19 depending. parallel search seems to respond well to late move reductions, with respect to speedup. It's not hurting performance at all that I have measured so far, speedups look right in line with older versions.

[H.G.Muller]

The hash table should indeed truly reduce the EBF. I was rather disappointed, though, how few ranspositions remain in a minimax tree with good move sorting. I only counted about 5% of transposition hits with sufficient draft, even under conditions where virtually no positions have to be overwritten. So that should reduce the EBF by only 5%.

[diepeveen]

The hash table should indeed truly reduce the EBF. I was rather disappointed, though, how few ranspositions remain in a minimax tree with good move sorting. I only counted about 5% of transposition hits with sufficient draft, even under conditions where virtually no positions have to be overwritten. So that should reduce the EBF by only 5%.

the observed branching factor is not equal to the hashtable hitrate.

Vincent

[diepeveen]

The hash table should indeed truly reduce the EBF. I was rather disappointed, though, how few ranspositions remain in a minimax tree with good move sorting. I only counted about 5% of transposition hits with sufficient draft, even under conditions where virtually no positions have to be overwritten. So that should reduce the EBF by only 5%.

the observed branching factor is not equal to the branching factor minus hashtable hitrate.

They are 2 totally different statistics, though a better hashtable cutoff does influence your b.f.

An improvement of 1% of the hashtable cutoff rate does not directly translate to a 1% reduction of the branching factor.

It doesn't work that way.

Vincent

[H.G.Muller]

Well, if my hash-table hits are homogeneously distributed over depth, that should be the case, shouldn't it? If 5% of the daughter nodes of a given node is not searched because the hash table already contained the search result, at each level of the tree you only search only 95% of the moves in an all node, while in 5% of he cut nodes atthat level you don't have to search any move at all, (since you have a transposition cutoff), and in 95% of the cut nodes just one. And if only 95% of the moves have to be searched at any level, that would lower the EBF by 5%, wouldn't it?

Or is the hit rate systematically different in all nodes and cut nodes?

[diepeveen]

Well, if my hash-table hits are homogeneously distributed over depth, that should be the case, shouldn't it? If 5% of the daughter nodes of a given node is not searched because the hash table already contained the search result, at each level of the tree you only search only 95% of the moves in an all node, while in 5% of he cut nodes atthat level you don't have to search any move at all, (since you have a transposition cutoff), and in 95% of the cut nodes just one. And if only 95% of the moves have to be searched at any level, that would lower the EBF by 5%, wouldn't it?

You are assuming in your model a minimax search without alfabeta and without nullmove and without qsearch.

The branching factor gets influenced by more than just hashtable cuts and things like double nullmove are reducing the tree exponential.

So the total effect of a 5% increase, from say 3-4% to 8%-9%, 3-4% being what i have in diep for hashtable hitrate in middlegame, assuming that the +5% is evenly distributed over all depthlefts, means obviously a far bigger decrease in branching factor than just 5%.

Good example is when move ordering cutrate improves by 1%. Already at a ply or 10 that gives 1 ply deeper search.

This where if you put that in branching factor numbers in a lineair influencual way like you assume hashtable also assumes it linieair that would mean with the root being a PV node always of factor 40 which falls away:

(40 * 2.772 ^ 9) / (40 * 2.8 ^ 9 ) = 0.99^9 = 0.9135

So basically on paper a decrease of 1% of the branching factor
will reduce at that depth only 9% of the nodes, where in reality
the cutrate increase here searched exactly 1 ply deeper already at 10 ply.

Or is the hit rate systematically different in all nodes and cut nodes?

Branching factor is the RESULT of all enhancements. Enhancements don't lineairly influence the branching factor itself.

Assuming a normal position and if then suddenly your hashtable hitrate would go up from 3-4% to 8-9%, you're searching plies deeper of course. Many plies.

And not just save out a small % of the nodes.

This is very logical.

Note that at 10 ply an improvement of 5% on paper of the b.f. would mean 0.95^9 = 0.63 means 37% of the nodes you save out.

This is not the case. Reality is you'll search plies deeper.

Vincent