Michel wrote:
There are no continuous parameters to be tuned. But SEE is expensive and it makes sense to try to truncate it to speed up things. This is something that could be tunable. I recall that somebody at fishtest experimented with this, but it was elo neutral and therefore rejected (although it was a simplification in terms of LOC).
That would be some kind of futility pruning for SEE? Interesting idea, although I would think that you end up saving very little (because you'd only be able to do that near the end of the line, when most of the work is already done and the futility pruning code itself is not free).
I use two things to speed up SEE: early exit if the first capture is lowxhigh (the sequence is always winning, so we know SEE>0) and a cache. The latter I know is a (smallish) gain because I tested it. The first I don't think I ever tested, but that wouldn't be so useful to test anyway.
SEE is a normal minimax search where the only 'moves' are stand-pat or capture to the given square with the lowest attacker. So all techniques that speed up minimax can in principle also be applied to SEE. In particular alpha-beta. In this case the only beta cutoff can occur after stand-pat, saving you the trouble to try the next-in-line capture.
Futility pruning is basically just an early stand-pat on a lazy eval. As the evaluation in SEE is trivial and accounted incrementally, the stand-pat test can be moved to the 'parent node' (= previous iteration in an iterative implementation) without any loss of accuracy.
Just wanted to thank you guys for the replies. I ended up implementing SEE with the most basic piece values you learn as a beginner (100, 300, 300, 450, 900, a large number for the king). It was certainly more work then the 3 lines of code it took me to implement futility pruning earlier this week (after understanding it it feels embarrassing I didn't implement futility pruning earlier...) however the gain was pretty huge, clocking in at over 50 elo in self play. If I had to estimate my engine's CCRL rating it would now be rather close to my own FIDE rating, so maybe if I find time I will do a human vs computer tournament time control match in the future .
nionita wrote:
Excellent point, this one with (no) check extension in end game. I will try this one for sure.
Unfortunately this one was a clear loss of at least 10 Elo with 95% (more probably 20 Elo, but I don't want to spend more CPU on it to know exactly how much).
The condition was: if move checks && side to move has queen - extend 1 ply.
In micro-Max King Safety and Check extension are not just dependent on presence of the Queen, but on game phase (basically total non-Pawn material). If this drops below a certain value (I think <= 2 Queens + 1 minor), the King gets drawn towards the center, and check extension is switched off.
hgm wrote:In micro-Max King Safety and Check extension are not just dependent on presence of the Queen, but on game phase (basically total non-Pawn material). If this drops below a certain value (I think <= 2 Queens + 1 minor), the King gets drawn towards the center, and check extension is switched off.
I can imagine that when there are less pieces the king is more exposed and combinations of check and piece captures (for example with a rook) get more frequently. This could be one explanation why it is still important to extend, although my king safety gets 0 with no opponent queen.
There could still be a difference between extending in horizon nodes only, and everywhere in the tree. The problem is that when the King gets exposed, because it is safe to march it to the center, there will always be extremely long sequences of checks. They usually lead nowhere, but when they get extended to twice the nominal depth, they will eat virtually all the nodes.
If a fork or skewer on the King occur well within the tree, the subsequent loss of the other piece will be within the horizon, and you won't need an extension to see it. Only in horizon nodes there is a danger that you will overlook these tactics.
Micro-Max is never check-aware in QS. (It gets the in-check info from the null-move search, which is too expensive in QS). So switching off check extension does not hurt it in this respect. This might explain the difference.
.