Q: Move ordering, checks

[hgm]

I know many engines search checks in the first few levels of QS. But how do they order them? Go all non-capture checks after the captures?

And how is this done at d=1? Are the checks there just ordered amongst the other non-captures (assuming non-captures are not futile)? Or do they go after the latter? Because of the extension checks are relatively expensive, and that could be a reason to search them only as a last resort.

Although at d=1 this might not be so bad: non-checking moves get a QS reply that searches only captures, checks a d=1 reply, which searches only evasions, and after that both drop into QS. The number of evasions might not be very different from the number of captures.

It seems more of a problem that this should be a pretty sure way to push trouble over the horizon, even despite the extension. E.g. if there exists a fork against you. Any move would then make the opponent cash on the fork in QS. But after check + extended evasion it is my turn in QS, and I happily stand pat in face of the fork.

Should checks at d=1 be forbidden for this reason? I suppose this is just an example of the more general rule that when null move fails low at d=1 you really should not try anything that is not tactically connected to the null-move refutation, as even when it appears to help this would just be horizon effect.

An alternative is to forbid stand-pat after a check evasion. The fact that two ply earlier a check was played suggests that the null move failed low there, and (when you search checks last) all non-checking moves too. So there apparently was a threat that could not be solved by any non-check. So it would be a bit foolhardy to assume you will be able to dodge that threat now. But searching the check, and merely forbidding stand-pat after the evasion, would at least enable you to see tactics where you create an attack through an intermediate check, and cash that in QS.

[bob]

I know many engines search checks in the first few levels of QS. But how do they order them? Go all non-capture checks after the captures?

And how is this done at d=1? Are the checks there just ordered amongst the other non-captures (assuming non-captures are not futile)? Or do they go after the latter? Because of the extension checks are relatively expensive, and that could be a reason to search them only as a last resort.

Although at d=1 this might not be so bad: non-checking moves get a QS reply that searches only captures, checks a d=1 reply, which searches only evasions, and after that both drop into QS. The number of evasions might not be very different from the number of captures.

It seems more of a problem that this should be a pretty sure way to push trouble over the horizon, even despite the extension. E.g. if there exists a fork against you. Any move would then make the opponent cash on the fork in QS. But after check + extended evasion it is my turn in QS, and I happily stand pat in face of the fork.

Should checks at d=1 be forbidden for this reason? I suppose this is just an example of the more general rule that when null move fails low at d=1 you really should not try anything that is not tactically connected to the null-move refutation, as even when it appears to help this would just be horizon effect.

An alternative is to forbid stand-pat after a check evasion. The fact that two ply earlier a check was played suggests that the null move failed low there, and (when you search checks last) all non-checking moves too. So there apparently was a threat that could not be solved by any non-check. So it would be a bit foolhardy to assume you will be able to dodge that threat now. But searching the check, and merely forbidding stand-pat after the evasion, would at least enable you to see tactics where you create an attack through an intermediate check, and cash that in QS.

I have a check generator that only generates non-capturing checks (since the capture generator took care of the capture checks automagically). Special piece of code only used in the q-search.

[Ferdy]

I know many engines search checks in the first few levels of QS. But how do they order them? Go all non-capture checks after the captures?

Here is what I did in qsearch. This is at depth 0, the side to move here is not in-check, this is guaranteed by main search. Get the static eval see if I can exit early. If not generate capture and promote moves. If one of these moves checks the opp king, then generate complete evasions (caps, non-caps and others), this evasion happens at depth -1. At depth -1 since the side to move is in-check I will not call my static eval, instead generate complete evasion as earlier said. The depth at qsearch where there is check is not incremented. At depth -2, I will always call the static eval to make an attempt to exit early, it does not matter if I am in-check. If at depth -2 I cannot exit early, then just generate caps and promote moves. If one of these moves checks the opp king, then don't bother with generating evasions, just call static eval, and check if I can exit early, if not then generate caps and promote moves again. This would mean that evasion happened only at depth -1.

Here comes the non-caps check move generation, at depth 0 if all my caps and promote moves failed to improve alpha, I will generate non-cap check moves. This only happens at depth 0. Check evasions are allowed at next depth which is at depth -1.

[hgm]

This made me think a bit on how to make a dedicated generator for non-capture checks. I suppose bitboard engines do this by once generating the Rook attacks and Bishop attacks from the king-square, (masking off the occupied bits to be left with non-captures, and then intersect those with the attacks for Rooks and Bishops (one by one) from the squares they are on (and for Queens intersect the sum of both with the sum of both from the king-square). Then they can extract the checking opportunities for that piece one by one from the intersection.

I would like to have something similarly fast for mailbox, as that would mean it is far faster for boards with more than 64 squares. One way that comes to mind would be to keep an array that tabulates, as a function of the relative position of a piece to the King, what direction it would have to move in, and how far, in order to check the King, and in which direction, and how distant from the King it would do that then.

Now in the most general case of the Queen there are 12 checking opportunities, as every ray through the king-square will intersect 3 of the 4 rays going through the queen-square, while the 4th ray would be parallel. (And if it coincides we could capture the King already.) These 12 opportunities could be stored in some canonical order, so that the number of the opportunity implies the orientation of the moving and the checking ray. These directions (0-3) could then be tabulated in two small (12-entry) tables. The only thing that really depends on the relative positions is the distances.

So we could do

Code: Select all

typedef long long unsigned int Mask; // 64-bit

typedef struct {
  char kDist[12];
  char qDist[12];
  Mask directionMask;
} CheckOpportunity;

CheckOpportunity rawCheckOpportunity[15*16];
CheckOpportunity *co;

#define checkOpportunity (rawCheckOpportunity + 7*16 + 7)

char kDir[4*16];
char qDir[4*16];

char bit2opportunity[64]; // DeBruijn bit extraction table for mask

Mask checkMask[NrOfPieces]; // field of piece list

The idea is that checkMask[] holds a bitmap where bits correspond with one of the 12 checking opportunities in a fixed way, and which opportunities are relevant for the piece in question. A Rook, f.e., would only have the bits set that correspond to rank move + file check and file move + rank check. The idea is to run through the piece list, and extract the bits for them to get an opportunity number, use that as index in kDir[] and q[dir] to see in which directions from King and prospective checker this opportunity lies, look in checkOpportunity[fromSqr-kingSqr].kDist and .qDist to see how many empty squares would be needed along each of the two rays for the opportunity not to be blocked, and finally compare those distances to viewDistance[sqr][direction], an incrementally updated array that keeps track of piece distances (and serves also many other purposes).

There is one nasty detail, however; the opportunity number corresponds to combinations of orientations, numbered 0-3 (file, rank, diagonal, anti-diagonal), while viewDistance[][8] distinguishes direction along the rays, numbered 0-7. In Chess variants pieces could also have asymmetric moves, e.g. backward along file or forward diagonal. So it becomes important to know whether a certain opportunity that uses, say, file for moving and diagonal for checking, uses this file and diagonal in the forward or backward direction. This will not be a fixed property of the opportunity number, but depends on the relative position.

So each of the 12 checking opportunities actually can have 4 flavors, depending on the direction of the moves along the two involved rays. This is the purpose of the directionMask field in the CheckOpportunity struct: each opportunity has 4 bits assigned there, the same way as they are assigned in the pieces' checkMask. So symmetric pieces like Rook would always have all 4 flavors of the corresponding opportunity set, but asymmetric pieces could select those that apply to them. By ANDing checkMask with co->directionMask before extracting the bits we would be left with only those opportunities that also traverse the involved rays in the allowed directions. The bit would map to a number from 0-63, in such a way that the the opportunity number (0-11) would be in the lowest 4 bits, while the next two higher bits indicate the flavor. The kDir[] and qDir[] tables would then be indexed by the full number, so they can provide the correct upstream or downstream direction belonging to the ray orientation.

The 4 unused opportunities (12-15) in each flavor group could be used to flag alignment along the four principal rays. Such alignment (when not filtered away through the checkMask as being irrelevant for the piece type) would not necessarily mean you are already checking, if sliders with a finite range participate in the game. It could just mean that the slider has to approach a bit more along the ray to get the King in range. And for an unlimited-range slider, an own piece blocking the ray would flag opportunities to deliver discovered checks. This can also be deduced from the viewDistances through a different kind of test, which does not need any information dependent on relative position.

So we would get something like

Code: Select all

for(piece=...){
  int from = location[piece];
  CheckOpportunity *co = &checkOpportunity[from-xKing];
  Mask opportunities = co->directionMask & checkMask[piece];
  while(opportunities) {
    Mask next = opportunities & -opportunities;
    opportunities -= next;
    opNr = bit2opportunity[next*DEBRUIJN>>58];
    k = kDir[nr]; q = qDir[nr];
    nr = opNr & 15;
    if(viewDistance[xKing][k] > co->kDist[nr] && range[piece][ANTI(k)] >= co->kDist[nr]) {
      if(viewDistance[piece][q] > co->qDist[nr] && range[piece][q] >= co->qDist[nr]) {
        int to = from + step[q]*co->qDist[nr];
        GenerateMove(from, to);
      } else opportunities &= qSkipMask[opNr]; // mask off more distant in same direction from checker
    } else opportunities &= kSkipMask[opNr]; // mask off more distant in same direction from King
  }
}

(where the range stuff would not be needed for orthodox Chess, where all sliders have unlimited range).

There still is one little trick in this code: the Mask bits would be ordered in such a way that opportunities needing a larger travel distance from the King (or checker) will be extracted after those that needed a shorter distance in the same direction. (Note there could be up to three opportunities in that direction, e.g. Qe6 could check Kc2 on c4, c6 and c8 along the +c-file.) If one of the distance tests then fails on one opportunity, we could immediately clear all oportunities more distant in the same direction before extracting the next opportunity, as these will certainly be blocked too. This is especially important for distance to King, as the King will be safely tucked away during most of the game, so that its viewDistance will be wuite small in any direction. So on most ray even the closest opportunity would already ly beyond the King shield, so that the more distant ones never survive to be extracted and tested. This keeps the amount of work bearable even for Queens, with their 12 theoretical possibilities, as typically only 4 would remain (for a King on g1/g8)

[bob]

If you think about checks, you can do them in stages:

(1) direct checks. You use the "super-piece" idea for the king, and extract the diagonal attacks if it were a bishop. Then you find each bishop/queen and see if its attacks intersect. Repeat for rooks and queens.

(2) discovered checks. Similar idea where you check the diagonals or ranks/files and if the king super-piece attacks one of your pieces, and if you remove that piece it attacks a piece of yours that moves in the same direction, then moving that piece in the two orthogonal directions is a discovered check.

(3) there is one case I chose to ignore, enpassant captures. The enpassant capture can be a direct check, which I catch. It can also be a discovered check directly or indirectly. For example, it moves diagonally and can discover a check on the opposite diagonal. But even more interesting, the pawn you remove is not on the same square as the pawn you move, so removing that pawn can also discover a check. Not that hard to handle, but when I wrote the code it almost made my head explode. You can look at Crafty's "movgen.c" file.

I think I remember not doing king move discovered checks. If you think about it, bishops can't discover a check on a diagonal at all. Two of the directions would keep it on the same diagonal, but more importantly, the bishop/queen would already be checking the enemy king if diagonal moves would work at all. Ditto for rooks/queens on ranks/files. Kings were a more complicated case since they move in all directions. My intent was to have two separate king attack bit boards, as I do for rooks and bishops. Then I could only move the king in a direction that exposes a check, but that is still a bit complicated... I chose to ignore it.