Removing Q-search
Posted: Fri Sep 02, 2016 3:15 pm
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.
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.