Quiescence - Check Evaluation and Depth Control

Discussion of chess software programming and technical issues.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
syzygy
Posts: 5048
Joined: Tue Feb 28, 2012 10:56 pm

Re: Quiescence - Check Evaluation and Depth Control

Post by syzygy » Mon Nov 12, 2012 11:37 pm

Cheney wrote:I have not had any time yet to work on this further but I understand what you are writing :). I will continue with this and enhance it more so that all ???xQ moves are moved frontwards (MVV) and those moves will be ordered based on ??? (LVA); repeat this for all lesser MVV and so on.
To do that, just replace

Code: Select all

move.sortScore = move.capturedpiece.value - move.piece.value; 
by

Code: Select all

move.sortScore = &#40;move.capturedpiece.value << 8&#41; - move.piece.value;
or another shift that is large enough to get the desired effect.

I don't think the improvement is very large, though.

User avatar
lucasart
Posts: 3224
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: Quiescence - Check Evaluation and Depth Control

Post by lucasart » Tue Nov 13, 2012 1:30 pm

Cheney wrote:Hi Lucas,

Thanks for the time with this, too. I have been getting some great help on this thread.

Although I do not have SEE, I understand the basics of it and follow what you are trying to illustrate.

I'll provide some feedback after I play around a bit more with the MVV/LVA to get it sorting correctly :)
Regarding MVV/LVA, it's very simple. What you want is to sort captures by two criterions, in the following order:

Code: Select all

1/ most valuable victim
2/ &#40;when victim have equal value&#41; least valuable attacker
You can modify 1/ to handle promotions. Here's my code for MVV/LVA, if it can help you:

Code: Select all

int mvv_lva&#40;const Board& B, move_t m&#41;
&#123;
	// Queen is the best capture available &#40;King can't be captured since move is legal&#41;
	static const int victim&#91;NB_PIECE+1&#93; = &#123;1, 2, 2, 3, 4, 0, 0&#125;;
	// King is the best attacker &#40;since move is legal&#41; followed by Pawn etc.
	static const int attacker&#91;NB_PIECE&#93; = &#123;4, 3, 3, 2, 1, 5&#125;;

	int victim_value = victim&#91;m.flag&#40;) == EN_PASSANT ? PAWN &#58; B.get_piece_on&#40;m.tsq&#40;))&#93;
		+ &#40;m.flag&#40;) == PROMOTION ? victim&#91;m.prom&#40;)&#93; - victim&#91;PAWN&#93; &#58; 0&#41;;
	int attacker_value = attacker&#91;B.get_piece_on&#40;m.fsq&#40;))&#93;;
	
	return victim_value * 8 + attacker_value;
&#125;
multiplying by 8 is for performance reasons, but any value >= 6 is also correct in the sense that it preserves the ordering.
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

diep
Posts: 1786
Joined: Thu Mar 09, 2006 10:54 pm
Location: The Netherlands
Contact:

Re: Quiescence - Check Evaluation and Depth Control

Post by diep » Tue Nov 13, 2012 4:42 pm

syzygy wrote:
diep wrote:Of course it goes too far for someone who posted a few beginner questions to really go into details, yet i want to post the small remark that if you extend check giving moves in mainsearch rather than check evasions, that you will search in general more nodes.

The simple insight to see why already comes when taking a look at how transpositiontable works.

If we are at position P depthleft D , we give a check get in position Q and extend then we are still at depthleft D.

So we have {P,D} and {Q,D}

In contradiction to that the check evasion manner of extending we end up having {P,D} and {Q,D-1}

the latter will of course get easier a transpositiontable cutoff.
As far as I can see, in both cases you get exactly the same cutoffs. Whenever the search gets to position Q, it will be by a move giving check leading to in-check position Q. Either you store such positions as {Q,D} and look for tt entries {Q,E} with E>=D, or you store such positions as {Q,D-1} and look for tt entries {Q,E-1} still with E>=D.
There are 2 problems with your assumption.
First of all you assume a correct manner to detect checks.
This where the cheapest way to see whether you are in check is to
check the previous move made and just check whether it attacks the king's square.

This goes with a quick table and only in a part of the cases you need to call a function to check this.

That's the fastest way to detect most checks and for fast beancounters it would be nonsense to do it in a different manner.

So it doesn't detect all checks simply.

If you do it in a different manner, your program is slower of course.

That's first flaw in your assumptions.

Secondly it's nonsense to extend all checks with the same amount of plies.
Fractional extensions huh?

Third The King for example used to extend with 2 plies. Yet it's better then to do those extensions when getting out of check as then it's easier to check whether you give the extension.

The path leading to the extensions there is total crucial and determines the extensions - so doing all this in the same manner is not efficient.

In 2 out of those 3 cases we can prove it's faster more efficient nodewise to extend solely check evasions and in the third case it's more convenient.

Diep's evaluation function does not evaluate when being in check to give one example and if you check ICCA publications you'll find an article of Chrilly Donninger about how to extend in an effective manner. The ideal moment for that would be for example the ply after the check. Those extensions are difficult to trigger when being in check.
Of course one difference is that that {Q,D-1} will be overwritten more easily than {Q,D} by other positions. The question is then which of D-1 and D correlates best with the actual work involved in searching position Q.

syzygy
Posts: 5048
Joined: Tue Feb 28, 2012 10:56 pm

Re: Quiescence - Check Evaluation and Depth Control

Post by syzygy » Tue Nov 13, 2012 7:32 pm

diep wrote:
syzygy wrote:
diep wrote:Of course it goes too far for someone who posted a few beginner questions to really go into details, yet i want to post the small remark that if you extend check giving moves in mainsearch rather than check evasions, that you will search in general more nodes.

The simple insight to see why already comes when taking a look at how transpositiontable works.

If we are at position P depthleft D , we give a check get in position Q and extend then we are still at depthleft D.

So we have {P,D} and {Q,D}

In contradiction to that the check evasion manner of extending we end up having {P,D} and {Q,D-1}

the latter will of course get easier a transpositiontable cutoff.
As far as I can see, in both cases you get exactly the same cutoffs. Whenever the search gets to position Q, it will be by a move giving check leading to in-check position Q. Either you store such positions as {Q,D} and look for tt entries {Q,E} with E>=D, or you store such positions as {Q,D-1} and look for tt entries {Q,E-1} still with E>=D.
There are 2 problems with your assumption.
(....)
All this has nothing do to with what you wrote. What you wrote is that the tree gets larger due to the position being stored with depth D instead of D-1 which apparently would lead to fewer transposition cutoffs. This is simply incorrect reasoning.
First of all you assume a correct manner to detect checks.
Yes, that's indeed a very strange assumption that I made!

diep
Posts: 1786
Joined: Thu Mar 09, 2006 10:54 pm
Location: The Netherlands
Contact:

Re: Quiescence - Check Evaluation and Depth Control

Post by diep » Wed Nov 14, 2012 10:59 am

syzygy wrote:
diep wrote:
syzygy wrote:
diep wrote:Of course it goes too far for someone who posted a few beginner questions to really go into details, yet i want to post the small remark that if you extend check giving moves in mainsearch rather than check evasions, that you will search in general more nodes.

The simple insight to see why already comes when taking a look at how transpositiontable works.

If we are at position P depthleft D , we give a check get in position Q and extend then we are still at depthleft D.

So we have {P,D} and {Q,D}

In contradiction to that the check evasion manner of extending we end up having {P,D} and {Q,D-1}

the latter will of course get easier a transpositiontable cutoff.
As far as I can see, in both cases you get exactly the same cutoffs. Whenever the search gets to position Q, it will be by a move giving check leading to in-check position Q. Either you store such positions as {Q,D} and look for tt entries {Q,E} with E>=D, or you store such positions as {Q,D-1} and look for tt entries {Q,E-1} still with E>=D.
There are 2 problems with your assumption.
(....)
All this has nothing do to with what you wrote. What you wrote is that the tree gets larger due to the position being stored with depth D instead of D-1 which apparently would lead to fewer transposition cutoffs. This is simply incorrect reasoning.
What i wrote is factual correct.
First of all you assume a correct manner to detect checks.
Yes, that's indeed a very strange assumption that I made!
Most programs in 90s and also some beancounters i wrote, they are doing the fast manner of checking for a check. It's faster - regardless which datastructure you have.

So in such case you already will see a difference of D versus D-1,
because a search D that didn't detect the check correct will go
from position P to Q with Q being D-1.

Now a different position P' goes to Q detecting the check and will have depth D in position Q when extending giving check moves.

When extending check evasions however you have in both cases D-1 in position Q and things go fine, for example you might get a transpositiontable cutoff, which is what you want of course and when doing the check giving extension, you would not get a transpositiontable cutoff, you have to search it again and waste more nodes.

User avatar
lucasart
Posts: 3224
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: Quiescence - Check Evaluation and Depth Control

Post by lucasart » Wed Nov 14, 2012 1:51 pm

Cheney wrote:Hi Lucas,

Thanks for the time with this, too. I have been getting some great help on this thread.

Although I do not have SEE, I understand the basics of it and follow what you are trying to illustrate.

I'll provide some feedback after I play around a bit more with the MVV/LVA to get it sorting correctly :)
For QS captures, MVV/LVA is a HUGE improvement over randomly sorted moves. I'm in the process of rewriting my engine, and currently in the Qsearch stage too. Example of the qsearch with full window (alpha=-inf, beta=+inf). Note that you cannot reproduce these results because you'd have to have the same eval and same order of move generation. Anyway gives you an idea
[d]r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1
1/ no sorting (moves sorted as they are generated): 1,365,008 nodes. This is GIGANTIC for a qsearch! And I AM using fail soft alpha beta pruning (but nothing else just to avoid mixing too many things at the same time).
2/ MVV/LVA sorting: only 727 nodes!! Feel the difference...

PS: You might wonder what happens without alpha/beta. I have tried, and I couldn't even get the qsearch to complete. I stopped the experiment after 100 M nodes, but I'm sure the number of nodes is just insane. So simply with alpha/beta and a decent move sort, we've obtained exactly the same result as a minmax without optimization in 727 nodes, while the minmax would probably take over a billion nodes (I have no idea what the exact number is surely gigantic). And I didn't even use SEE pruning here (here are no approximations).
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

User avatar
lucasart
Posts: 3224
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: Quiescence - Check Evaluation and Depth Control

Post by lucasart » Wed Nov 14, 2012 2:22 pm

[d]r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1
Now for something a little better:

1/ order check evasions better
- alpha/beta fail soft
- MVV/LVA ordering of captures and promotions
- SEE ordering of check evasions (checks which arise from captures and promotions): if evasion is a capture, or the target square of the evasion move is attacked, use SEE, else 0.
=> nodes = 633

2/ SEE pruning
- alpha/beta fail soft
- MVV/LVA ordering of captures and promotions
- SEE ordering of check evasions (checks which arise from captures and promotions): if evasion is a capture, or the target square of the evasion move is attacked, use SEE, else 0.
- SEE pruning: if (not in check && mov is not check && SEE < 0) skip the move
=> nodes = 126!

Note that 2/ is an approximation, and SEE pruning misses some tactics. Although in practice it has a relatively negligible effect. In this example, the score returned by the qsearch was exactly the same (by pure luck, it's not always true).

I hope this helps you understand qsearch better, and how powerful the combination of alpha/beta and a good move ordering really is!
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

User avatar
lucasart
Posts: 3224
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: Quiescence - Check Evaluation and Depth Control

Post by lucasart » Wed Nov 14, 2012 2:36 pm

Does anyone have examples of positions that lead to qsearch explision ?

Would be very appreciated, as I am currently debugging/improving my (very basic) qsearch.
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

Michel
Posts: 2248
Joined: Sun Sep 28, 2008 11:50 pm

Re: Quiescence - Check Evaluation and Depth Control

Post by Michel » Wed Nov 14, 2012 5:05 pm

Just for curiosity what is your quiescence score on this position?

GNU Chess's score is too high I think since the quiescence search does not see
the concealed threat against Ne5 (it might be a bug).

Jan Brouwer
Posts: 201
Joined: Thu Mar 22, 2007 6:12 pm
Location: Netherlands

Re: Quiescence - Check Evaluation and Depth Control

Post by Jan Brouwer » Wed Nov 14, 2012 10:16 pm

lucasart wrote:Does anyone have examples of positions that lead to qsearch explision ?

Would be very appreciated, as I am currently debugging/improving my (very basic) qsearch.
[d]6Bk/PPPPPp1P/8/7R/7K/8/ppppppQ1/6B1 w - - 0 1

Perhaps not very realistic, but very troublesome...

It takes my program 24M nodes to finish a one ply search.

Post Reply