lucasart wrote:there are 2 interesting positions, on which my engine output a "NoMove" as it couldn't even searching depth 1!
Do you ever extend by more than one ply, deliberately or by accident?
If so, that's probably causing a massive (and pointless) explosion of the search tree.
After a lot of debugging on the first position, I realized that I was facing a quiescent search explosion!
So I read my qsearch again and again, and I finally found the solution in StockFish. I was just pruning see < 0 without distinction, whilst SF does the following SEE pruning in the qsearch
// Detect non-capture evasions that are candidate to be pruned
evasionPrunable = inCheck
&& bestValue > VALUE_MATED_IN_PLY_MAX
&& !pos.move_is_capture(move)
&& !pos.can_castle(pos.side_to_move());
// Don't search moves with negative SEE values
if ( !PvNode
&& (!inCheck || evasionPrunable)
&& move != ttMove
&& !move_is_promotion(move)
&& pos.see_sign(move) < 0)
continue;
So if my search exploded it's probably because of all the useless non capturing check evasions. Also I was brutally pruning see < 0 at PV nodes, which is dangerous (I was even pruning the tt move...)
So after adapting this code (especially because my see does handle promotions unlike SF's), as well as adding 2 killer moves and a mate killer, my WAC score is now 253/300 in 2 sec per move and using 16 MB Hash.
Just out curiosity I wonder who invented this SEE pruning refinement. Was it first seen in SF or were there previous open source program doing that ? Perhaps Crafty ?
It was even in Cray Blitz. But I am not sure that the PV condition makes a lot of sense. The q-search is _filled_ with errors (99% of the time the best move in a position is _not_ a capture or check). Trying to limit a few small errors doesn't, I believe, make any difference. Each time I have tried such things, it either does not help, or hurts very slightly. One classic is whether you do null-moves _everywhere_ or limit it by not trying on PV nodes or whatever and then adding in the verification search idea. I've never found a case where the verification search helps in real games. Only in zugzwang positions, which are rare. I prefer to optimize for the common case, not for oddball ones, if the overall effect is to play better.
Note that SF generates checks and check evasions only at the first two levels of qsearch, at depth 0 and at depth -1. In earlier versions it was only one level. SF also does not use moves from HT besides captures and promotions below those levels.
In case you do checks and check evasions everywhere or in case you try every move from HT in qsearch, then that might be a reason for a qsearch explosion.
Ralph Stoesser wrote:Note that SF generates checks and check evasions only at the first two levels of qsearch, at depth 0 and at depth -1. In earlier versions it was only one level. SF also does not use moves from HT besides captures and promotions below those levels.
In case you do checks and check evasions everywhere or in case you try every move from HT in qsearch, then that might be a reason for a qsearch explosion.
There is another ugly and not well-known bug. IF you hash in the q-search, you can reach a position that was searched in the regular search earlier in the tree, and the HT move might not be a capture or check at all, just the best move in that position from a normal search. If you include _that_ in the q-search, you can expect an explosion.
I assume SF does not do checks at the 2nd q-search ply, although I have not looked. To do so is a wasted effort, since you are hoping that the check wins something, yet at the first q-search ply the opponent could always "stand pat.". I do checks at the first q-search layer, and evasions at the 2nd, but only when the first layer move was a check, since if it wins something the side playing the check would eschew the stand-pat score and take the better checking move score...
bob wrote:
I am not sure that the PV condition makes a lot of sense.
You're probably right! Generally speaking introducing such path dependant conditions is theoretically unsound when used with a htable. So all these pv conditions should be tested, and unless they actually prove usefull, they should be avoided.
I've found however that extending recaptures by 1/2 ply at non PV nodes and 1 ply at PV nodes performs a little (but significantly) better in practice. Probably because:
- on the one hand you have a PV condition which doesn't make sense in theory
- on the other hand extending all recaptures by 1 ply is far too costly and explodes the search tree
- so in the end the result is an overall positive.
I'll try to remove each pv condition and test to see if it is actually useful.
I would like to submit my engine (under developpement) to the famous WAC.epd test. Do you know of a (UCI + Linux) interface that allows that ?
Basically I'm looking for a feature like:
* load positions sequentially
* computer analyzes for X seconds
* compares the best move found by computer to the one indicated in the EPD
* output a score (like 200/300 meaning 200 correct moves out of the 300 WAC.epd positions)
Thank you
PS: here's a position that seems relatively easy for humans but tricky for computers (my engine never finds Rxb2! and Houdini only finds it at depth 20, although it reaches that depth in a couple of seconds...)
[D]8/7p/5k2/5p2/p1p2P2/Pr1pPK2/1P1R3P/8 b - -
WAC002 has always been a challenge for my engine! It was finally able to get it correct after I added check extensions. I'm down to about 34 seconds now, which is a major accomplishment for me:
lucasart wrote: Just out curiosity I wonder who invented this SEE pruning refinement.
The idea to prune useless evasions in qsearch is from Joona and it is original AFAIK.
We also did this in Cray Blitz. But I did not originate the idea. I want to say it was Fred Schwartz (Chaos) but I am not certainly. We've all used SEE to trim the q-search way down.
I don't do it in Crafty because I only have one layer of q-search checks, while in CB we could do more. I don't want to miss mates, which is the only purpose for doing 1 layer of checks/evasions in the first place. Pruning unsafe ones did not help at all in my testing, but pruning unsafe checks was certainly worthwhile.
bob wrote:I assume SF does not do checks at the 2nd q-search ply, although I have not looked. To do so is a wasted effort, since you are hoping that the check wins something, yet at the first q-search ply the opponent could always "stand pat.".
It does, but SF has very strict conditions for delivering checks in qsearch. Non-capturing checking moves are always pruned unless SEE >= 0 and one of the following conditions is fulfilled:
- Stand pat is very close to beta (<= 0.25cp)
- It's a double threat and capturing victim allows us to reach beta
- It's a queen contact check
- Opponent's king has at maximum one escape squares
Using this condition and delivering checks in two q-search plies was the optimal way for us. Not a biggie though, something around 5-10 ELOs. You might want to try something like this in Crafty.
