EBF question

[bob]

Thinking late at night after a lengthy call of duty session didn't work very well.

*blink*

Didn't see that one coming.

??

Been an xbox live player since the original Ghost Recon game on the original Xbox. Then migrated to the various call of duty programs, starting with COD 4, when Ghost Recon faded away. Current is COD: black ops.

Shoot, I used to play in doom team deathmatch battles when we had some faculty / student battles back when doom was popular on the PC.

Us old guys are _quite_ dangerous.

[LucenaTheLucid]

Not JUST knowledgeable but hip as well.

Kind of curious how good you are though. =O)

[bob]

Not JUST knowledgeable but hip as well.

Kind of curious how good you are though. =O)

gamertag = crafty48. Feel free to join up for a match or two if you want.

I'm certainly not the best player there. But I am a _long_ way from the worst...

[Clemens Pruell]

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?

Yes, and that's exactly where my bug was, I accidently sorted them
in reverse order [moves with low history/blunder ratio first ...]
Now that the moves are ordered as intended everything seems to work
fine and node count is ok for most positions.
Very big thanks for all your help here.+
Next I'll see whether Null Move could possibly help me with doing 9-plys.

Btw. I sometimes get Instable Search results with my Aspiration Window!
Sometimes when a position must be searched twice (because the bounds of the AW
were wrong) the returned bound will first tell me, that the
result of the search is lower than alpha.
So then I adjust the A/B Window to e.g. -INFINITY/oldAlpha+1.
After doing the second search 99% of the time the value is indeed in the
range of -INFINITY/oldAlpha+1 - as expected!
But very rarely the result of the second search will be oldAlpha+1 (!).
Is this a proof that there must be some more bugs with my Search Function ?
Could the fail-soft AlphaBeta version I use be the reason for this issue, or does/can this
happen with fail-hard AB too? Which parts of the
search / evaluation functions could be responsible for instable search results
(I've not yet looked at PVS or other algorithms of manipulating the
search window because they seem to be even more risky/subject to
instable search results than e.g. AW.)
I'm having trouble figuring out which parts of my search / evaluation
function could possibly be the reason for the instable search results
and whether or how I can reduce the chance of getting a (seemingly...)
impossible fail-high right after a fail-low like the example?

[hgm]

The use of hash-table scores could lead to such search instability. To test if that is the reason, you can require exact-depth hits for hash cutoffs. With the fixed-depth search you do (without null-move and LMR), that should remove all instability completely.

But beware that removing the instability is not good for playing strength. It is better to make the search resistant to such instability, by not assuming the score will be <= alpha if you research after a fail low, but always research {-INF, beta} in that case.

[micron]

Next I'll see whether Null Move could possibly help me with doing 9-plys.

HGM in his first response indicated that your Hash Table hits are extraordinarily low. Getting the hash working properly is more important than null-move or LMR.
You gave an example:

Code: Select all

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

For comparison, here are my engine's stats after an 8-ply search on the same position, in which it found the same move as your engine (I turned off null-move, LMR and PVS to make conditions similar to yours):

Code: Select all

Hash table statistics:
7.7E+5 unique positions saved. 1.5E+6 replacements
2.3E+6 probes
1.2E+6 hits (score used)         53%
2.4E+5 hits (useable move)       10%
4.8E+4 hits (useless)            2%
7.7E+5 misses                    33%

Robert P.

[Clemens Pruell]

Thanks a lot for your comment, it's true: a minor bug in the Position Key Update Function caused that low hash hits. Now I get 200k+ Hits too
VERY BIG THANKS. I wouldn't ever have expected such a serious bug there if it wasn't for your comment !

[Clemens Pruell]

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.

So this means that even a zero-window search must expand at
least 4,170,272 Nodes for any 8-ply search (if no forward pruning
is used) - no matter how good the move ordering may be.
Even if every node either fails low or fails high, there are still so many
all-nodes which just can't be avoided and which need to iterate every
move ... I did a test with a zero-Aspiration Window (when I knew the
correct score in advance) --> ~6 Mio. Nodes for an 8-ply (Iterative Deepening) search.
I'll either try Fail-High Reduction or Null-Move Reduction next, they
seem to be the methods with the lowest risk of overlooking some
unexpected combination. There seem to be good methods of confirming
a beta cut more quickly, but what about all-nodes where no move
can raise alpha ... if only THOSE could be pruned reliably (and without
overlooking e.g. a glorious, 'quiet' queen sacrifice which happens
close to the leaf nodes ...)
There are so many exceptions in Chess that no pruning heuristic seems
to be 100% reliable ...

Thanks for your help.