Increased Branch Factor Deeper Depths

[Cheney]

Hi,

I've come back to working on my engine after a little break and believe I have completed working out the kinks in my hash table. During testing with other engines, I have noticed at some points in the game, at deeper depths in a search, the node count / Branching Factor (BF) increases dramatically.

I use a basic form of BF calculation: node-count-this-iteration / node-count-last-iteration. The engine has a BF around 2 to 7 on average.

What I see in a few searches is a BF of 100+, even 200+. Sometimes the very next ply of that search is back to a normal BF, sometimes not.

I have two possible conclusions:

First, when this troubled search is compared to the previous search, the depth reached in that previous search is not to the depth of the current search where the BF increase happens. So, there are no hash entries which should lead to an increase in searched nodes.

Second, it may be possible that at the particular point in the game, the move ordering was not optimal for that position. One of the stats I track is the percentage of best moves (exact) found that are sorted first in the move buffer versus best moves found near the end of the move buffer. Normally, the engine hits about 88% success yet in these searches, 75% is the average percentage, a fair decrease in first move success.

My questions are:

In regards to the hash table conclusion, does this sound feasible? Has anyone else experienced this? Do you think I am chasing another hash bug?

In regards to the move ordering, I'm not so sure it is an issue which can be resolved. Sometimes a move that is not in the hash, is not a killer, has little history, and sorts to the rear can become the best move at that ply. Is this feasible too or is there something I might be missing to deal with this?

Thank you

[Henk]

Hi,

I've come back to working on my engine after a little break and believe I have completed working out the kinks in my hash table. During testing with other engines, I have noticed at some points in the game, at deeper depths in a search, the node count / Branching Factor (BF) increases dramatically.

I use a basic form of BF calculation: node-count-this-iteration / node-count-last-iteration. The engine has a BF around 2 to 7 on average.

What I see in a few searches is a BF of 100+, even 200+. Sometimes the very next ply of that search is back to a normal BF, sometimes not.

I have two possible conclusions:

First, when this troubled search is compared to the previous search, the depth reached in that previous search is not to the depth of the current search where the BF increase happens. So, there are no hash entries which should lead to an increase in searched nodes.

Second, it may be possible that at the particular point in the game, the move ordering was not optimal for that position. One of the stats I track is the percentage of best moves (exact) found that are sorted first in the move buffer versus best moves found near the end of the move buffer. Normally, the engine hits about 88% success yet in these searches, 75% is the average percentage, a fair decrease in first move success.

My questions are:

In regards to the hash table conclusion, does this sound feasible? Has anyone else experienced this? Do you think I am chasing another hash bug?

In regards to the move ordering, I'm not so sure it is an issue which can be resolved. Sometimes a move that is not in the hash, is not a killer, has little history, and sorts to the rear can become the best move at that ply. Is this feasible too or is there something I might be missing to deal with this?

Thank you

Replace your search by a simple alpha beta search and see if you still have these high BF jumps.

By the way I see I also have jumps bf = 20. This is because I reduced more on that level.

[hgm]

It seems almost impossible to just guess what causes this, without taking addidional data. You could make the engine print the path it is thinking about every second or millisecond, so that you can see what it is searching that takes so much time (nodes).

[bob]

Almost certainly more move ordering than anything else. Remember how you order. Hash move, killer moves, which were all "learned" based on what was going on the previous iteration. If this iteration suddenly encounters a major tactical pitfall it overlooked the last iteration, then suddenly all those "good moves" are no longer good, and the EBF climbs. EBF is best when you lock on to a move early and never change away from it. Because now all those hash and killer moves work. But when you change, the EBF climbs. The more "unexpected" the change, the bigger the climb...

[AlvaroBegue]

I agree with Bob's diagnosis. Perhaps you should try internal iterative deepening? I am not certain it will help, but it is plausible.

[Cheney]

Thank you for the replies everyone

Here's some comments and initial findings.

I have a fairly plain AlphaBeta/PVS search with null move pruning and hash/transposition table probing. I do not have any other pruning or reductions. For ordering, I sort moves on PV, hash, good/even captures, killers, bad captures, castling, and history. I do not have IID or aspiration but would like to try them out soon.

I do have a position which I can recreate this BF explosion after two "opponent" moves and two searches to populate all the cached tables. I recorded stats for each ply: hash hits that cut searches, beta cuts and percentage where it is first move, alpha increase where it is sorted near front and near rear.

For plies 1 to 7, each shows that ply had 33 TT cuts and the node count between plies increased by 33. Seems like all moves are TT exact moves.

Ply 8, BF is 125, 1,122 TT cuts, 2,921 beta cuts and 90% are first move tried, 1 move increased alpha and it was sorted near the front. No recorded "late moves being best". .07 seconds and 29K moves.

Ply 9 - BF 214, 97% beta cut first move, 46% alpha best move near front - this is unusually low. 2.9 seconds, 6.1M moves. 46% explains this ply, but not ply 8.

Ply 10 - BF 3, 97% beta cuts, 90% alpha near front - this is good. 10 seconds, 23.5M moves.

I performed this test with two other adjustments: clear the hash before this suspicious search and turn off the hash (except for move ordering).

All three tests find the same move and PV, clearing the hash gets to ply 10 faster, turning off the hash only gets to ply 9 with a slightly different PV, and in most other plies where there is a late alpha increase, there is a slight increase of the BF, more so when the TT was on versus off.

So I am suspecting it is the move ordering as Bob has mentioned. The previous search is two plies away from the current, the current can now get another ply deeper, must be finding a late move that changes the tree 'x' amount of plys back, and thus a node increase.

Since I do obtain the same PV and best move, maybe this is more cosmetic for now. I just do not want to clear the hash before moves and lose all that good info and I certainly hoped it is not another TT/hash bug

[Dann Corbit]

Thank you for the replies everyone

Here's some comments and initial findings.

I have a fairly plain AlphaBeta/PVS search with null move pruning and hash/transposition table probing. I do not have any other pruning or reductions. For ordering, I sort moves on PV, hash, good/even captures, killers, bad captures, castling, and history. I do not have IID or aspiration but would like to try them out soon.

I do have a position which I can recreate this BF explosion after two "opponent" moves and two searches to populate all the cached tables. I recorded stats for each ply: hash hits that cut searches, beta cuts and percentage where it is first move, alpha increase where it is sorted near front and near rear.

For plies 1 to 7, each shows that ply had 33 TT cuts and the node count between plies increased by 33. Seems like all moves are TT exact moves.

Ply 8, BF is 125, 1,122 TT cuts, 2,921 beta cuts and 90% are first move tried, 1 move increased alpha and it was sorted near the front. No recorded "late moves being best". .07 seconds and 29K moves.

Ply 9 - BF 214, 97% beta cut first move, 46% alpha best move near front - this is unusually low. 2.9 seconds, 6.1M moves. 46% explains this ply, but not ply 8.

Ply 10 - BF 3, 97% beta cuts, 90% alpha near front - this is good. 10 seconds, 23.5M moves.

I performed this test with two other adjustments: clear the hash before this suspicious search and turn off the hash (except for move ordering).

All three tests find the same move and PV, clearing the hash gets to ply 10 faster, turning off the hash only gets to ply 9 with a slightly different PV, and in most other plies where there is a late alpha increase, there is a slight increase of the BF, more so when the TT was on versus off.

So I am suspecting it is the move ordering as Bob has mentioned. The previous search is two plies away from the current, the current can now get another ply deeper, must be finding a late move that changes the tree 'x' amount of plys back, and thus a node increase.

Since I do obtain the same PV and best move, maybe this is more cosmetic for now. I just do not want to clear the hash before moves and lose all that good info and I certainly hoped it is not another TT/hash bug

Can you post the position here?
It will be interesting to see if other engines have trouble with it.

[Cheney]

The actual position does not directly create the issue. I start two positions back and then replay the game moves.

Start here:
rnbq1rk1/1pp1bppp/5n2/p2p4/3P4/P1N1P1P1/1P2NP1P/R1BQKB1R w KQ a6 0 9

The opponent moved e2f4

My engine (only with PSQ/Tapered eval) chose g7g5:
Ply:9 Score:3 sec:9.18 nodes:22997450 PV:g7g5 f4e2 c7c5 f1g2 c8e6 e1g1 b8c6 c1d2 c5d4 BF:3

Opponent moved f4e2

Then the search:
ply:1 score:5 sec:0 moves:33 PV:c7c5 BF:33
ply:2 score:5 sec:0 moves:66 PV:c7c5 f1g2 BF:2
ply:3 score:5 sec:0 moves:99 PV:c7c5 f1g2 c8e6 BF:1
ply:4 score:5 sec:0 moves:132 PV:c7c5 f1g2 c8e6 e1g1 BF:1
ply:5 score:5 sec:0 moves:165 PV:c7c5 f1g2 c8e6 e1g1 b8c6 BF:1
ply:6 score:5 sec:0 moves:198 PV:c7c5 f1g2 c8e6 e1g1 b8c6 f2f4 BF:1
ply:7 score:5 sec:0 moves:231 PV:c7c5 f1g2 c8e6 e1g1 b8c6 f2f4 g5f4 BF:1
ply:8 score:5 sec:.01 moves:29416 PV:c7c5 f1g2 c8e6 e1g1 b8c6 f2f4 g5f4 g3f4 BF:127
ply:9 score:3 sec:2.52 moves:6493272 PV:c7c5 f1g2 c8e6 e1g1 b8c6 c1d2 h7h6 f2f4 g5f4 BF:220
ply:10 score:3 sec:8.81 moves:21945605 PV:c7c5 f1g2 c8e6 e1g1 b8c6 d1c2 c5d4 e3d4 h7h6 c1e3 BF:3

I do see in comparison, the previous search's ply 9 PV, when overlaid onto this search's PV at ply 6, the last move is different.

[hgm]

So what exactly is bothering you? The large relative increase from 7 ply to 8 ply? Upto 7 ply you hardly has to search anything, because the position was already searched to 7 ply in the previous search. So every has hit gives you a hash cutoff. Only at 8 ply the real work starts.

[bob]

Thank you for the replies everyone

Here's some comments and initial findings.

I have a fairly plain AlphaBeta/PVS search with null move pruning and hash/transposition table probing. I do not have any other pruning or reductions. For ordering, I sort moves on PV, hash, good/even captures, killers, bad captures, castling, and history. I do not have IID or aspiration but would like to try them out soon.

I do have a position which I can recreate this BF explosion after two "opponent" moves and two searches to populate all the cached tables. I recorded stats for each ply: hash hits that cut searches, beta cuts and percentage where it is first move, alpha increase where it is sorted near front and near rear.

For plies 1 to 7, each shows that ply had 33 TT cuts and the node count between plies increased by 33. Seems like all moves are TT exact moves.

Ply 8, BF is 125, 1,122 TT cuts, 2,921 beta cuts and 90% are first move tried, 1 move increased alpha and it was sorted near the front. No recorded "late moves being best". .07 seconds and 29K moves.

Ply 9 - BF 214, 97% beta cut first move, 46% alpha best move near front - this is unusually low. 2.9 seconds, 6.1M moves. 46% explains this ply, but not ply 8.

Ply 10 - BF 3, 97% beta cuts, 90% alpha near front - this is good. 10 seconds, 23.5M moves.

I performed this test with two other adjustments: clear the hash before this suspicious search and turn off the hash (except for move ordering).

All three tests find the same move and PV, clearing the hash gets to ply 10 faster, turning off the hash only gets to ply 9 with a slightly different PV, and in most other plies where there is a late alpha increase, there is a slight increase of the BF, more so when the TT was on versus off.

So I am suspecting it is the move ordering as Bob has mentioned. The previous search is two plies away from the current, the current can now get another ply deeper, must be finding a late move that changes the tree 'x' amount of plys back, and thus a node increase.

Since I do obtain the same PV and best move, maybe this is more cosmetic for now. I just do not want to clear the hash before moves and lose all that good info and I certainly hoped it is not another TT/hash bug

Also make sure your ttable replacement policy is not broken. Nothing like overwriting the wrong entries to quickly cause the search to explode.