http://chessprogramming.wikispaces.com/MVV-LVA
MVV/LVA is not about sorting on (victim_value - attacker_value). The difference is very important.
Quiescence - Check Evaluation and Depth Control
Moderators: hgm, Rebel, chrisw
-
- Posts: 892
- Joined: Sun Nov 19, 2006 9:16 pm
- Location: Russia
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Quiescence - Check Evaluation and Depth Control
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.Cheney wrote:For captures, I basically subtracted the captured piece's value from the attacker's value.
Sven
-
- Posts: 104
- Joined: Thu Sep 27, 2012 2:24 am
Re: Quiescence - Check Evaluation and Depth Control
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
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
-
- Posts: 3232
- Joined: Mon May 31, 2010 1:29 pm
- Full name: lucasart
Re: Quiescence - Check Evaluation and Depth Control
Here's a concrete example that might help you to get started with move ordering. Let's take a rather complex position:Cheney wrote: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
[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
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
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.
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Quiescence - Check Evaluation and Depth Control
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.Cheney wrote: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
Sven
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Quiescence - Check Evaluation and Depth Control
A couple of suggestions.Cheney wrote: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
(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...
-
- Posts: 1822
- Joined: Thu Mar 09, 2006 11:54 pm
- Location: The Netherlands
Re: Quiescence - Check Evaluation and Depth Control
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.bob wrote:A couple of suggestions.Cheney wrote: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
(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.
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...
-
- Posts: 5563
- Joined: Tue Feb 28, 2012 11:56 pm
Re: Quiescence - Check Evaluation and Depth Control
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.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.
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.
-
- Posts: 104
- Joined: Thu Sep 27, 2012 2:24 am
Re: Quiescence - Check Evaluation and Depth Control
I was thinking today about what I wrote and now realized I wrote wong, I am sorry
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
I am subtracting the capturing piece's score from the captured piece's score:I basically subtracted the captured piece's value from the attacker's value
Code: Select all
move.sortScore = move.capturedpiece.value - move.piece.value;
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
-
- Posts: 104
- Joined: Thu Sep 27, 2012 2:24 am
Re: Quiescence - Check Evaluation and Depth Control
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
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