Pruning in QS

Discussion of chess software programming and technical issues.

Moderators: Harvey Williamson, bob, hgm

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
hgm
Posts: 25076
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Pruning in QS

Post by hgm » Wed Mar 06, 2013 11:48 am

The recent discussion about SEE revived my efforts for finding a stable algorithm for QS, less prone to search explosion. Pruning captures that don't seem promising can be a big help towards this purpose.

The strictest criteria for searching moves that still seemed to make sense are:
* Don't try Higher x Lower if the victim is protected
* Don't try equal captures if the victim is protected
* Don't try to capture something if the opponent can capture something more or equally valuable with his reply

There is no obvious gain from moves that fit any of these descriptions. They could be winning captures, but without thinking ahead more than 2 ply you cannot know that. So they are more like 'wild goose chases'. One way to prevent search explosion is to limit the number of such goose chases.

This gives you a handle for iteratively deepening QS, turning it from an aggressive depth-first search (which is especially prone to search explosion) to a much more stable breadth-first search (which offers a much better guarantee of finding quick and cheap refutations if they exist). What you can do is in the horizon node iterate over capture searches that allow at most 0, 1, 2, 3, ... goose chases in any branch. Presumably this would converge to a stable QS tree at some point. (And if not, you can abort the deepening, which is more than you could do if you would just have 'plunged in', allowing any goose chase in a single depth-first search.)

A basic need for this algorithm is a way to check if a piece is protected or not. A poor man's implementation for this could be to just make the move, and then run the move generator to check if a recapture is possible, and legal. But of course much more advanced methods for this are in common use.

In all cases you would pass the value of the last victim with a QS call. If a moves that is not LxH or has an unprotected victim would capture something more valuable, the previous move would be counted as a goose chase as well. (Despite the fact that it might have been LxH or captured something unprotected.)

Example: you have PxB, but the opponent can retaliate with RxR. At first glance the PxB seems an OK move, but as soon as you discover RxR in the daughter (which will be pretty early, if you use MVV ordering), you will determine if the Rook was protected. Should it turn out that it was not, the PxB is now counted as a goose chase, and reduces your remaining budget for those (possibly aborting the curent branch immediately, if you had none). Though shalt not capture a Bishop if thy Rook is hanging! If the Rook was protected, however, the possibility that a Rook trade could follow would not deter you in any way from making the PxB capture.

After having screened all captures of B and higher this way, (as retaliation against a hanging B also makes the PxB not an obvious gain), you can establish if PxB was a goose chase, and if so, decrement the budget for those, and abort with +INF score if it was already exhausted. If it wasn't, you continue searching captures that provide obvious gain (LxH or unprotected victim) passing the remaining budget, and, when the budget is positive, the other captures with a decremented budget.

If, for example the RxR reply to PxB would be on a protected Rook, it would still be searched if the original goose-chase budget for PxB had been 1 (as PxB would have been 'clean' then), but now with butget 0, because R x protected R is non-obvious. This could lead to a second RxR (if the protector was a Rook, and we did not have a second attacker, so that our Rook would now be hanging, so capturing it would be searched despite the remaining zero-budget). If we would have a second attacker on the Rook (say Q), however, it would stop after PxB, RxR, as the subsequent RxR would find its victim protected (by QxR), and thus considered a goose chase, while there was no budget left for those. (And indeed, it would be just an additional Rook trade, which would not alter the score.

Code: Select all

int Attacked(square)
{
  GenerateCaptures();
  for(ALL_MOVES) {
    if(move.toSquare == square) return 1;
  }
  return 0;
}

int Protected(square)
{
  GenerateCaptures();
  for(ALL_MOVES) {
    if(move.toSquare == square) {
      MakeMove();
      legal = !Attacked(kingSqr);
      UnMake();
      if(legal) return 1;
    }
  }
  return 0;
}

int QS(alfa, beta, budget, threshold)
{
  int currentEval = Evaluate();
  if(currentEval >= alpha) alpha = currentEval;
  if(alpha >= beta) return beta;
  GenerateCaptures();
  SortMoves();
  for(ALL_MOVES) {
    if&#40;value&#91;victim&#93; < threshold&#41; break; // assumes MVV sorting
    if&#40;value&#91;victim&#93; > value&#91;piece&#93; || !Protected&#40;move.toSqr&#41;) &#123; // pre-screening
      budget--; // previous move was goose chase
      if&#40;budget < 0&#41; return +INF; // reject it
      break;
    &#125;
  &#125;
  for&#40;ALL_MOVES&#41; &#123;
    int cost = 0;
    if&#40;value&#91;victim&#93; <= value&#91;piece&#93; && Protected&#40;move.toSqr&#41;) cost = 1;
    if&#40;cost > budget&#41; continue; // move is goose chase, and out of budget
    MakeMove&#40;);
    score = -QS&#40;-beta, -alpha, budget - cost, value&#91;victim&#93;);
    UnMake&#40;);
    if&#40;score > alpha&#41; &#123; // alpha-beta stuff
      ...
    &#125;
  &#125;
&#125;
That you first 'search' the expensive retaliations

Ron Murawski
Posts: 397
Joined: Sun Oct 29, 2006 3:38 am
Location: Schenectady, NY
Contact:

Re: Pruning in QS

Post by Ron Murawski » Thu Mar 07, 2013 5:21 am

hgm wrote:The recent discussion about SEE revived my efforts for finding a stable algorithm for QS, less prone to search explosion. Pruning captures that don't seem promising can be a big help towards this purpose.

The strictest criteria for searching moves that still seemed to make sense are:
* Don't try Higher x Lower if the victim is protected
* Don't try equal captures if the victim is protected
* Don't try to capture something if the opponent can capture something more or equally valuable with his reply
...
Hi HG,

I will assume that we have a magic function with almost no speed cost that can determine if a square is protected or not. I'm going to play devil's advocate here.

* Don't try Higher x Lower if the victim is protected

I'm sure this works more than 99% of the time. Sometimes the protecting piece is pinned and then it may not really be a protector. So, if your program keeps a list of pinned pieces, this will work perfectly. Otherwise the only way to avoid a blindness for pinned pieces as protectors is to generate all legal captures in reply to the original capture.

* Don't try equal captures if the victim is protected

If there are more attackers then defenders, then this 'equal' capture is probably winning. My opinion is that SEE is needed here, or some sort of attack board.

* Don't try to capture something if the opponent can capture something more or equally valuable with his reply

This will be good more than 99% of the time but will miss sharp tactical shots. ie: There are situations where all attacking pieces can be captured, but the opponent is too busy trying to avoid mate to take the time to make the capture. If you can tie this concept to letting the king safety score of the defender determine if this is safe, then I think it may work.

I don't think it is possible to eliminate SEE in qsearch, but I think SEE usage can be minimized.

Ron

User avatar
Rebel
Posts: 5694
Joined: Thu Aug 18, 2011 10:04 am

Re: Pruning in QS

Post by Rebel » Thu Mar 07, 2013 8:47 am

Ron Murawski wrote: * Don't try equal captures if the victim is protected

If there are more attackers then defenders, then this 'equal' capture is probably winning. My opinion is that SEE is needed here, or some sort of attack board.
My experience is that every equal capture should be investigated and that the costs for doing so are to neglect. It's a long time ago and although rare on the bigger scale I have seen quite some horrible tactical blunders because the lack off it in the past.

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

Re: Pruning in QS

Post by hgm » Thu Mar 07, 2013 10:37 am

Ron Murawski wrote:I will assume that we have a magic function with almost no speed cost that can determine if a square is protected or not. I'm going to play devil's advocate here.

* Don't try Higher x Lower if the victim is protected

I'm sure this works more than 99% of the time. Sometimes the protecting piece is pinned and then it may not really be a protector. So, if your program keeps a list of pinned pieces, this will work perfectly. Otherwise the only way to avoid a blindness for pinned pieces as protectors is to generate all legal captures in reply to the original capture.
Indeed, the need to test for 'false protectors' is a nuisance. In my pseudo-code that makes the difference between Attacked() and Protected(), the latter being obviously much more expensive. You will have exactly the same problem in SEE, however. Basically my Protected() function is just the first ply of a SEE. And usually you don't generate all legal captures for the opponent to check if a move was legal. You just test for alignment of your King with the from-square. Usually there is none, and only if there is you have to scan the ray from the King to see if you bump into the right kind of slider.

A poor-man's implementation would be to play the move always, but pass the toSquare to the daughter node, which then would abort (returning +INF) if it found a legal capture to that square. Which again it could do (in a time-wise expensive but code-wise almost free way) by calling QS on the recapture before searching any other capture, with beta=+INF. (So that all captures except King capture would be futile.) This is sort of a trade-off, though: would you try the recapture or the most-valuable victim first? The common case is that pieces are not pinned, so the recapture is very likely to immediately cut off the search (= fail high), without the need to search more than one node. It is as if the last move piece has temporary +INF value, so effectively it has become the MVV.

Even this poor man's implementation would prune a lot compared to a non-pruning QS, (which for a beta cutoff in the daughter would be dependent on a full search of the recapture to turn a high-enough score, rather than to just be legal). Although not as much as when you would have more clever ways to determine 'true protectors'. Which again would be much cheaper than a full-blown SEE, as in SEE you would have to do exactly that for every move in the exchange.
* Don't try equal captures if the victim is protected

If there are more attackers then defenders, then this 'equal' capture is probably winning. My opinion is that SEE is needed here, or some sort of attack board.
Yes, this definitely is a weakness. Multiple exchanges are comparatively rare, though. Note, however, that the overall scheme just uses this as a first approximation. It labels it a 'goose chase', but it could have budget for goose chases, and then it would search it. The scheme relies on the hope that by iterating over increasing 'goose budget' (the depth measure of QS) you would often find simple, although perhaps not best refutations before the SEE-wise best but lengthy exchange has been fully searched. If I can capture two Rooks with SEE = +2, one through BxR, PxR, the other through QxR, QxQ, (x-ray)BxQ, KxB, sorting purely by SEE would not see the difference, and might as well try the latter first. In a first, 'gooseless' iteration, however, the exchange starting with QxR would be suppressed, as it is labeled a goose chase (H x protected L).

I agree that information on the number of attackers and protectors could help to make the heuristic more accurate. But the question is if such information can be cheaply obtained, and if it would be reliable enough to really make a difference.
* Don't try to capture something if the opponent can capture something more or equally valuable with his reply

This will be good more than 99% of the time but will miss sharp tactical shots. ie: There are situations where all attacking pieces can be captured, but the opponent is too busy trying to avoid mate to take the time to make the capture. If you can tie this concept to letting the king safety score of the defender determine if this is safe, then I think it may work.
Well, again iterating over goose budget would cure that. In 99% you would converge after few iterations. The only penalty in the other 1% of the cases would be that you need to do extra iterations, duplicating some of the work from the previous one. (But of course converged sub-trees would be hashed, etc.)

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

Re: Pruning in QS

Post by hgm » Thu Mar 07, 2013 2:26 pm

The way I wanted to iteratively deepen the QS would look something like this:

Code: Select all

int pruneCount;

int QS&#40;alfa, beta, budget, threshold&#41;
&#123;
  int startCount = pruneCount;
  int currentEval = Evaluate&#40;);
  if&#40;currentEval >= alpha&#41; alpha = currentEval;
  if&#40;alpha >= beta&#41; return beta;
  GenerateCaptures&#40;);
  SortMoves&#40;);
  for&#40;ALL_MOVES&#41; &#123;
    if&#40;value&#91;victim&#93; < threshold&#41; break; // assumes MVV sorting
    if&#40;value&#91;victim&#93; > value&#91;piece&#93; || !Protected&#40;move.toSqr&#41;) &#123; // pre-screening
      budget--; // previous move was goose chase
      if&#40;budget < 0&#41; &#123; pruneCount++; return +INF; &#125; // reject it
      break;
    &#125;
  &#125;
  for&#40;ALL_MOVES&#41; &#123;
    int cost = 0;
    if&#40;value&#91;victim&#93; <= value&#91;piece&#93; && Protected&#40;move.toSqr&#41;) cost = 1;
    if&#40;cost > budget&#41; &#123; pruneCount++; continue; &#125; // move is goose chase, and out of budget
    previousCount = pruneCount;
    MakeMove&#40;);
    score = -QS&#40;-beta, -alpha, budget - cost, value&#91;victim&#93;);
    UnMake&#40;);
    if&#40;score > alpha&#41; &#123; // alpha-beta stuff
      if&#40;score >= beta&#41; &#123;
        pruneCount -= previousCount - startCount; // discard all counts in unnecessary subtrees
        return beta;
      &#125;
      alpha = score;
    &#125;
  &#125;
  return alpha;
&#125;

int HorizonSearch&#40;alpha, beta&#41;
&#123;
  int budget = 0;
  do &#123;
    pruneCount = 0;
    score = QS&#40;alpha, beta, budget, +INF&#41;;
  &#125; while&#40;pruneCount && budget++ < MAX_QS_ITER&#41;;
  return score;
&#125;
This contains the same routine QS(), except that it now counts the number of times it actually pruned a capture for being a goose chase, and the maximum number of allowed goose chases in a branch was already used up. As we don't care about any pruning in sub-trees that should not have been searched at all, because they cannot possibly affect the score (i.e. all moves other than the cut-move in a cut-node), and this becomes only apparent after we actually found the cut-move, we have to correct the count for that whenever we take a beta cutoff.

In horizon nodes we can then see after QS() has completed how many 'loose ends' that in theory could still change the results (put in practice are unlikely to do so) are still dangling. If this is non-zero we could now enable those moves, by incrementing the budget for such moves by one, and ordering a re-search. This re-search would then benefit from the previous search through the hash table, which would pass them the cut-moves in all nodes that were searched before. The 'budget' parameter would play the role that is usually played by the depth, i.e. you could take hash cutoffs based on hashed score bounds if the hashed budget was >= the requested budget. To optimize this, nodes should check their pruneCount, and increase the stored depth to MAX_QS_ITER if they had no prunings in the essential sub-tree they sprout. As the QS trees are expected to be quite small, a special hash table could be used for this, which fits entirely in L2 (and the accessed elements for the fully developed tree probably in L1), so that the re-search of already visited parts of the tree will be extremely fast.

The parameter QS_MAX_ITER could be used to put an absolute break on search explosions (at the expense of getting an inaccurate result in positions that would otherwise explode). The results of HorizonSearch could go into the main hash table, as QS result.

Daniel Shawul
Posts: 4055
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Pruning in QS

Post by Daniel Shawul » Thu Mar 07, 2013 3:53 pm

The recent discussion about SEE revived my efforts for finding a stable algorithm for QS, less prone to search explosion. Pruning captures that don't seem promising can be a big help towards this purpose.
I think stability of QS is more important than anything else.Recently I was confused about where to put drop moves of shogi. Clearly they are as important as captures in many situations and should be tried in QS but if i do that search explodes way too much. So I had to put them in the main search but where? before or after non-capture moves? If I put them before ,LMR would reduce the other moves so much because piece drop moves are too many. So what started out as promising moves ended up being left out of QS, and being put at the rare end of the move list. I have also encountered similar situations in Go where the utmost priority should be stablity by giving a blind eye to some good moves that should have been tried. QS might not even makes sense in some cases at all.
The strictest criteria for searching moves that still seemed to make sense are:
* Don't try Higher x Lower if the victim is protected
* Don't try equal captures if the victim is protected
* Don't try to capture something if the opponent can capture something more or equally valuable with his reply
SEE it is too domain specific for me, and the benefits you get from additional cutoffs compared to MVV/LVA is not that much. Chess is on the lucky side since you can usually get to a stable position (run out of captures) even if you don't use any tricks in QS. This may also be the case with a global SEE that does swaps everywhere.

Btw if you have to do iterative QS with different depth , why not try the same thing in the lower parts of the main search, with heavy lmr. It should have the same effect and you have a lot more options as to what move gets tried.

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

Re: Pruning in QS

Post by hgm » Thu Mar 07, 2013 5:30 pm

Of course the way I described it now would not really cause any pruning at all, in the end. To be left with pruning similar to pruning SEE-wise bad captures, you would have to change the condition on allowing 'not obviously winning' captures. These were now detected by the line

Code: Select all

if&#40;value&#91;victim&#93; <= value&#91;piece&#93; && Protected&#40;move.toSqr&#41;) cost = 1; 
i.e. even equal captures of protected pieces were postponed to later iterations, but in the end, as the budget increased, they would always be searched. There would have to be some differentiation here in moves you want to postpone, and moves you would never want to try.

What would also be an incentive to try equal captures immediately is when he is able to capture you back (which usually is the case in equal captures), and you are unprotected yourself. Because then he is almost certainly going to try that on any other move you will try. If you are protected, the rule that prevents you from doing the equal capture, likewise would restrain him.

For instance, if you don't have a second attacker of the square (which in some cases might force you to also look for an X-ray attacker behind you, as these would not in your current move list of captures on this victim), even equal captures mightalways be pointless, and High x protected Low is certainly bad. In the latter case SEE would also be certainly < 0 if the value of the protector is less than H - L. These could be reasons to always prune the move without incrementing pruneCount, no matter how much budget you have.

Ron Murawski
Posts: 397
Joined: Sun Oct 29, 2006 3:38 am
Location: Schenectady, NY
Contact:

Re: Pruning in QS

Post by Ron Murawski » Fri Mar 08, 2013 5:58 am

hgm wrote:
Ron Murawski wrote:I will assume that we have a magic function with almost no speed cost that can determine if a square is protected or not. I'm going to play devil's advocate here.

* Don't try Higher x Lower if the victim is protected

I'm sure this works more than 99% of the time. Sometimes the protecting piece is pinned and then it may not really be a protector. So, if your program keeps a list of pinned pieces, this will work perfectly. Otherwise the only way to avoid a blindness for pinned pieces as protectors is to generate all legal captures in reply to the original capture.
Indeed, the need to test for 'false protectors' is a nuisance.
I have a legal move generator and I maintain a bitboard of pinned pieces, so it's not much of a nuisance. I also maintain bitboards of all squares attacked by each side. Since this information is almost free for me I will try out some of your ideas. At present I don't have a working engine so testing will not be any time soon.
hgm wrote:In my pseudo-code that makes the difference between Attacked() and Protected(), the latter being obviously much more expensive. You will have exactly the same problem in SEE, however. Basically my Protected() function is just the first ply of a SEE. And usually you don't generate all legal captures for the opponent to check if a move was legal. You just test for alignment of your King with the from-square. Usually there is none, and only if there is you have to scan the ray from the King to see if you bump into the right kind of slider.

A poor-man's implementation would be to play the move always, but pass the toSquare to the daughter node, which then would abort (returning +INF) if it found a legal capture to that square. Which again it could do (in a time-wise expensive but code-wise almost free way) by calling QS on the recapture before searching any other capture, with beta=+INF. (So that all captures except King capture would be futile.) This is sort of a trade-off, though: would you try the recapture or the most-valuable victim first? The common case is that pieces are not pinned, so the recapture is very likely to immediately cut off the search (= fail high), without the need to search more than one node. It is as if the last move piece has temporary +INF value, so effectively it has become the MVV.

Even this poor man's implementation would prune a lot compared to a non-pruning QS, (which for a beta cutoff in the daughter would be dependent on a full search of the recapture to turn a high-enough score, rather than to just be legal). Although not as much as when you would have more clever ways to determine 'true protectors'. Which again would be much cheaper than a full-blown SEE, as in SEE you would have to do exactly that for every move in the exchange.
* Don't try equal captures if the victim is protected

If there are more attackers then defenders, then this 'equal' capture is probably winning. My opinion is that SEE is needed here, or some sort of attack board.
Yes, this definitely is a weakness. Multiple exchanges are comparatively rare, though. Note, however, that the overall scheme just uses this as a first approximation. It labels it a 'goose chase', but it could have budget for goose chases, and then it would search it. The scheme relies on the hope that by iterating over increasing 'goose budget' (the depth measure of QS) you would often find simple, although perhaps not best refutations before the SEE-wise best but lengthy exchange has been fully searched. If I can capture two Rooks with SEE = +2, one through BxR, PxR, the other through QxR, QxQ, (x-ray)BxQ, KxB, sorting purely by SEE would not see the difference, and might as well try the latter first. In a first, 'gooseless' iteration, however, the exchange starting with QxR would be suppressed, as it is labeled a goose chase (H x protected L).

I agree that information on the number of attackers and protectors could help to make the heuristic more accurate. But the question is if such information can be cheaply obtained, and if it would be reliable enough to really make a difference.
Several years ago I tried maintaining attack boards in move/unmove. It slowed down the search by about 20%, but I picked up speed in the QS because I could often use the attack information instead of SEE. Overall it was a loss of Elo but maybe there's a more clever way to maintain and use the attack boards.
hgm wrote:
* Don't try to capture something if the opponent can capture something more or equally valuable with his reply

This will be good more than 99% of the time but will miss sharp tactical shots. ie: There are situations where all attacking pieces can be captured, but the opponent is too busy trying to avoid mate to take the time to make the capture. If you can tie this concept to letting the king safety score of the defender determine if this is safe, then I think it may work.
Well, again iterating over goose budget would cure that. In 99% you would converge after few iterations. The only penalty in the other 1% of the cases would be that you need to do extra iterations, duplicating some of the work from the previous one. (But of course converged sub-trees would be hashed, etc.)
I believe that "Don't try to capture something if the opponent can capture something more valuable with his reply" is a viable assumption. But I think the "if the opponent can capture something *equally* valuable" part is a tactically dangerous place to stop the QS. I think it requires the QS to go deeper. Like Ed says: every equal capture should be investigated.

Ron

User avatar
Rebel
Posts: 5694
Joined: Thu Aug 18, 2011 10:04 am

Re: Pruning in QS

Post by Rebel » Fri Mar 08, 2013 6:47 am

Ron Murawski wrote:
hgm wrote: Well, again iterating over goose budget would cure that. In 99% you would converge after few iterations. The only penalty in the other 1% of the cases would be that you need to do extra iterations, duplicating some of the work from the previous one. (But of course converged sub-trees would be hashed, etc.)
I believe that "Don't try to capture something if the opponent can capture something more valuable with his reply" is a viable assumption. But I think the "if the opponent can capture something *equally* valuable" part is a tactically dangerous place to stop the QS. I think it requires the QS to go deeper. Like Ed says: every equal capture should be investigated.
I ran a bullet match (taking equal captures out QS) and not only it scored badly (46.9%) but surprisingly also the default version (do all equal captures) performed 2.5% faster while searching many more moves. I can only think of one explanation, hash table in QS responsible for improved move ordering.

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

Re: Pruning in QS

Post by hgm » Fri Mar 08, 2013 8:33 am

For clarity: what do you mean exactly with 'equal captures' here. Just any capture by a piece of the same kind as the victim (even if the latter was unprotected), or captures with SEE = 0?

The iterative framework for QS that I describe here allows you the freedom to classify captures as "never to be searched", "to be searched immediately", or "to be searched in the next QS iteration". Testing should show what is best. The more precisely you can classify the move, the better performance you would likely achieve. You could for instance make a difference between equal captures (of protected pieces) where you have a second attacker, where the number of attackers is larger than the number of protectors, where SEE > 0, depending on which information is available.

Note that my original proposal did not suggest to put equal captures in the "never search" category. Just that it could be better (in absence of SEE info or attack counts) to postpone their search until after all moves have been tried that win something in a more trivial way. This was partly inspired by the need to make the "don't capture things that are worth less than what you stand to lose elsewhere" rule viable. If I have PxB, I don't want the fact that a QxQ trade is possible to discourage searching of PxB. One way of doing that was to classify the QxQ as a move to be postoponed, so that its existence would not be a reason to abort PxB on the first try.

But it is true that we could make a distinction between moves too postpone, and moves that could be reason for aborting a previous seemingly good capture because the pose a more severe threat (e.g. capturing a B while your Rook is hanging). So a less restrictive set of rules (relying on more aggressive search per iteration, and fewer iterations) could be:

1) Don't try Higher x Lower if the victim is protected
2) Do try equal captures (even if the victim is protected)
3) Don't try to capture something if the opponent can capture something more or equally valuable with his reply through moves other than (1) or (2)

This would not stop me from trying PxB if there existed mutual QxQ attacks (both Q protected), or my protected R was diagonally attacked by Q. But it would stop me from trying that same PxB (or at least very quickly abort it) if my R or Q were unprotected and under Q attack. The mere detection of that condition would be enough to make PxB fail low. It is a good question if this should be reason to classify PxB immediately as a "never-to-be-searched" move, or merely as a "goose chase". I would be inclied to do the latter, because it is conceivable that the PxB would attack another R (or Q), and then the fact that I had a hanging R would not have to discourage me at all. Retaliation against a different square is an inherently risky method for refutation, because you leave the original capturer alive. If I capture a B through RxB, and he recaptures the Rook, he never has to worry what my Rook will attack in this new place. But if he captures another Rook instead...

So in summary: with PxB in the presence of protected Q x protected Q, you would try PxB (after trying QxQ on MVV grounds first, of course. But say that doesn't work because he recaptured with the B, so that you cannot follow up with PxB anymore, and it remains an even trade, while beta > currentEval). In the daughter node he would have Q x protected Q, which would not be reason to abort, but would be searched immediately. That sounds like the proper treatment for this case, so indeed the new rules do seem an improvement.

A controversial point could still be the "or equally valuable" I put in italics in rule (3). I put it there to put a quick stop to plunder raids, where the Q of each side could start capturing a string of unprotected minors. The outcome of such plunder raids is difficult to predict in advance, and they can be very expensive to search depth-first. So the idea is to not engage in them until after you have tried every simple option. And if you capture the same as what he will capture elsewhere, you will have made no progress in two ply, and created a potentially explosive situation. So better only search that branch if it is really score-determining, which will become clear after you have tried every alternative option to prune it by alpha-beta (i.e. in the next QS iteration).

Post Reply