Removing Q-search

[matthewlai]

Random idea of the day -

We do QS because of the horizon effect. If we look at all kinds of moves we search in QS - captures, promotions, advanced pawn pushes, maybe checks, they all have something in common - they cause a large change in eval (in the checks case, it changes eval by severely limiting opponent's mobility).

Why not generalize from that, and instead of manually selecting what kind of moves to search in QS, just only search moves that improve eval by at least a certain amount?

We can even have a tapered search. For example -
Depth 0 to -1: Only search moves that improves eval by at least 25cp
Depth -2 to -3: Only search moves that improves eval by at least 50cp
Depth -4 to -inf: Only search moves that improves eval by at least 100cp

It is true that in this case we longer have a termination guarantee, so it may make sense to apply an "irreversible moves only" filter at some depth.

This will allow us to search important reversible moves in the first few plies of QS - some people already include checks which are reversible, but there are other reversible moves like putting rook on 7th or trapping a bishop, that may be beneficial to include in the first few negative plies. These things can easily be worth more than one pawn. Of course, this assumes the eval function to be good enough to see these things.

When I was developing Giraffe my goal was to have as little hardcoded chess knowledge as possible, and the QSearch is one thing that I really wanted to eliminate because of that. I think I finally figured out how.

[matthewlai]

This can be further extended to positive depths as well.

Depth 5-inf: Search all moves
Depth 3-4: Only search moves that improve eval by at least -300cp (or in other words, doesn't make eval drop by more than 300cp)
Depth 1-2: Only search moves that improve eval by at least -100cp
Depth 0: Only search moves that improve eval.

In this case, it will work more or less like a more accurate version of futility pruning (and extended futility, and other similar fun stuff).

Depth 0 here means the point where we stop searching moves that don't improve eval.

[Henk]

Perhaps this may work for Giraffe because it has such a good evaluation. My evaluation is useless for predicting any interesting move.

I remember I tried something like that before but it did not work for Skipper.

[Dann Corbit]

I have a similar idea, which I call BMOBUN
Best move only, back up N times, where N is some constant.

The idea is to have a fast look ahead search, but it does not perform captures only. Instead, it performs the best move only, so it has a branching factor of 1, just like qsearch. But if it fails low, it decrements N, backs up and tries the next best move until N is exhausted, and then returns the reply eval.

The reason I like this idea is that your program is not going to play a long string of captures unless this is what is already in your pv, in which case you will have already searched it.

[Dann Corbit]

IOW, the qsearch is a defective look ahead with a branching factor of 1.
Why not do a fast look ahead that will more closely resemble what you are really going to do?

[THyer]

Top engines already have something very like this.

Here is the Gull derivative "Slizzard" (see http://talkchess.com/forum/viewtopic.php?t=61195): https://bitbucket.org/hyer/sonsofthebir ... ew-default

The function capture_margin_mask determines which "to" squares can lead to a sufficient eval change. This is stored in Current->mask and used to ignore most moves.