MVV/LVA move ordering and qSearch

Discussion of chess software programming and technical issues.

Moderator: Ras

Uri Blass
Posts: 10895
Joined: Thu Mar 09, 2006 12:37 am
Location: Tel-Aviv Israel

Re: MVV/LVA move ordering and qSearch - real data

Post by Uri Blass »

mcostalba wrote:
Uri Blass wrote: I cannot believe that PxN is better in most of the cases and it is still better to search first QxQ(see=0)

In theory it can be correct because of smaller tree after inferior QxQ but I think that in this case the right solution is to be more aggresive in reductions after PxN and not to search the inferior move first.
Uri you miss the point that in qsearch you have very often hanging pieces. If you do some statistic you will be surprised by how much positions with hanging pieces you have in qsearch.

QXQ is _always_ the best move when the capturing queen is undefended. You cannot try PxN before, otherwise you lose your queen.
I do not miss that point
This was exactly the reason that I expected QxQ(see=0) to be the best move more often than PxN.

My intuition clearly told me that the case that the queen is hanging may happen often but Bob told me that my intuition is wrong and PxN is usually better than QxQ(see=0) so I continue the discussion based on his assumption that is that PxN is better in most cases and the cases when the queen is hanging are relatively rare.

Uri
Uri Blass
Posts: 10895
Joined: Thu Mar 09, 2006 12:37 am
Location: Tel-Aviv Israel

Re: MVV/LVA move ordering and qSearch - real data

Post by Uri Blass »

I can add that I posted in the end of page 3 a diagram when the queen is hanging to explain why I expected QxQ(see=0) to be the better move in most cases.

Maybe my assumption that Bob has no bug in his code to calculate statistics is wrong so it may be better if bob generate some epd files of positions when QxQ(see=0) and PxN are possible in the qsearch when there are basically 4 different files

1)both moves fail high in the qsearch
2)both moves fail low in the qsearch
3)only QxQ fail high in the qsearch(PxN does not fail high relative to the same beta)
4)PxN fail high in the qsearch(Crafty searched earlier QxQ and it failed low)

Bob's claim is that 4 happens more often than 3.

I stopped working on movei so I am not going to calculate statistics for movei but it may be interesting to have statistics for other programs.

Uri
Michael Sherwin
Posts: 3196
Joined: Fri May 26, 2006 3:00 am
Location: WY, USA
Full name: Michael Sherwin

Re: MVV/LVA move ordering and qSearch

Post by Michael Sherwin »

Fguy64 wrote:OK, if your Qsearch is just a straight-up capture search, then MVV/LVA is touted as a means to prevent "explosions. Now MVV/LVA is a 2-key sort first a descending sort on the value of the victim, then an ascending sort on the value of the attacker.

Is there any reason why we can't just sort on the value of the difference between the attacker an the defender. In this second case, PxN would be ordered before QxQ, whereas this would not happen with MVV/LVA.

Anyways, the point is that my idea would involve only a single key sort, which presents certain logistical advantages.

Now, when it comes to alpha/beta search, explosions aren't an issue, and we are free to play a bit with move ordering. Not so with Qsearch is my impression.
Since what I do in RomiChess is a little different I will put in my $.02.

During capture generation the attacked squares are noted.

Then the captures are sorted like this:

sortValue = value of victim;

if(ts was attacked by the enemy && ts was not last ply's ts)
sortValue -= value of attacker;

The philosophy is this:

trade accuracy for time.

example 1:

A queen moves. Most of the time, especially in the end game, the queen was the only piece attacking that square. So, do not subtract the attacker.

example 2:

A queen is captured that did not just move, however, the square was not attacked. So, do not subtract the attacker.

example 3:

A queen is captured that did not just move, however, the square is attacked. So, subtract the attacker.


This is more accurate than it might seem and very very fast. IMO.
If you are on a sidewalk and the covid goes beep beep
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
bob
Posts: 20943
Joined: Mon Feb 27, 2006 7:30 pm
Location: Birmingham, AL

Re: MVV/LVA move ordering and qSearch - real data

Post by bob »

Uri Blass wrote:
bob wrote:
Uri Blass wrote:
bob wrote:
Uri Blass wrote:<snipped>
bob wrote: I don't have any "expectation" unless you want to use some sort of "quick evaluation" (or the stand-pat score in a q-search). And even then what I expect to happen often does not, there is no perfect move ordering in the chess tree. I use this very idea to try to avoid parallel search splits where I expect a fail high, but I am often wrong.

I think about expectation based on order of moves(maybe it has a name beta type nodes or alpha type nodes but I am not sure about definitions in computer chess)

The idea is to have a list of the place of the moves in the move list and use this information to predict fail high and fail low with the idea that not first moves usually fail low.

For example in the opening position.

Suppose that you search the line 1.a4 e5 2.a5 d5 and go to qsearch with white to move


1.a4 is move number 7 in the move list for white that you searched
1...e5 is move number 1 in the move list for black that you searched
2.a5 is move number 8 in the move list for white that you searched
2...d5 is move number 1 in the move list for black that you searched

You have the following list of numbers
7,1,8,1

You can expect the qsearch to fail low

The general rule is simple
If the last number in your list is bigger than 1 you can expect the move to fail high
If the last number in your list is 1 and the previous number is bigger than 1 you can expect the move to fail low.

If the last 2 numbers are 1 then you should calculate your expectation based on the sequence without the last 2 numbers so sequence like
7,1,8,1,1,1 can be translated to 7,1,8,1 and qsearch fail low expectation
when sequence like 7,1,8,2,1,1 can be translated to 7,1,8.2 and qsearch fail high expectation.

The cases that you cannot decide because all the numbers are 1 are rare and it is not very important what is your expectation in them.

Uri
OK, that is the basic idea behind "Young Brothers Wait" in parallel search. Once the first move is completed and it doesn't fail high, there is a very high probability that this is an ALL node. But in the q-search, where we are talking about this MVV/LVA stuff, this doesn't work, because there are very few moves to search. And we are not trying to find the "best" move at a ply to search, we are trying to find the best capture instead. Except the definition of "best" has changed. Given QxQ (even) or PxN (win a piece), PxN is better. But MVV/LVA gives better results with ordering. So it isn't about "expectation" or anything else, it is about removing heavy pieces first. Which is counter-intuitive I agree, but it works because it has been tested by several, including myself.

If anyone can propose a different reason why it is better to search QxQ before PxN, when SEE says QxQ wins _less_ than PxN, then I'm all for hearing it. Intuition says this is wrong. Actual experimental results say it is correct.
1)You can still have different statistics for all nodes and for other nodes in the qsearch based on what happened earlier.

If you already search RxQ and it failed low in the qsearch then you can fully expect fail low for QxQ so it is probably all node.

If QxQ is the first move in the qsearch then you need to go to earlier plies to decide if it is all nodes or not all nodes

My point is that statistics of better move may be different in fail high nodes and in other nodes.


2)I think that there is a possibility that QxQ(see=0) wins more material than PxN in the cases when both moves fail high so it cause QxQ to generate a smaller tree.

I cannot believe that PxN is better in most of the cases and it is still better to search first QxQ(see=0)

In theory it can be correct because of smaller tree after inferior QxQ but I think that in this case the right solution is to be more aggresive in reductions after PxN and not to search the inferior move first.

Uri
There are no reductions after PxN. We are talking q-search. Just captures, + checks (in my case), or getting out of checks only at the 2nd ply of q-search.
You can still have smaller qsearch.

For example not allowing equal captures in the qsearch in part of the cases when the score is bad for the side to move.

The point is that if the qsearch started with PxN then the position is bad for the side to move and in case that QxQ is an equal capture the reply QxQ is probably going to cause fail low so you may decide to skip it
in order to save time.

Uri
Let's return to planet earth for a minute. The question was "Why is playing QxQ, better according to MVV/LVA, better than playing PxN, better according to SEE, producing overall smaller game trees, which is the _only_ reason for using the combination of MVV/LVA (for those that have not followed, the current approach used by many is to order captures by MVV/LVA, and just before playing one, check the SEE score. If this is < zero, then this capture is deferred (in the main search) or eliminated (in the q-search).

One proposition was that QxQ is usually better than PxN, even if QxQ is an even trade while PxN wins material (both of these tested by SEE). This turns out to be incorrect as my test showed.

The only other explanation is that it reduces the size of the tree because you remove heavy pieces which results in fewer captures available in the q-search. This seemed to be consensus months ago, but now some do not agree. I see no other explanation for this working.
bob
Posts: 20943
Joined: Mon Feb 27, 2006 7:30 pm
Location: Birmingham, AL

Re: MVV/LVA move ordering and qSearch - real data

Post by bob »

mcostalba wrote:
Uri Blass wrote: I cannot believe that PxN is better in most of the cases and it is still better to search first QxQ(see=0)

In theory it can be correct because of smaller tree after inferior QxQ but I think that in this case the right solution is to be more aggresive in reductions after PxN and not to search the inferior move first.
Uri you miss the point that in qsearch you have very often hanging pieces. If you do some statistic you will be surprised by how much positions with hanging pieces you have in qsearch.

QXQ is _always_ the best move when the capturing queen is undefended. You cannot try PxN before, otherwise you lose your queen.
Aha, but you didn't look at my original comments. SEE would _always_ search QxQ (Q undefended) before PxN, because QxQ = +900, PxN = +300 at best, perhaps only +200. But we are now trying QxQ first, _always_ because QxQ can't (according to SEE) lose material, it is at worst an even exchange.

I was ordering all captures by SEE up until this discussion cropped up earlier this year. I now use MVV/LVA to order, then as I try captures, I use SEE to postpone/eliminate captures that look bad. And the trees are smaller than the more accurate ordering SEE produces. We are discussing the "why is this true?" question.
bob
Posts: 20943
Joined: Mon Feb 27, 2006 7:30 pm
Location: Birmingham, AL

Re: MVV/LVA move ordering and qSearch - real data

Post by bob »

Uri Blass wrote:
mcostalba wrote:
Uri Blass wrote: I cannot believe that PxN is better in most of the cases and it is still better to search first QxQ(see=0)

In theory it can be correct because of smaller tree after inferior QxQ but I think that in this case the right solution is to be more aggresive in reductions after PxN and not to search the inferior move first.
Uri you miss the point that in qsearch you have very often hanging pieces. If you do some statistic you will be surprised by how much positions with hanging pieces you have in qsearch.

QXQ is _always_ the best move when the capturing queen is undefended. You cannot try PxN before, otherwise you lose your queen.
I do not miss that point
This was exactly the reason that I expected QxQ(see=0) to be the best move more often than PxN.

My intuition clearly told me that the case that the queen is hanging may happen often but Bob told me that my intuition is wrong and PxN is usually better than QxQ(see=0) so I continue the discussion based on his assumption that is that PxN is better in most cases and the cases when the queen is hanging are relatively rare.

Uri
If you look at QxQ, and the SEE is zero, how can the queen be hanging? Impossible, unless SEE is wrong due to a pin or whatever. This is pretty rare (but not impossible). So we know that QxQ (SEE=0) and PxN (SEE = 200 or 300) are both playable at the same time. My data shows PxN is better, since it would fail high 2x more than QxQ would.

So, again, why is the more general case of QxQ over PxN (any big piece exchange that appears to be even in material, over any capture that appears to win material according to SEE) better? We _know_ it is. Or at least I know that from extensive testing. Others apparently know it as well because they used this idea before I did. So why does it work? Certainly not because QxQ is better. My tests in this thread show that is wrong. All that is left is the reduction in tree size as a viable explanation.

But we keep drifting off of that topic.
bob
Posts: 20943
Joined: Mon Feb 27, 2006 7:30 pm
Location: Birmingham, AL

Re: MVV/LVA move ordering and qSearch - real data

Post by bob »

Uri Blass wrote:I can add that I posted in the end of page 3 a diagram when the queen is hanging to explain why I expected QxQ(see=0) to be the better move in most cases.

Maybe my assumption that Bob has no bug in his code to calculate statistics is wrong so it may be better if bob generate some epd files of positions when QxQ(see=0) and PxN are possible in the qsearch when there are basically 4 different files

1)both moves fail high in the qsearch
2)both moves fail low in the qsearch
3)only QxQ fail high in the qsearch(PxN does not fail high relative to the same beta)
4)PxN fail high in the qsearch(Crafty searched earlier QxQ and it failed low)

Bob's claim is that 4 happens more often than 3.

I stopped working on movei so I am not going to calculate statistics for movei but it may be interesting to have statistics for other programs.

Uri
Why don't you think about what I wrote for a minute? There is no bug in this code. It added all of 6 lines of code. I did not do an all-inclusive test, it would be too messy to deal with. I simply took the case being discussed, (QxQ SEE=0 and PxN SEE=+200 or more) and compared since it was claimed (HGM) that when QxQ (SEE=0) is playable, PxN (SEE = +) is usually a very bad move. That was disproved by a 2-1 margin.

So, the question is, why is capturing the largest piece (when the capture does not lose material) better than making the most profitable capture (again, according to SEE) in the general case? The only distinctive property of a heavy piece is additional mobility and the proclivity for more captures. Getting rid of them as early as possible produces smaller trees.

I do plan on trying pure SEE in q-search, and MVV/LVA-SEE in normal search, to see if that is even better, which it might well be.
Uri Blass
Posts: 10895
Joined: Thu Mar 09, 2006 12:37 am
Location: Tel-Aviv Israel

Re: MVV/LVA move ordering and qSearch - real data

Post by Uri Blass »

<snipped>
bob wrote:
mcostalba wrote: QXQ is _always_ the best move when the capturing queen is undefended. You cannot try PxN before, otherwise you lose your queen.
Aha, but you didn't look at my original comments. SEE would _always_ search QxQ (Q undefended) before PxN, because QxQ = +900, PxN = +300 at best, perhaps only +200. But we are now trying QxQ first, _always_ because QxQ can't (according to SEE) lose material, it is at worst an even exchange.
Marco is talking about the case that the capturing queen is undefended and not about the case that the captured queen is undefended.

From his words:
"QXQ is _always_ the best move when the capturing queen is undefended."

If I understand english correct
the capturing queen means the first queen in QxQ and not the second queen so he is not talking about the case when SEE=+900

Uri
bob
Posts: 20943
Joined: Mon Feb 27, 2006 7:30 pm
Location: Birmingham, AL

Re: MVV/LVA move ordering and qSearch - real data

Post by bob »

Uri Blass wrote:<snipped>
bob wrote:
mcostalba wrote: QXQ is _always_ the best move when the capturing queen is undefended. You cannot try PxN before, otherwise you lose your queen.
Aha, but you didn't look at my original comments. SEE would _always_ search QxQ (Q undefended) before PxN, because QxQ = +900, PxN = +300 at best, perhaps only +200. But we are now trying QxQ first, _always_ because QxQ can't (according to SEE) lose material, it is at worst an even exchange.
Marco is talking about the case that the capturing queen is undefended and not about the case that the captured queen is undefended.

From his words:
"QXQ is _always_ the best move when the capturing queen is undefended."

If I understand english correct
the capturing queen means the first queen in QxQ and not the second queen so he is not talking about the case when SEE=+900

Uri
OK, the "ed" and "ing" ran together. I would probably agree with that, since if you don't play QxQ, your opponent will promptly rip your queen unless he has another capture that wins material _and_ gives check. So it isn't "always" the best move, but most likely is the best move most of the time. For example, given the choice of PxR+, or QxQ, I would probably play PxR+ first, since my opponent is obligated to get out of check, then I trade queens. If I play QxQ first, he might have a checking move to save the rook and then recapture the king, saving the loss of the rook completely.

That's why we leave _those_ decisions to the search, rather than trying to make SEE sophisticated enough to understand.
bob
Posts: 20943
Joined: Mon Feb 27, 2006 7:30 pm
Location: Birmingham, AL

Re: MVV/LVA move ordering and qSearch - real data - more dat

Post by bob »

Running the test with mvv/lva+SEE in normal search, but pure SEE ordering in q-search. Appear to be dead even. SEE is very slightly slower (since it is applied before sorting moves, where in MVV/LVA SEE is deferred until just before a move is actually searched), mvv/lva+see in q-search produces slightly larger trees. It looks like the gain here is in the normal search rather than in the q-search. Have to wait until the tests complete for confirmation, but some quick tests on specific positions shows very little difference.

This is becoming quite convincing that the gain here is due to eliminating a heavy piece with the increased capture potential it has, rather than because QxQ is better than PxN in general.