EBF question

[Clemens Pruell]

(1) What's the lowest EBF (chess) I can get (realistically),
when using backwards pruning only (that is: the correct minmax result
should be guaranteed) ?
I programmed a (very weak) chess enigne a few years ago (which needed ~5 - 80 Sek. for analyzing all nodes up to
depth = 7 plies in an 'average' midgame position).

Sadly, my new engine is only slightly better, it will analyze 8 plies in the same time.
However, it uses a whole bunch of improvements which my old
engine didn't use:
Iterative Deepening (the old engine searched 7 plies immediately),
Hashmoves, (simplified) SEE, Killer/Counter/History/Blunder Moves for better move ordering,
incremental updates of various re-usable data (pinned pieces, SEE, attacked pieces, piece count, bitboard for pawn location,
+ move generation is also 3x faster than my old engine etc).

But the result of all these improvements together -> the new engine
searches (only) 1 ply deeper than the old one (in the same time).
The typical numbers of 'searched nodes (total)' in midgame positions is
5 Mio. - 15 Mio., but may be a lot more (up to 60 Mio) if queens are on the board and can do many legal moves.
On the other hand, in or near endgame positions (with only a few legal moves left + many hits in the hashtable)
the engine will generate an 8-ply response almost immediately.

I guess my EBF in Midgame positions must be in the range of 7,6- 9,0
{which is (of course) really bad ...}
I'm wondering whether there are still some other methods/heuristics
of backwards pruning, which could reduce the EBF
(but which should still guarantee a correct MinMax score ! -
I'm afraid my engine won't find certain mate-in-4 combinations when I use forward pruning (e.g. 'prune' every subtree,
where Q x P has a -800 SEE for the Q ? Right? That's forward pruning?
How could a program distinguish a 'good' Queen Sacrfice (because it allows to mate the opponent's
King) from an 'obvious' blunder (Queen is lost -> Prune this subtree ?))
How big is the danger that a chess program which uses forward pruning
suddenly won't find certain combinations, which lie wihtin its ('officially declared) search depth
(but are pruned away because they seem to be 'obvious' blunders?)

Atm it seems to me that if I want my engine to search for depth == 9
in the same time as it needs for depth == 8 now, I maybe MUST use some kind of forward pruning (this is the same as losing any guarantee
that the returned minmax value/ best move can be trusted, right ??).

Or is there some way for my engine of doing a full-tree search to depth 9 in ~30 Sek, and only using methods
which guarantee a correct MinMax Value and won't ever overlook even the most unexpected Queen Sacrifice ?

[hgm]

It sounds a bit fishy that all these improvements only buy you one extra ply. Without forward pruning, the only thing you can do is improve your move ordering, to make the backward pruning more effective.

Do you keep statistics, on how many beta cutoffs are caused by the first, second, third move you search? It would be best to collect such statistics for each remaining depth (which in a fixed-depth search corresponds to ply level) separately, otherwise the stats would be dominated by QS nodes, which are not really representative for full-width nodes. It would also be good to keep statistics on how many times you have a hash move, and how many cutoffs this produces, and how often killer 1 or killer 2 produce the cutoff.

[Evert]

Sadly, my new engine is only slightly better, it will analyze 8 plies in the same time.
However, it uses a whole bunch of improvements which my old
engine didn't use:
Iterative Deepening (the old engine searched 7 plies immediately),
Hashmoves, (simplified) SEE, Killer/Counter/History/Blunder Moves for better move ordering,

No null-move?
Also, out of curiosity, what are "blunder moves"? Simply keeping track of moves that historically fail low and sort them lower down in the move list, or something more clever?

incremental updates of various re-usable data (pinned pieces, SEE, attacked pieces, piece count, bitboard for pawn location,

Do you need all of that? Updating things you don't actually need can be expensive and, ultimately, a waste of time.
Don't worry too much about it though. This is hardly going to be your bottle neck at this time.

But the result of all these improvements together -> the new engine
searches (only) 1 ply deeper than the old one (in the same time).
The typical numbers of 'searched nodes (total)' in midgame positions is
5 Mio. - 15 Mio., but may be a lot more (up to 60 Mio) if queens are on the board and can do many legal moves.
On the other hand, in or near endgame positions (with only a few legal moves left + many hits in the hashtable)
the engine will generate an 8-ply response almost immediately.

No idea how to compare those numbers reliably with other programs, but that does sound like a lot.

I guess my EBF in Midgame positions must be in the range of 7,6- 9,0
{which is (of course) really bad ...}

Don't guess, calculate it.

I'm wondering whether there are still some other methods/heuristics
of backwards pruning, which could reduce the EBF

It sounds as though you have a bug that makes things sub-optimal at the moment. You'll want to fix those first.
Are your beta-cutoffs going the right way? Are you sorting moves correctly so the expected best move is searched first (it's very easy to accidentally sort it last instead)? Is the hashtable working correctly?

I'm afraid my engine won't find certain mate-in-4 combinations when I use forward pruning (e.g. 'prune' every subtree,
where Q x P has a -800 SEE for the Q ? Right? That's forward pruning?

That is forward pruning, but there need to be conditions for when you do or don't do it. Giving check is an obvious (but maybe not optimal) candidate for not doing forward pruning, having previously found a mate threat (either from a NULL-move search or in another branch of the tree) is another. But most importantly of all: that capture is probably but not certainly bad. Close to the leaves of the tree, where you may not expect to find out whether it's actually good or not before hitting the quiescence search, you may prune it (or go directly to q-search). Further away from the leaves, don't prune it outright, but maybe reduce the search depth.
That way the program will still find the mate, but at a nominally larger search depth than it otherwise would have.

How big is the danger that a chess program which uses forward pruning
suddenly won't find certain combinations, which lie wihtin its ('officially declared) search depth
(but are pruned away because they seem to be 'obvious' blunders?)

Happens all the time. Hopefully they get picked up on the next pass through the iterative deepening loop, where the search depth is larger. There's a fine balance though: prune (or reduce) too little, and you get no benefit. Prune (or reduce) too much, and it hurts more than it helps.[/i]

[Evert]

Do you keep statistics, on how many beta cutoffs are caused by the first, second, third move you search? It would be best to collect such statistics for each remaining depth (which in a fixed-depth search corresponds to ply level) separately, otherwise the stats would be dominated by QS nodes, which are not really representative for full-width nodes. It would also be good to keep statistics on how many times you have a hash move, and how many cutoffs this produces, and how often killer 1 or killer 2 produce the cutoff.

Something you (or Bob) may know that I've wondered about: to what extend is the search time dominated by "worst case" move ordering?
I did a quick test (using some tactical test positions) a couple of weeks ago and found that although most of the time the cutoff is caused by the first move searched. Sometimes the second, rarely the third. If it isn't one of those though, then chances are high that the move causing the cutoff is somewhere way down on the list, number 20, 30. In this particular case, the fail-high propagated back to the root and changed the PV. How important is it to try to improve move ordering to the point where that move gets sorted higher up, given that you can't ever avoid that situation completely?
My gut feeling is that since the problem can't be avoided anyway, and move ordering seems to be good for the most part, it probably buys very little to spend any great amount of time on the problem.

(Even if it is important, a single tactical test position is hardly going to help find a way to do that, obviously; for the curious, the move that caused the cutoff was a quiet move that moved the king into the square of a free pawn that would otherwise promote in four ply)

Sorry for running off on a tangent here, but at least it's somewhat relevant for the OP's question.

[Sven]

(1) What's the lowest EBF (chess) I can get (realistically),
when using backwards pruning only (that is: the correct minmax result
should be guaranteed) ?
I programmed a (very weak) chess enigne a few years ago (which needed ~5 - 80 Sek. for analyzing all nodes up to
depth = 7 plies in an 'average' midgame position).

Sadly, my new engine is only slightly better, it will analyze 8 plies in the same time.
However, it uses a whole bunch of improvements which my old
engine didn't use:
Iterative Deepening (the old engine searched 7 plies immediately),
Hashmoves, (simplified) SEE, Killer/Counter/History/Blunder Moves for better move ordering,
incremental updates of various re-usable data (pinned pieces, SEE, attacked pieces, piece count, bitboard for pawn location,
+ move generation is also 3x faster than my old engine etc).

But the result of all these improvements together -> the new engine
searches (only) 1 ply deeper than the old one (in the same time).
The typical numbers of 'searched nodes (total)' in midgame positions is
5 Mio. - 15 Mio., but may be a lot more (up to 60 Mio) if queens are on the board and can do many legal moves.
On the other hand, in or near endgame positions (with only a few legal moves left + many hits in the hashtable)
the engine will generate an 8-ply response almost immediately.

How does your move ordering work in quiescence search?

How do you deal with checks?

Are there any extensions you have implemented that might cause a tree explosion?

Have you tried to dump your search tree and analyze the dump? (Use a shallow search for that, not one with 60.000.000 nodes.)

Sven

[hgm]

If it isn't one of those though, then chances are high that the move causing the cutoff is somewhere way down on the list, number 20, 30.

What I sometimes do is to print positions where such a very late move causes the cutoff, to get an impression in what kind of situations this happens. In the hope to get an idea for how to recognize them cheaply, and how to identify the cut move.

IIRC the first attempt reveiled that they were almost all check evasions (because I did pseudo-legal moves even on evasions). But that is not very detrimental, as all the low-failing moves searched before where rejected in the daughted node without deeper search. So I filtered out the in-check positions as well, and only printed when not in check. Then it was mostly evasions of some other threat. I minimized that by recognizing threats (after a null-move fail low), and sorting one withdrawal of the piece to a safe square to front. But at some point you just get to positions where there is just no easy remedy. Then you really have to search. IID could help to speed up that search, but the problem is that these are often things you only discover at quite high depth. Just doing d=1 for a non-capture often isn't enough. It would be for a simple evasion when the eval is already above beta, but not for something more complex, like giving a fork or skewer when the score is below alpha.

[Clemens Pruell]

Thanks for your help,
I'll do some major debugging & statistics retrieval next.

Here's a few statistics about Hash Table -Hits, -Misses,
-Key Collisions (Legal-Move-Check failed) -Beta-Cutoff: Success/Failure Rate + Search Explosion (last example).

Code: Select all

[u]Ok Case 1 (Example):[/u]

position startpos moves e2e4 d7d5 e4d5 d8d5 b1c3
go

Nodes: 2842810,
HashHits: 255
HashEnableMiss (Key Collision): 41,
HashMiss: 88792
HashCuts: 200,
HashCut_Fail: 12
evalAccurate: 1777119,
evalLazy: 0,
bestresult: -14,
depth = 8
TIME: 5.13964 sec
info depth 8 score cp -14 nodes 2842810 pv d5e6
bestmove d5e6


[u]Ok Case 2 (Example):[/u]

position startpos moves d2d4 d7d5 c2c4 e7e6 b1c3 c7c5
go

Nodes: 3781303,
HashHits: 108
HashEnableMiss (Key Collision): 3,
HashMiss: 111159
HashCuts: 99,
HashCut_Fail: 4
evalAccurate: 2463416,
evalLazy: 0,
bestresult: 74,
depth = 8
TIME: 7.11313 sec
info depth 8 score cp 74 nodes 3781303 pv c4d5
bestmove c4d5



[u]Bad Case (Example):[/u]

position fen 4rrk1/2p4p/2p3p1/p2q4/2p1nP2/Q2bP3/PP1B2BP/R3R1K1 b - - 0 21
go

Nodes: 9221338,
HashHits: 74
HashEnableMiss (Key Collision): 8,
HashMiss: 280752
HashCuts: 62,
HashCut_Fail: 3
evalAccurate: 5591302,
evalLazy: 0,
bestresult: 115,
depth = 8
TIME: 16.0205 sec
info depth 8 score cp 115 nodes 9221338 pv f8f5
bestmove f8f5


[u]Worst Case (Example):[/u]

position fen r1br2k1/ppq2pbp/6p1/2P1p1N1/3nP3/1NQ2PP1/P5BP/R3R1K1 w - - 0 20
go

Nodes: 60564956,
HashHits: 200
HashEnableMiss (Key Collision): 6,
HashMiss: 533306
HashCuts: 190,
HashCut_Fail: 2
evalAccurate: 47600637,
evalLazy: 0,
bestresult: -14,
depth = 8
TIME: 94.1044 sec
info depth 8 score cp -14 nodes 60564956 pv h2h4
bestmove h2h4

I'm not an expert programmer, so I'm not sure whether the Hash Table
is buggy due to these numbers (most of the time I do trial + error
programming ...).

[hgm]

Well, I would sy something is very wrong, as you seem to have almost no hash hits. And the number of misses is rather low too. E.g. in the first position,for 2.8M nodes you seem to have 90k hash misses.

Why is misses +hits not simply 2.8M here?

[bob]

(1) What's the lowest EBF (chess) I can get (realistically),
when using backwards pruning only (that is: the correct minmax result
should be guaranteed) ?
I programmed a (very weak) chess enigne a few years ago (which needed ~5 - 80 Sek. for analyzing all nodes up to
depth = 7 plies in an 'average' midgame position).

Sadly, my new engine is only slightly better, it will analyze 8 plies in the same time.
However, it uses a whole bunch of improvements which my old
engine didn't use:
Iterative Deepening (the old engine searched 7 plies immediately),
Hashmoves, (simplified) SEE, Killer/Counter/History/Blunder Moves for better move ordering,
incremental updates of various re-usable data (pinned pieces, SEE, attacked pieces, piece count, bitboard for pawn location,
+ move generation is also 3x faster than my old engine etc).

But the result of all these improvements together -> the new engine
searches (only) 1 ply deeper than the old one (in the same time).
The typical numbers of 'searched nodes (total)' in midgame positions is
5 Mio. - 15 Mio., but may be a lot more (up to 60 Mio) if queens are on the board and can do many legal moves.
On the other hand, in or near endgame positions (with only a few legal moves left + many hits in the hashtable)
the engine will generate an 8-ply response almost immediately.

I guess my EBF in Midgame positions must be in the range of 7,6- 9,0
{which is (of course) really bad ...}
I'm wondering whether there are still some other methods/heuristics
of backwards pruning, which could reduce the EBF
(but which should still guarantee a correct MinMax score ! -
I'm afraid my engine won't find certain mate-in-4 combinations when I use forward pruning (e.g. 'prune' every subtree,
where Q x P has a -800 SEE for the Q ? Right? That's forward pruning?
How could a program distinguish a 'good' Queen Sacrfice (because it allows to mate the opponent's
King) from an 'obvious' blunder (Queen is lost -> Prune this subtree ?))
How big is the danger that a chess program which uses forward pruning
suddenly won't find certain combinations, which lie wihtin its ('officially declared) search depth
(but are pruned away because they seem to be 'obvious' blunders?)

Atm it seems to me that if I want my engine to search for depth == 9
in the same time as it needs for depth == 8 now, I maybe MUST use some kind of forward pruning (this is the same as losing any guarantee
that the returned minmax value/ best move can be trusted, right ??).

Or is there some way for my engine of doing a full-tree search to depth 9 in ~30 Sek, and only using methods
which guarantee a correct MinMax Value and won't ever overlook even the most unexpected Queen Sacrifice ?

With pure alpha/beta, the math is pretty easy, assuming a fixed depth search and ignoring extensions which would change this slightly:

minmax = W^D terminal nodes searched. If you want to count all nodes, you could do sum (W^1 + W^2 + ... + W^D) which is approximately W^(D+1). Most just use terminal nodes and almost all theoretical analysis has used the W^D number so let's go with that.

So, Minmax = W^D terminal nodes.

Alpha/beta = W^floor(D/2) + W^ceil(D/2)

floor = round down to next lower integer, ceil = round up. And for the convenient case of D being even, we get

Alpha/beta = 2 * W ^(D/2)

Now you can plug in some numbers and get an effective branching factor. Say for D=8, and assuming W=38, the number most commonly quoted for average moves in a position, over an entire game,

depth 8 nodes = 2 * (38^4) = 4, 170,272.

Depth 9 nodes = 38^4 + 38^5 = 81,320,304.

The effective branching factor is, for that case, about 20.

If you want to beat that, you have to do some sort of forward pruning, or else depth reductions. Null-move is a good start, although I do not know of a theoretical analysis showing what it does to EBF, but it does a lot.

Today's Crafty seems to be about 2.0 roughly, although as move ordering breaks down due to tactical complexities, that can go down or up significantly...

Most simply compute EBF = time used for current depth / time used for last depth. Which is a reasonable approximation. If the time for the last iteration is cumulative, your EBF will be somewhat understated, naturally. Better is time (iteration n) / time (iteration n-1) where the times are just for those two searches, not cumulative time.

[Gerd Isenberg]

So, Minmax = W^D terminal nodes.

Alpha/beta = W^floor(D/2) + W^ceil(D/2)

floor = round down to next lower integer, ceil = round up. And for the convenient case of D being even, we get

Alpha/beta = 2 * W ^(D/2)

Now you can plug in some numbers and get an effective branching factor. Say for D=8, and assuming W=38, the number most commonly quoted for average moves in a position, over an entire game,

depth 8 nodes = 2 * (38^4) = 4, 170,272.

Depth 9 nodes = 38^4 + 38^5 = 81,320,304.

The effective branching factor is, for that case, about 20.
...

depth 10 nodes = 2 * (38^5) = 158,470,336
The effective branching factor is, for that case, about 2.

You have that individual odd and even EBF.

Isn't it more appropriate if "measuring" average EBF to take the square root from number of nodes n to n+2?

Code: Select all

EBF(odd)  = (W+1)/2
EBF(even) = 2W/(W+1)
EBF(avr)  = sqrt (EBF(odd) * EBF(even) ) = sqrt(W)