about qs

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.
Daniel Anulliero
Posts: 705
Joined: Fri Jan 04, 2013 3:55 pm
Location: Nice

about qs

Post by Daniel Anulliero » Wed Sep 11, 2013 9:38 pm

hi all

I read that rebel analyze only the winning/equal captures in qs and only queen promo.
Is it for the two sides or only for program side? Because if the oponent find a good sacrifice ("losing" capture) the engine can't see that ,right? (or I mis understand something :-) ? )
And also I think we need to test the incheck moves for that trick right?
Thanks for some light and sorry for my bad english :-)
bye all!

kbhearn
Posts: 411
Joined: Thu Dec 30, 2010 3:48 am

Re: about qs

Post by kbhearn » Wed Sep 11, 2013 11:28 pm

Quiescence search is not meant to be 100% accurate, it's meant to take some of the noise out of evaluating positions. Since most losing captures are in fact losing, and there's a lot more of them than good captures, you shrink the tree by a large factor by not considering them in quiescence allowing your search to reach a depth where it will spot the 'good sacrifice' and give proper thought to various defending lines quicker.

Checks are included in some but not all quiescent searches, often with strings attached (such as see > 0, only first N ply of quiescence). Also in some programs the line between the main search and quiescent search is really blurred as the last few plies of the main search are really like a slightly broader quiescent search, including some moves that the normal quiescent search ignores, trying to wrap up quickly. But it also may exclude a large portion of the move list on the grounds that there's not enough search space left to give proper consideration to apparently-losing moves and find out that they're not.

Daniel Anulliero
Posts: 705
Joined: Fri Jan 04, 2013 3:55 pm
Location: Nice

Re: about qs

Post by Daniel Anulliero » Thu Sep 12, 2013 8:53 am

hi all

Ok thanks I understand now;-)
I will try something like that because I often have a qs explosion :-)
Bye all!

Sven
Posts: 3883
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: about qs

Post by Sven » Thu Sep 12, 2013 4:58 pm

Daniel Anulliero wrote:hi all

Ok thanks I understand now;-)
I will try something like that because I often have a qs explosion :-)
Bye all!
Skipping losing captures in QS is definitely an improvement but I am not so sure about the "large factor" mentioned by Kevin.

A common reason for a QS explosion is bad move ordering, instead. If you correctly follow the MVV/LVA rule then you should not suffer from QS explosions. Try captures of the most-valued victim first, and among different moves with the same victim value, try those with the least-valued aggressor first. I.e., try QxQ prior to NxR prio to RxR prior to PxB etc., even though NxR and PxB are "winning" captures (but QxQ and RxR usually help to cut down the remaining tree faster). Non-capturing promotions could be put to the end of the move list since it is not clear whether the promotion piece will be lost immediately; if it is lost then the promotion move often loses a pawn. Also promotions do not help to cut down the remaining tree, they even tend to blow it up. Many programs only try promotions to a queen during QS.

If move ordering works well then you can add the skipping of losing captures and see how much of an improvement you get. But be careful: you need to be sufficiently sure that QxP, for instance, does not simply win a hanging pawn. Many programmers use SEE to support this decision.

Regarding your other question:
And also I think we need to test the incheck moves for that trick right?
In QS you will usually detect being in check, and generate all legal check evasions in that case instead of generating only captures. This is mainly to avoid missing that you are checkmated. But being in check obviously requires that the opponent makes a checking move. To prevent QS explosion you will avoid to generate all quiet checking moves so that during QS the only "in check" situations (except for the QS root node which can be reached through a quiet checking move at the parent node which belongs to full-width search) may arise after a capture or promotion that also gives check. The only exception which is made in many engines is the first ply of QS. Considering also quiet checking moves in the first QS ply is usually a strength improvement since it helps to see some more tactics. But it is not absolutely necessary, and now to your question, it is also not necessary for the "skip losing captures" improvement.

Sven

xmas79
Posts: 286
Joined: Mon Jun 03, 2013 5:05 pm
Location: Italy

Re: about qs

Post by xmas79 » Thu Sep 12, 2013 6:01 pm

Hi,
in my qsearch I actually allow only 1 check extension along the whole qsearch, so I'm not limiting it to the first ply. My idea was that qsearch is to remove tactics, and some tactics can happen after a few trades:
1) PxP, NxP, Queen checks, King moves, QxN is a sequence that I allow
2) Queen checks, king moves, PxP and then NxP is not played because opponent stand pat.

This clearly makes my q-search tree bigger, but I think it could catch more tactics.

Am I missing something? Am I wrong? Is my tree really big by a far amount so that I have to change this?

Best regards,
Natale.

bob
Posts: 20918
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: about qs

Post by bob » Fri Sep 13, 2013 2:09 am

xmas79 wrote:Hi,
in my qsearch I actually allow only 1 check extension along the whole qsearch, so I'm not limiting it to the first ply. My idea was that qsearch is to remove tactics, and some tactics can happen after a few trades:
1) PxP, NxP, Queen checks, King moves, QxN is a sequence that I allow
2) Queen checks, king moves, PxP and then NxP is not played because opponent stand pat.

This clearly makes my q-search tree bigger, but I think it could catch more tactics.

Am I missing something? Am I wrong? Is my tree really big by a far amount so that I have to change this?

Best regards,
Natale.
There is a flaw here. Your "check" can't win material, because at the previous ply, your opponent could "stand pat" thanks to being in the q-search. That's why most do checks at the first q-search ply mainly, or possibly plies 1 AND 3, because if you check at ply 1 of the q-search, your opponent can't stand pat assuming you do a normal full-width check evasion search there...

Daniel Anulliero
Posts: 705
Joined: Fri Jan 04, 2013 3:55 pm
Location: Nice

Re: about qs

Post by Daniel Anulliero » Fri Sep 13, 2013 6:10 am

hi all!
First , thanks to all for your great explanations! :-)
So yesterday I changed my qs (just winnings and equal capture) after compiling Iran a self test (100 games 1'+1) ...And after 60 games the result was so disapointing : 70% for "full qs version".... and this morning I noticed a silly bug in my gen_capture : I wrote if (val_piece [to] > val_piece [from]) instead of >= :-) pfff... now I must retest!:-)
bye all and thx again !

Sven
Posts: 3883
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: about qs

Post by Sven » Fri Sep 13, 2013 7:20 am

xmas79 wrote:in my qsearch I actually allow only 1 check extension along the whole qsearch, so I'm not limiting it to the first ply.
Let's use the correct terms in the context of QS:

a) "Check extension" means to search one ply deeper than you would normally do. This mainly applies to full-width search where you have a remaining depth. The term can also be applied in QS but is not very meaningful there, it could be interpreted as item b) below but I would not call that a "check extension" just to avoid confusion.

b) "Searching all legal evasions when being in check", so whenever the moving side is in check in QS (caused by a capture or a quiet check) you do a full-width search of exactly 1 ply.

c) "Searching also quiet moves that give check in addition to captures", which is also something that I would not call "check extension".

The recommendation is to always do b), and to limit c) to the first QS ply, or as Bob wrote, maybe also the third QS ply (the second ply does not make much sense).

Now are you talking about a), b) or c) in case of your engine?

Sven

Sven
Posts: 3883
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: about qs

Post by Sven » Fri Sep 13, 2013 7:41 am

Daniel Anulliero wrote:hi all!
First , thanks to all for your great explanations! :-)
So yesterday I changed my qs (just winnings and equal capture) after compiling Iran a self test (100 games 1'+1) ...And after 60 games the result was so disapointing : 70% for "full qs version".... and this morning I noticed a silly bug in my gen_capture : I wrote if (val_piece [to] > val_piece [from]) instead of >= :-) pfff... now I must retest!:-)
bye all and thx again !
Hi Daniel,

as I wrote above, skipping "losing captures" is not about skipping all QxP, RxN, etc. captures just because of piece_val[piece[to]] < piece_val[piece[from]]. This would skip way too much and would actually lead to clearly weaker play since your engine would miss a lot of simple tactics: many blunders in the last full-width ply would not be punished by capturing the hanging piece. You need to check whether a "potentially losing capture" like QxP, RxN is actually "most probably a losing capture". Only skip those captures where you are almost sure that they are actually "losing". This can be done in several ways, e.g. by testing if the lower-valued victim is protected by a pawn, or by implementing SEE which is a bit more accurate.

Your bugfix is necessary, of course, but I'd guess the improvement will not be huge unless you implement the point above. You currently also exclude equal captures which is even worse than excluding all captures of a lower-values piece, but after fixing that the main problem will remain - at least if I understood correctly what you wrote.

As another improvement, I would also consider to move the code to skip "losing captures" from your move generator into the context of your search. The reason is speed: you do not need to perform this "is it a losing capture?" check for moves that are never tried in the search due to a cutoff, and this will save a lot of work.

Sven

Daniel Anulliero
Posts: 705
Joined: Fri Jan 04, 2013 3:55 pm
Location: Nice

Re: about qs

Post by Daniel Anulliero » Fri Sep 13, 2013 2:33 pm

hi sven !
Thanks again for your good explanations !
Ok qs is not that simple ..;-)
In my program I have a routine "square_atacked (side, sq) " .This function compute all the atackers from the color "side" on square "sq" with p=1, n=3, b=3, R=5, q=9. It compute with xrays (if a bishop behind a queen on diagonal or a rook behind a queen on a row etc...)
I thought to try testing each captures with the routine : (example with white capture )
pseudo code :

make_capture ()
if (square_atacked (white, sq) - square_atacked (black, sq) < 0)
skip capture


is it a pseudo SEE ?
is SEE time consuming ?

Well maybe I have something wrong with my mva\lva too...
bye all ![/code]

Post Reply