bob wrote:So at least a factor of 2x, which is 50-70, and I did not remove the extension selection tests or any other uses of Swap(), just q-search...
Time-to-depth speedup for a pruning is not a decisive measure, right? You also lose accuracy, which might cost you Elo. Some of the SEE-wise bad captures you prune actually win material (because a protector was overloaded or soft-pinned, or a capture delivered a discoverd threat), and your search will now miss that.
Besides, SEE is not really necessary for this pruning. With BLIND I make similar prunings too.
Yes, but the question would have to be "how much". The only real way to test is a cluster run, which I will fire up right now. Data this afternoon...
Here's the results. Had too many meetings and then class to check on test earlier:
23.6 is current normal crafty 23.6Q01 has the Swap() code removed from q-search only, so that all captures are searched in usual MVV/LVA order.
Bottom line was 52 Elo roughly, or about 2x slower overall due to larger q-search tree...
I also ran the test with the Swap() test removed from the check extension, so that all checks get extended, not just the ones with SEE >= 0. Q02 is that version:
bob wrote:So at least a factor of 2x, which is 50-70, and I did not remove the extension selection tests or any other uses of Swap(), just q-search...
Time-to-depth speedup for a pruning is not a decisive measure, right? You also lose accuracy, which might cost you Elo. Some of the SEE-wise bad captures you prune actually win material (because a protector was overloaded or soft-pinned, or a capture delivered a discoverd threat), and your search will now miss that.
Besides, SEE is not really necessary for this pruning. With BLIND I make similar prunings too.
Yes, but the question would have to be "how much". The only real way to test is a cluster run, which I will fire up right now. Data this afternoon...
Here's the results. Had too many meetings and then class to check on test earlier:
23.6 is current normal crafty 23.6Q01 has the Swap() code removed from q-search only, so that all captures are searched in usual MVV/LVA order.
Bottom line was 52 Elo roughly, or about 2x slower overall due to larger q-search tree...
The amount of ELO loss will depend a lot of the particular program, but I suspect it would be more for Komodo.
You said it was remove from q-search only. What does that mean? Where else does Crafty use SEE and can you remove it for a test or does the program depend on it for other things?
I may run a test where I simply return "true" regardless to see what happens.
Don
1. I use it to eliminate futile q-search captures (captures that can't bring the base material value back up to at least alpha, the so-called "delta pruning" idea from Cray Blitz days. I compute what the gain has to be to get material back up (down a queen, no need in looking at knight captures, for example). I also use it to eliminate losing captures (queen takes defended pawn and such).
2. I use it to not extend losing checks. These are generally "spite checks" and are a waste of time to follow deeper.
3. I use SEE to recognize losing captures in move ordering, and push the SEE<0 captures down into the "remaining moves" phase of the search, to follow good / even captures and then killers.
The first test disabled 1. The second test added 2. I did not try to disable 3.
I don't get it why anyone need to run SEE through an en-passant move. Or did I miss out bigtime on some things.
SEE is only about isolating bad captures that may lose material and be pruned or sorted back - it does not matter if a move is clearly winning or equalizes. En-passant can never be a loser and be a candidate for prunning. It should always be make() early if there is one. So what am I missing here?
As for the one game win against Stockfish, this is the first time it happens a few days back after I added some to evaluation. But I am less surprised that it happens, even if just a rare one time event. I am confident my engine, search and evaluation, now is very thoroughly debug and almost bugfree.
Best Regards,
Rasjid.
I don't do EP in SEE myself, as that implies a pawn push, where SEE only considers captures...
I can call see() on any move. But see() first checks to see if it's en-passant and returns that it is safe. With promotions you just treat them as pawn moves which they are. If you promote and are captured, you don't lose a queen, you lose a pawn because you never really had the queen. If you capture to promote that's always a win of material and if you cannot push forward to promote you lose a pawn anyway. Castling is always safe if it's legal so I simply return that it's safe.
I can call SEE() anywhere as well, but I removed the ep test. It adds something to the front of EVERY SEE that is done, and it is very rare. I couldn't tell any difference with or without in testing, and when there is no difference, I always go with "simplest".
I handle promotions correctly. f8=Q is +8. Rxf8 = -9, I just lost a pawn, not a queen. fxg8=Q is +8 + value of captured piece, Rxg8 = -9, I just won whatever was captured.
It seems that there are a number of issues here that get a bit mingled:
1) The effect of move ordering by using SEE
2) The effect of pruning losing captures in QS (i.e. that have SEE < 0)
3) The effect of pruning futile captures ('delta pruning')
Point (3) is not quite clear to me. Normally 'futile' means that the move itself does not get you above alpha (i.e. currentEval + pieceValue[victim] <= alpha - MARGIN). This does not require SEE. The way you describe it here, however, suggest that you prune if currentEval + SEE <= alpha - MARGIN. If this is the case, what exactly do you mean by switching this off? Does it mean that
a) You still prune futile captures that have currentEval + pieceValue[victim] <= alpha - MARGIN
b) You don't prune any captures at all
I like to distinguish the effect of the move ordering and the pruning, as there also is a lot of pruning one can do that is not based on SEE. Not having SEE is really very different from not pruning captures like Q x protected P.
hgm wrote:It seems that there are a number of issues here that get a bit mingled:
1) The effect of move ordering by using SEE
2) The effect of pruning losing captures in QS (i.e. that have SEE < 0)
3) The effect of pruning futile captures ('delta pruning')
Point (3) is not quite clear to me. Normally 'futile' means that the move itself does not get you above alpha (i.e. currentEval + pieceValue[victim] <= alpha - MARGIN). This does not require SEE. The way you describe it here, however, suggest that you prune if currentEval + SEE <= alpha - MARGIN. If this is the case, what exactly do you mean by switching this off? Does it mean that
a) You still prune futile captures that have currentEval + pieceValue[victim] <= alpha - MARGIN
b) You don't prune any captures at all
I like to distinguish the effect of the move ordering and the pruning, as there also is a lot of pruning one can do that is not based on SEE. Not having SEE is really very different from not pruning captures like Q x protected P.
Maybe you are making a distinction about how see() can be used. Q x protected P is exactly what see() would detect and avoid for pruning in quies. If you don't have a proper see but you are willing to look at defenses by pawns and knights (so that you don't have to deal with sliding pieces) you have something that function like a poor mans see() routine.
However see can also be used to return an exchange score or value. For example does the move actually win something? In that sense the simple pruning see-like rules is not very much like the full see.
Komodo has 2 see versions, one that returns a score and another one that is boolean which is used simply to determine if a move is non-losing.
Don
Capital punishment would be more effective as a preventive measure if it were administered prior to the crime.
My point was that SEE might be a needlessly expensive (and perhaps not always very much more accurate) way to do some of those things. Futility pruning is normally done based on the victim value (which is instantly available), not on SEE value. If (in Bob's tests) futility pruning would have been switched off altogether, because normally he happens to use SEE for that, the results would be highly misleading.
Very possible that doing futility pruning based on SEE is superior to doing it based on victim value. But then the SEE can only take credit for the improvement. Not for the entire benefit of futility pruning, as you could do plenty of futility pruning without having SEE.
In a sense BLIND is indeed a poor-man's SEE, but it might give you for free what you would otherwise have to compute. Some engines do keep track of which pieces are protected and which aren't, e.g. for the purpose of evaluation. That information could also be used for pruning obviously bad captures. SEE might offer very little on top of that.
hgm wrote:My point was that SEE might be a needlessly expensive (and perhaps not always very much more accurate) way to do some of those things. Futility pruning is normally done based on the victim value (which is instantly available), not on SEE value. If (in Bob's tests) futility pruning would have been switched off altogether, because normally he happens to use SEE for that, the results would be highly misleading.
Very possible that doing futility pruning based on SEE is superior to doing it based on victim value. But then the SEE can only take credit for the improvement. Not for the entire benefit of futility pruning, as you could do plenty of futility pruning without having SEE.
In a sense BLIND is indeed a poor-man's SEE, but it might give you for free what you would otherwise have to compute. Some engines do keep track of which pieces are protected and which aren't, e.g. for the purpose of evaluation. That information could also be used for pruning obviously bad captures. SEE might offer very little on top of that.
I have found that this applies all over the place in chess programming, which heuristic is responsible for the improvement or regression - and often they interact so that you cannot get a straightforward answer. I am finding this in BeeKay as I re-implement many things.
So to measure the true benefit of see() I think you simply have to specify exactly what you you are talking about. What are you measuring, the "concept" of statically analyzing an exchange or a specific implementation? To me it's just an implementation detail how you do it. So if you are trying to measure the value of the (more or less) standard SEE implementation of full swap down you also have to ask, "as opposed to what?"
Capital punishment would be more effective as a preventive measure if it were administered prior to the crime.
hgm wrote:It seems that there are a number of issues here that get a bit mingled:
1) The effect of move ordering by using SEE
2) The effect of pruning losing captures in QS (i.e. that have SEE < 0)
3) The effect of pruning futile captures ('delta pruning')
Point (3) is not quite clear to me. Normally 'futile' means that the move itself does not get you above alpha (i.e. currentEval + pieceValue[victim] <= alpha - MARGIN). This does not require SEE. The way you describe it here, however, suggest that you prune if currentEval + SEE <= alpha - MARGIN. If this is the case, what exactly do you mean by switching this off? Does it mean that
a) You still prune futile captures that have currentEval + pieceValue[victim] <= alpha - MARGIN
b) You don't prune any captures at all
I like to distinguish the effect of the move ordering and the pruning, as there also is a lot of pruning one can do that is not based on SEE. Not having SEE is really very different from not pruning captures like Q x protected P.
This "delta pruning" is not very sophisticated, and is actually just an extension of "let's don't search captures with SEE <= 0." It becomes "let's don't search captures where material + SEE() < alpha, which makes winning a pawn get passed over if the current material is a piece down.
I didn't change any ordering stuff in the normal search at all, just the pruning in the q-search...
But did you still prune captures with material + victimValue < alpha after you disabled the SEE-based pruning? VictimValue is an upper limit for SEE, so this bound might not be as sharp as SEE, but there still is an appreciable fraction of the moves that you prune by SEE that would be pruned by this condition too. If you did not even prune these I am not surprised that you tree gets so much bigger.
Btw, your material+SEE condition seems dangerous. Suppose that alpha = material + 3, and you have two Bishop x protected Rook captures, each of those has only SEE = 2, but together they have SEE = 4, which would bring you above alpha. And he must recapture after the first, to not give you 5, so you will get a shot at the second.
Have you tried to only prune margin + SEE < alpha when SEE is odd (meaning you lose tempo), while allowing all captures with SEE even (meaning you keep tempo) and margin + victimValue > alpha?
hgm wrote:Btw, your material+SEE condition seems dangerous. Suppose that alpha = material + 3, and you have two Bishop x protected Rook captures, each of those has only SEE = 2, but together they have SEE = 4, which would bring you above alpha. And he must recapture after the first, to not give you 5, so you will get a shot at the second.
Yes, that is a situation where this technique would prune too much. Testing is the only way to tell if this is enough of a problem that the technique is not worth it. According to Bob's tests and my own, it is definitely worth it.
