Magic SEE

[D Sceviour]

H.G.Muller wrote,

That would give you the attackers as an almost free side effect of move generation. For hits of slider on similarly moving slider you would have to continue the move to get the X-ray, which is only slightly more expensive (as such hits occur rarely).

I tried something like that in move generation some time ago but it was abandoned. It is better to calculate the move list as fast as possible with minimal legality tests. This is in hope of a fast cutoff or futility prune. Only after each makemove() in the move list is it safe to proceed with the extra calculations for magics and xrays. Each position is unique AFTER the move.

[hgm]

That implies you cannot sort the moves. If you don't know the sort key for all the moves you want to sort (such as captures) before you start sorting, there is nothing to sort. Just knowing the sort key of the move you are going to search next wouldn't be helpful in any way.

I don't think sacrificing the quality of move ordering to save on calculating x-rays can be a winning tradeoff.

[Michel]

That implies you cannot sort the moves. If you don't know the sort key for all the moves you want to sort (such as captures) before you start sorting, there is nothing to sort. Just knowing the sort key of the move you are going to search next wouldn't be helpful in any way.

I don't think sacrificing the quality of move ordering to save on calculating x-rays can be a winning tradeoff.

I seem to recall someone once tested "Lazy SEE" (SEE without x-rays) on fishtest. Interestingly there was no regression. I don't know if it was ever tested for elo gain.

[hgm]

That is interesting. If x-rays are not worth it, you would never calculate them, of course.

This does kind of fit in with the rarity of cases where presence of KQ matters, and would nicely simplify SEE. The problem I had was that there are 270 combinations of attackers or protectors if you do count x-rays: 2*3*4*3 = 72 K/P/minor/R combinations without Q, also 72 with unbacked Q, 2*3*3*3 = 54 with QB, 2*3*4*2 = 48 with QR and 2*3*4*1 = 24 with QRR. That is just too much to fit in a byte.

[Michel]

It wasn't easy to find but this is it:

https://github.com/official-stockfish/S ... h/pull/365

[mvk]

I never considered simplifying my hashed SEE. When I reprogrammed it for rookie v3, the only requirement I set to myself was "the SEE must put the best move/moves upfront in the move list in at least 99% of the test positions randomly selected from games ("best" as judged by an explicit material search restricted to recaptures on the same square)"

This then led to accounting for pieces pinned against the king and remove them from the attacker and defender lists. Because without that it wouldn't meet the 99%.

[hgm]

Pinning against the King is not the issue. This could be solved in the move generator that supplies the attacker and protector sets.

The question is whether x-ray attacks to the evaluated square should go in. For batteries where the weakest piece goes in front this does not require any special measures, as these don't force an unnatural capture order, and are equivalent to direct attacks. But when Rook(s) or Bishop are x-raying a Queen, the SEE will have to take that into account.

I guess this would lead to differences only when both side have such a 'reversed battery'. E.g. B-behind-Q + R attacking a P protected by R-behind-Q would have SEE = +1 (RxP, QxR, QxQ, RxQ, BxR), while when the x-raying B and R would be swapped, it would be SEE = -1 (RxP, QxR, QxQ, BxR, RxB). If it is not in the course of a Q trade it would never pay to involve Q except for the final move.

I have always been a bit skeptical on how useful deep SEE calculations are, and even whether respecting pins against King is of any importance. For one, pinning against some other pieces (Queen or unprotected Rook) is just as damaging and not any less common. And overloading seems to be a much more common reason for not being able to involve a piece in the exchange than pinning. Many SEE calculations also involve x-raying by enemy pieces ('foe-backing'), and this will make the SEE completely meaningless (as the attackers of the square will be backstabbed on the square they are coming from before they can be involved). Also attackers involved in a SEE can be under attack themselves from other directions, and thus be unreliable: NxP, RxN, BxR looks pretty good (SEE = +1, as the opponent would stop after the first capture). But now suppose the B was attacked by N, and after NxP the opponent would play NxB... Say I could recapture with PxN, so that this was just a 'harmless' trade. Except that now suddenly my already engaged Knight has lost its B protector, and after RxN the SEE = +1 capture lost me a Knight for a Pawn! (Or a Bishop, when I did not recapture that.) The more pieces there are involved in an exchange, the larger the chances that some of them cannot be relied on.

And what is gained by making a SEE correspond to the exact search result limited to captures to the square in 99% of the cases rather than 95% of the cases, when that exact search result matches the full QS outcome only 80% of the time anyway? For move ordering a very shallow scope is often enough; you want to play the moves that won't lose you material in the next two ply, and then you can decide how to continue based on better info than you have now.

[D Sceviour]

If you don't know the sort key for all the moves you want to sort (such as captures) before you start sorting, there is nothing to sort. Just knowing the sort key of the move you are going to search next wouldn't be helpful in any way.

I don't think sacrificing the quality of move ordering to save on calculating x-rays can be a winning tradeoff.

Schooner's Ideal Sort:

1) Principle Variation move
2) Hash best move
3) Mate Killer
4) En Prise captures
5) Good captures in MVV-LVA order
6) Heuristic move - killer move
7) Pawn promotions
8) Bad captures
9) En Passant captures
10)King moves if in check
11)Checking moves if Quiescence
12)Non-capture moves

X-rays and magic's are of no use until condition number 12, and then it is likely the remaining moves are fail-low. A lot of time can be saved by trying the first 11 conditions without extra calculation. Note that the information for testing en prise captures can be taken from the previous lower ply attack-board on the last move. It is not necessary to calculate anything extra during the move generation process.

[hgm]

But how would you know the captures are good? MVV/LVA by itself is a pretty poor sort. Using SEE for the high x low captures works much better. And SEE might benefit from x-rays. You might be tempted to capture a Knight that is attacked by R and Q and only protected by a Rook, if you wouldn't realized that the Rook actually is a battery. While the move deserves to be pruned in QS...

[mvk]

I don't recognise the 80% statistic, it sounds poor. It was my strategy not to compromise on qsearch tree shape because the program will spend most of its time there. This part was done early in the design and of course I had a secondary requirement based on cycles per node as well. Everything can be solved by a generic search, but I want my program to be competitive as well.