Evasion (capture) moves ordering by See

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.
Post Reply
tomitank
Posts: 273
Joined: Sat Mar 04, 2017 11:24 am
Location: Hungary

Evasion (capture) moves ordering by See

Post by tomitank » Sun Aug 06, 2017 11:18 pm

Evasion (capture) moves ordering by See

Someone tried it?

Most engine only use MVV-LVA + History score

Sometimes i get another move, when i use it.

-Tamas

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

Re: Evasion (capture) moves ordering by See

Post by Sven » Mon Aug 07, 2017 7:46 am

tomitank wrote:Evasion (capture) moves ordering by See

Someone tried it?

Most engine only use MVV-LVA + History score
In contrast to using SEE, ordering captures by MVV-LVA means, for instance, to prefer trading queens over winning a rook (or less). This will usually lead to a smaller tree size. The typical use case for SEE is the detection of losing captures which can be skipped in QS and postponed in full-width search.

Using history score is a completely different topic, this typically applies to quiet moves only.

What do you mean by "Evasion (capture) moves"?
tomitank wrote:Sometimes i get another move, when i use it.
I do not understand what you mean, could you explain, please?

User avatar
hgm
Posts: 26531
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Evasion (capture) moves ordering by See

Post by hgm » Mon Aug 07, 2017 8:49 am

The normal way to use SEE is to substitute the SEE value for the victim value on High x Low captures only, before ordering MVV/LVA. In practice the sorting is best done through extraction of the next move in the ordering when you need it; if you discover at that point that the next move is a HxL capture, you can run a SEE to test how much (if any) the sort key suffers, and correct the sort key accordingly before deciding if you want to pick that move. That avoids running SEE on moves you never might get to because of a beta cutoff.

If the engine is 'threat-aware' you can increment the sort key of any capture of the threatening piece, or any capture (or move) with the threat victim with the SEE value of the threat. This can make it wortwhile to sort some non-captures with the captures. After all, it makes little sense to try PxR when your own Queen is hanging, and moving the Queen to safety will almost always be a better move.

It is rather difficult to be threat-aware, however. Exactly because of the MVV/LVA ordering the move that refutes your null move will usually not be the true threat, as the latter is masked by trading of higher-valued pieces. E.g. if your Knight is attacked by a Pawn, so that not acting against that will lose you a piece, your null move will be likely refuted by QxQ or RxR, via a line 1. null QxQ 2. PxQ RxR 3. RxR PxN 4. stand-pat {fail low}. Trying to prevent this QxQ or RxR will still lose you the Knight, even earlier in the line. So although you can use null move to detect whether there is a threat, it cannot be used to find what the threat is.

User avatar
Evert
Posts: 2929
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: Evasion (capture) moves ordering by See

Post by Evert » Mon Aug 07, 2017 10:23 am

hgm wrote: It is rather difficult to be threat-aware, however. Exactly because of the MVV/LVA ordering the move that refutes your null move will usually not be the true threat, as the latter is masked by trading of higher-valued pieces. E.g. if your Knight is attacked by a Pawn, so that not acting against that will lose you a piece, your null move will be likely refuted by QxQ or RxR, via a line 1. null QxQ 2. PxQ RxR 3. RxR PxN 4. stand-pat {fail low}. Trying to prevent this QxQ or RxR will still lose you the Knight, even earlier in the line. So although you can use null move to detect whether there is a threat, it cannot be used to find what the threat is.
So what if you change move ordering after a null-move to prefer capturing undefended pieces? That would make you thread aware (at the cost of doing a SEE-like ordering rather than MVV/LVA, which is cheaper).

User avatar
hgm
Posts: 26531
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Evasion (capture) moves ordering by See

Post by hgm » Mon Aug 07, 2017 12:17 pm

This still is no fool-proof method, as often the opponent's Q or R that you should trade first can start to wreck havoc when you leave it on the board to capture the Knight. A Queen can attack lots of stuff, and some of it might be unprotected. If QxQ is possible you already know for sure it attacks your Q.

A better solution could be to propagate the 'gain move' towards the root across the equal trades. This is a bit tricky, because you are not dealing with a single branch, but with a refutation tree. If a threat against you made the null move fail low, the opponent will be playing the cut-nodes, and you will be playing the all-nodes. In the all-node after PxN you could notice that you were not able to capture anything with the value of a Knight, which (together with the fact that you failed low) elevates the PxN to the status of 'gain move'. In the all-node after RxR you could recapture the Rook, but this fails low, and the search passes you PxN as gain move. Because you recaptured the material lost in the preceding RxR, that RxR does not superceed it as gain move.

You might have multiple ways to recapture the Rook (which you will all try in the all-node), but they likely all return the same PxN as gain move. It would be tricky if they had to be refuted in a different way, e.g. you could recapture with a Pawn and lose the Knight, or you could recapture with that Knight and then lose a Rook because that Knight was pinned on that Rook by a Bishop. You could assume here that you would prefer to suffer the lowest loss here, so keep the PxN as gain move.

But you will also have moves that do not recapture the Rook, which in general than would lose you a Rook If you really had no way at all to recapture the Rook, the preceding RxR would become a gain move. But because losing a Knight is better than losing a Rook, the PxN prevails.

In the end this would pass PxN as gain move to the null-move-reply node. In the parent this could then be seen as the threat move, and capture of the P or moving the N as possible cures , which deserve to be searched earlier.

It would be a bit more complex if the gain move was N x unprotected N, and the N became unprotected because of the piece protecting it (say a P) being used to recapture the R after RxR. In this case preventing the RxR would also have helped to save your Knight. But it still doesn't seem wrong to identify NxN as gain move here; it is just that you overlooked some alternative ways to solve the threat, because you only upgrade the priority of moves that capture the attacker or withdraw the victim. And not moves that interpose, protect the victim, solve the overloading or (soft)pinning of existing protectors, etc.

tomitank
Posts: 273
Joined: Sat Mar 04, 2017 11:24 am
Location: Hungary

Re: Evasion (capture) moves ordering by See

Post by tomitank » Mon Aug 07, 2017 8:20 pm

Using history score is a completely different topic, this typically applies to quiet moves only.
This is ok for quiet moves.
What do you mean by "Evasion (capture) moves"?
Evasion (capture) moves = evasion non quiet moves :)

I use currently see pruning in Qsearch when i'm not in check.

When i'm in check, i generate all evasion moves.
When i non quiet moves ordered by "see" algorithm, so (sometimes) i get different PV.
I think, because different move cause the cut.

-Tamas

User avatar
hgm
Posts: 26531
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Evasion (capture) moves ordering by See

Post by hgm » Mon Aug 07, 2017 9:21 pm

So you are talking about check evasions?

I don't think it would be much different from when you are not in check. Normal history would probably not help, though. Ordering non-capture evasions (interpositions or King withdrawal) so the SEE=0 moves are tried before those that lose material is not a crazy idea. The SEE=0 moves could further be ordered by resulting King Safety.

Note that cut nodes are never on the PV. Move ordering should not affect the PV, unless you get hash grafting to change the value of some branches because they effectively look deeper than requested.

tomitank
Posts: 273
Joined: Sat Mar 04, 2017 11:24 am
Location: Hungary

Re: Evasion (capture) moves ordering by See

Post by tomitank » Mon Aug 07, 2017 11:09 pm

the SEE=0 moves are tried before those that lose material is not a crazy idea.
It happened accidentally.. :)
I'll see if it's better or not.

Post Reply