Removing Q-search

Discussion of chess software programming and technical issues.

Moderators: Harvey Williamson, bob, hgm

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
matthewlai
Posts: 793
Joined: Sun Aug 03, 2014 2:48 am
Location: London, UK
Contact:

Removing Q-search

Post by matthewlai » Fri Sep 02, 2016 1: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.
Disclosure: I work for DeepMind on the AlphaZero project, but everything I say here is personal opinion and does not reflect the views of DeepMind / Alphabet.

matthewlai
Posts: 793
Joined: Sun Aug 03, 2014 2:48 am
Location: London, UK
Contact:

Re: Removing Q-search

Post by matthewlai » Fri Sep 02, 2016 1:43 pm

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.
Disclosure: I work for DeepMind on the AlphaZero project, but everything I say here is personal opinion and does not reflect the views of DeepMind / Alphabet.

Henk
Posts: 6560
Joined: Mon May 27, 2013 8:31 am

Re: Removing Q-search

Post by Henk » Fri Sep 02, 2016 2:29 pm

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
Posts: 11627
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Removing Q-search

Post by Dann Corbit » Fri Sep 02, 2016 5:13 pm

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.
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.

Dann Corbit
Posts: 11627
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Removing Q-search

Post by Dann Corbit » Fri Sep 02, 2016 5:16 pm

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?
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.

THyer
Posts: 40
Joined: Fri Jul 22, 2016 5:51 pm

Re: Removing Q-search

Post by THyer » Fri Sep 02, 2016 6:32 pm

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.
"Wise and cruel was the Bird, and wise and cruel were the Sons of the Bird."

Post Reply