Quiescence - Check Evaluation and Depth Control

[Aleks Peshkov]

http://chessprogramming.wikispaces.com/MVV-LVA
MVV/LVA is not about sorting on (victim_value - attacker_value). The difference is very important.

[Sven]

For captures, I basically subtracted the captured piece's value from the attacker's value.

That is not MVV/LVA and also incorrect, see also the other post from Aleks. It needs to be basically the other way round (subtract attacker from victim), and MVV/LVA also means that all moves capturing a queen are tried prior to all moves capturing a rook. This may sound counter-intuitive since you are tempted to calculate something like the "immediate material gain" of a move (assuming the moving piece would be lost afterwards) but the reason why MVV/LVA is better is that trying all moves capturing a queen prior to moves capturing less than a queen (and so on) has been found to shrink the tree more than ordering captures by their "immediate material gain". Example: QxQ has no gain but it is better to search this one prior to NXR since a queen is removed from the board.

Sven

[Cheney]

OK, I'll try that.

With the basic subtraction I did, I then sorted it both ways to test and when I ordered lesser values (into the negative) first, the cuts decreased and the searched nodes went through the roof.

I have read the CPW link but I guess what I am doing is sorting based on LVA first . and nothing else. I'll collect some data, reread the link, and if I am following, sort on MVV first (not leaving the LVA out) and adjust whatever else is needed. Thank you

[lucasart]

OK, I'll try that.

With the basic subtraction I did, I then sorted it both ways to test and when I ordered lesser values (into the negative) first, the cuts decreased and the searched nodes went through the roof.

I have read the CPW link but I guess what I am doing is sorting based on LVA first . and nothing else. I'll collect some data, reread the link, and if I am following, sort on MVV first (not leaving the LVA out) and adjust whatever else is needed. Thank you

Here's a concrete example that might help you to get started with move ordering. Let's take a rather complex position:
[d]r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1
1/ search
Here's a rather crude method to get you started: use the SEE if the move is a capture or promotion, or if the target square of the move is attacked. Otherwise zero (to be improved later with a history table, but let's keep it simple for now). My results (SEE on the left, move on the right)

Code: Select all

300	Bxa6
100	gxh3
0	Nb1
0	Nd1
0	Nb5
0	Nd3
0	Ng4
0	Rb1
0	Rc1
0	Rd1
0	Rf1
0	Rg1
0	Qe3
0	Qg3
0	Qf4
0	Bc1
0	Be3
0	Bf4
0	Bg5
0	Bd1
0	Bf1
0	Bd3
0	Bb5
0	OO
0	Kd1
0	Kf1
0	a3
0	b3
0	g3
0	OOO
0	a4
0	g4
0	dxe6
-100	d6
-200	Nc6
-200	Nxg6
-200	Nxd7
-200	Nxf7
-300	Na4
-300	Bh6
-300	Nc4
-300	Bc4
-400	Qxh3
-700	Qxf6
-700	Qg4
-700	Qd3
-1000	Qh5
-1000	Qf5

2/ qsearch, depth = 0
Here we generate only captures, promotions, and (some) quiet checks. The quiet checks I consider are checks by pieces only (including discovered), as it was simpler to code. My results (MVV/LVA on the left expressed in arbitrary unit, move on the right)

Code: Select all

19	Bxa6
17	Qxf6
12	gxh3
12	dxe6
11	Nxd7
11	Nxg6
11	Nxf7
9	Qxh3

3/ qsearch, depth < 0
Here we generate only captures and promotions, and sort by MVV/LVA. In the present case, the results are identical to 2/, because in this position there are no quiet checks available for white.

[Sven]

OK, I'll try that.

With the basic subtraction I did, I then sorted it both ways to test and when I ordered lesser values (into the negative) first, the cuts decreased and the searched nodes went through the roof.

I have read the CPW link but I guess what I am doing is sorting based on LVA first . and nothing else. I'll collect some data, reread the link, and if I am following, sort on MVV first (not leaving the LVA out) and adjust whatever else is needed. Thank you

Since you wrote "For captures, I basically subtracted the captured piece's value from the attacker's value." you are currently doing MVA, not LVA. That means, you try Qx(any),..., Px(any), then non-captures (here I ignore promotions). LVA would be Px(any), ..., Qx(any), then non-captures. Both ways are already much better than no ordering at all since you try captures prior to non-captures, and the difference between both is probably also smaller than the difference to no ordering at all. But to get MVV/LVA right you definitely need also LVA.

Sven

[bob]

Hi,

I am at the point of building in a qsearch, read a few docs, reviewed a fair amount of posts, and I am puzzled with something going on.

Basically, what I understand is in the normal alphabeta when depth is zero, call the qsearch to playout captures until there are no captures left. This I did. I followed the model on CPWiki.

I also read about having qsearch validate check on the king and if true to then call the alphabeta with depth of 1. This is where the time to complete a search increased drastically. This is because at the end of that alphabeta, qsearch is played again, which can lead to another iteration of alphabeta, and so on. Qsearch is reaching depths around 30 ply.

Is this expected or did I do something wrong?

I am thinking the following:

1. Do not have it validate check . From what I read, this is not a good idea.

2. Validate check and if check is true then call the alphabeta but set a flag so that the alphabeta only makes a move out of check and does not call qsearch again.

3. Implement SEE. It appears SEE will not only sort the capture moves but also only play out the ones that win material. If implemented correctly, it may cut back on the ply.

4. Apply a depth control in qsearch so that it stops at a certain depth.

Thank you for reading and sharing your opinions
-Cheney

A couple of suggestions.

(1) if you extend a checking move when you make the move, rather than when getting out of check, things are a bit simpler. Now you won't normally get to your q-search while in check so that this doesn't become as big a problem.

(2) but when you do that, you STILL have to stop extending on checks at some point, or the search will explode. But at that point, you will once again get to q-search when in check, but here you can take one of two actions:

(a) if you want to escape the check, do so for the first ply of q-search, and then you can look at just captures + checks at the next ply. But if you look at checks at the next ply, you have to look at escapes on the following ply or else the check was wasted. I only allow checks on the first ply of q-search.

(b) alternatively, you can look at checks and check-evasions for the first 2-3-4 plies of q-search and then turn it off. If you go beyond a few plies, this becomes very expensive. It is not cheap, as it is...

[diep]

Hi,

I am at the point of building in a qsearch, read a few docs, reviewed a fair amount of posts, and I am puzzled with something going on.

Basically, what I understand is in the normal alphabeta when depth is zero, call the qsearch to playout captures until there are no captures left. This I did. I followed the model on CPWiki.

I also read about having qsearch validate check on the king and if true to then call the alphabeta with depth of 1. This is where the time to complete a search increased drastically. This is because at the end of that alphabeta, qsearch is played again, which can lead to another iteration of alphabeta, and so on. Qsearch is reaching depths around 30 ply.

Is this expected or did I do something wrong?

I am thinking the following:

1. Do not have it validate check . From what I read, this is not a good idea.

2. Validate check and if check is true then call the alphabeta but set a flag so that the alphabeta only makes a move out of check and does not call qsearch again.

3. Implement SEE. It appears SEE will not only sort the capture moves but also only play out the ones that win material. If implemented correctly, it may cut back on the ply.

4. Apply a depth control in qsearch so that it stops at a certain depth.

Thank you for reading and sharing your opinions
-Cheney

A couple of suggestions.

(1) if you extend a checking move when you make the move, rather than when getting out of check, things are a bit simpler. Now you won't normally get to your q-search while in check so that this doesn't become as big a problem.

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.

It's a simplistic way of looking at it, but it's difficult to refute.

(2) but when you do that, you STILL have to stop extending on checks at some point, or the search will explode. But at that point, you will once again get to q-search when in check, but here you can take one of two actions:

(a) if you want to escape the check, do so for the first ply of q-search, and then you can look at just captures + checks at the next ply. But if you look at checks at the next ply, you have to look at escapes on the following ply or else the check was wasted. I only allow checks on the first ply of q-search.

(b) alternatively, you can look at checks and check-evasions for the first 2-3-4 plies of q-search and then turn it off. If you go beyond a few plies, this becomes very expensive. It is not cheap, as it is...

[syzygy]

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.

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.

[Cheney]

I was thinking today about what I wrote and now realized I wrote wong, I am sorry

I basically subtracted the captured piece's value from the attacker's value

I am subtracting the capturing piece's score from the captured piece's score:

Code: Select all

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

Sorry about the confusion.

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.

Thanks again

[Cheney]

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