Sliding-path for incremental move generation

[stegemma]

I am trying to write this up as pseudo-code, but I ran into a problem:[...]
KxK, KxQ, QxK, QxQ, R1xK, R1xQ, R2xK, R2xQ, B1xK, B1xQ, B2xK, B2xQ, N1xK, ...
[...]and could then simply be shifted to the location of another victim to make that inherit the captures on the piece it replaced.

It is not clear to me how do you handle promoted pawns. Some assumption about pawns can't be valid for promoted pawns and this will "invalidate" the whole move set (or almost a part of it).

Another part that is not clear is the last one; a piece can substitute only one of the other colors, for which the attacker/victims have to be reverted.

Another thing to handle should be 2 square push of the pawns, it coule be handled as a slide by 2 move, without capture and with all the rule involved.

[hgm]

The proposed system is only for handling captures. This should be the time-critical part of any engine: to a good approximation all nodes of the tree are QS nodes, and all moves made and unmade are captures. Even at d=1 non-captures are futile when you are below alpha-MARGIN. So the idea is that in full-width nodes after being done with the good captures, you would generate non-captures in a different way. Probably conventional mailbox move generation would be best; this is very efficient for generating non-captures. Double-pushes would be handled there. E.p. captures would be tricky, however. As they are always captures of Pawns, I guess you could simply generate them after normal capture generation (as they will not be flagged in the captures set), when the e.p. square is set. Or perhaps even before you get to the capture-of-Pawns part of the captures list.

For making non-captures you would also have some extra problems in the incremental update of the captures set: in addition to discovering slider attacks, you would now also have to take care of their blocking. And the captures set does not provide you any information on attacks to empty squares. So you would have to generate it on the spot, while the nearest-neighbor table would also not hold info on empty squares. So you would have to scan board rays to find the neighbors. Fortunately you only have to do that in 4 directions, because as soon as you hit something, you can find in the neirest-neighbor table what the nearest neighbor in the opposite direction was. (For this reason the neirest-neighbor table should also hold info for pseudo-squares in a guard band just around the board.) This is a lot more expensive than updating the captures set and neighbor table on a capture, but as it is only has to be done rarely this is acceptable, and more efficient than incrementally updating neighbor info for all empty squares. (Which would require ray scans every time you evacuate a square, to alter the info on every square of the rays through that square.)

As to promotions, I see two issues: generating them, and how to handle the situation with 'super-numerary pieces' (2 Queens or 3 Knights) that might occur after it. Now fortunately promotions are very rare in the tree, so that how you handle them hardly has any impact on speed. (Fruit rearranges its entire piece list on a promotion, renumbering all pieces on the board!) I suppose you could keep flags to indicate presence of 7th-rank Pawns, and examine those before you even get to generate captures. If you find any, the non-capture promotions would become of interest even in QS, when they are SEE-safe, and you would have to determine the latter without the benefit of info on attacks to the to-square. But it would also upset the ordering of captures, as when you have 7th-rank P x protected N and R x protected N, the better move (and thus first to be searched) should be would be RxN, as the 7th-rank P really should be treated as Q already. But promotions are already rare, and that you would have this choice would be even rarer. So my guess is it would be entirely satisfactory to completely ignore the problem, just accept poor move sorting in promotion nodes, relying on that at d=0 or d=1 you will find the best move, and higher depths will use that as hash move.

The problem with super-numerary pieces is nasty, because of the coincidence in Chess that the set of all attacker-victim combinations exactly filled the convenient int256 YMM-register size, without any spare bits. When you would restrict yourself to smaller word size, so that the set would have to span multiple words anyway, it would be easy to just reserve some extra bit-slots for the super-numerary pieces (e.g. an extra Queen and Knight, and forbid other under-promotions when you already have a Queen). The proposed scheme could easily handle a pair of Queens, if you don't pair K with Q but with a never-present dummy. A third Knight would be trickier (but much rarer), as the design assumed pairs of equal-valued pieces.

I don't think the Elo of an engine would measurably suffer if you would prune all promotions to a third Knight for the side it plays, and evaluate them as an immdiate win when the opponent plays them. So perhaps this is the practical approach. To satisfy the purists you could switch to a non-incremental mailbox search in sub-trees where 3 or more Knights, Rooks, Bishops or Queens occur. Or treat the 3rd piece of any type move-sorting-wise as if it had remained the Pawn that promoted to it, accepting that this move sorting will be sub-optimal.

Of course in practice extra Queens are very unlikely to occur in the tree before the material composition in the root has lost at least one Pawn for that side. At that point you could create room for a second Queen by interleaving the attackers set of the King with the unpaired Pawn, without exceeding the 256-bit limit. The order of the attacker bits inside the set could be resorted to the new LVA ordering, with 2 Q and 7 P instead of 1 Q and 8 P. Upto that moment you could handle promotions to a 2nd Queen as a loss for the side the engine plays. Or you could do the rather expensive remapping in the node where it happens, reassigning the bits formerly used to indicate moves that captured the Pawn for moves that capture the King, to be able to pair the 2nd Q with the 1st (interleaving their attackers sets).

Note that it doesn't really matter where in the captures set you store the captures of a King, as you would never want to extract them for playing. But that it is important they are there, because you will need that info to extend slider moves over that square when the King moves away. Captures of the King are perfectly legal when the opponent has the move, and pseudo-captures of it are always legal (and should use the same format as the captures set).

[hgm]

As a first attempt, I get something like this:

Code: Select all

const int256 ONE = 1;
const int SLIDERMASK = 0x15500000;

int256 captures[NCOLOR]; // bitmap of all captures in MVV/LVA order
int256 protects[NCOLOR]; // bitmap of all pseudo-captures in MVV/LVA order
int256 attackerMask[NPIECES]; // all potential captures of the given piece
int256 victimMask[NPIECES];   // all potential captures performed by the given piece

int attacker[256];  // move decoding, contains (i%32)/2
int victimNr[256];  //                contains (i&1) + 2*(i/32)
int shift[NPIECES]; // contains 32*(i/2) + (i&1)
int loc[NCOLOR][NPIECE]; // square number where piece stands
int board[128];          // number of piece that stands on square 
int view[128][8]; // distance to nearest neighbor of square in each direction

for(moveSet = captures[mine]; moveSet != 0;) { // loop over captures
  // extract next MVV/LVA capture
  moveNr = LowestBit(moveSet); // returns number of bit
  moveSet &= ~ONE << moveNr;
  // decode move
  piece  = attacker[moveNr];
  victim = victimNr[moveNr];
  from = loc[mine][piece];
  to   = loc[his][victim];
  // make move
  board[to]   = piece;
  board[from] = EMPTY;
  loc[mine][piece] = to;
  loc[his][victim] = ABSENT;
  // update capture set:
  // get attackers and protectors of to-square
  att  = captures[mine] >> shift[victim] & 0x55555555;
  prot = protects[his]  >> shift[victim] & 0x55555555;
  // delete moves with the captured piece, and attacks on it
  captures[his]  &= ~victimMask[victim];
  captures[mine] &= ~attackerMask[victim];
  protects[his]  &= ~victimMask[victim] & ~attackerMask[victim];
  // remember slider moves to from-square before deleting them from captures sets
  myExtend = protects[mine] >> shift[piece] & SLIDERMASK; // own sliders attacking from-square
  hisExtend = captures[his] >> shift[piece] & SLIDERMASK; // enemy sliders attacking from-square
  // delete (pseudo-)captures that mover could make from its old location
  captures[mine] &= ~victimMask[piece];
  protects[mine] &= ~victimMask[piece];
  // delete (pseudo-)captures on the mover in its old location (before extending, so that we do not clear an extended attack from behind)
  captures[his]  &= ~attackerMask[piece];
  protects[mine] &= ~attackerMask[piece];
  // extend slider moves over evacuated squares, first his ('pin punishments')
  while(hisExtend != 0) {
    slider = LowestBit(hisExtend);    // extract next slider
    hisExtend &= ~1 << slider;
    src = loc[his][slider];           // see where it is
    dir = direction[from - source];   // find direction in which it attacks
    distance = view[dir][from];       // find how far beyond from-square next obstacle in this direction is
    dest = from + distance*step[dir]; // calculate location of that new target
    target = board[dest];             // see what stands there
    if(COLOR(target) == mine) {
      captures[his] |= victimMask[slider] & attackerMask[target];
    } else if(COLOR(target) == his) {
      protects[his] |= victimMask[slider] & attackerMask[target];
    } // 3rd possibility, COLOR = EDGE, can be ignored
  }
  // extend own slider moves over evacuated squares ('discovered threats')
  while(myExtend != 0) {
    slider = LowestBit(myExtend);     // extract next slider
    myExtend &= ~1 << slider;
    src = loc[mine][slider];          // see where it is
    dir = direction[from - source];   // find direction in which it attacks
    distance = view[dir][from];       // find how far beyond from-square next obstacle in this direction is
    dest = from + distance*step[dir]; // calculate location of that new target
    target = board[dest];             // see what stands there
    if(COLOR(target) == his) {
      captures[mine] |= victimMask[slider] & attackerMask[target];
    } else if(COLOR(target) == mine) {
      protects[mine] |= victimMask[slider] & attackerMask[target];
    } // 3rd possibility, COLOR = EDGE, can be ignored
  }
  // make mover inherit attacks on to-square
  captures[his] |= prot << shift[piece];
  protects[mine] |= att << shift[piece];
  // update nearest-neighbor map due to evacuation of from-square
  for(dir=0; dir<4; dir++) {
    int upDist = view[from][dir], downDist = view[from][dir+4];
    int up = from + upDist*step[dir], down = from - downDist*step[dir];
    view[up][dir+4] = view[down][dir] = upDist + downDist;
  }
  // generate moves of piece from its new location

  ...  

}

[stegemma]

As a first attempt, it looks almost complete. It seems to me that it could be very efficient (maybe with some bottle-neck for 256 bit data). It's an impressive work, in so little time.

[hgm]

Well, many details are still missing. And most things I had already been thinking about; it was just the idea to make the move list a single 256-bit set in MVV/LVA order that was new, and made it all come together. Before I was thinking about a two-level approach, keeping the set of attackers per square, instead of per victim (which would make inheriting each others attackers easier), and a bitmap of victims that would indicate which victims were attacked (which would then cause their attackers sets to be examined). I guess for the game with 96 pieces that I am really interested in I still would have to do something that, as a set of 96x96 bits would be so large that even attacking the least-significant set bit would require quite inefficient looping. I am not even sure this would not be a problem for the 256-bit sets.

And I already found an error: the numbering of attackers and victims is not consistent, and one of those would have to be inverted. (i.e. initializing the victims[] array the other way around). Low move numbers would be extracted first, and should thus correspond to high victims or low attackers.

The nice thing about this approach is not only that it is fast, but that it can be made even faster by skipping parts of it. After the moves of the captured piece have been deleted, and its slider moves have been extended, captures[his] has been fully updated. So you could extract the first opponent move at that point, to check the value of the victim, and thus whether he has a capture that could possibly push you below beta. If he has not, and it is obvious even without calculating the mobility term that stand pat also won't do it, the move can be discarded before updating captures[mine] (i.e. extending your own sliders, letting the mover inherit the attacks on the victim, calculating its new moves...)

If the opponent has no non-futile captures, but might conceivably be able to stand pat, you would have to evaluate the mobility term to make sure. In that case you would have to extend your own sliders, to get their mobility gain, and calculate the new moves of the mover to get its mobility. So you could not skip anything, but even then the calculation gives you the mobility as a side effect very cheaply.

The new moves of the mover can be efficiently calculated by means of the nearest-neighbor table:

Code: Select all

range[NPIECES][8]; // range in each of the 8 major directions of the given piece

  // generate moves of piece from its new location
  for(dir=0; dir<8; dir++) {
    int dist = view[to][dir];
    if(dist <= range[piece][dir]) {
      dest = to + dist*step[dir];
      target = board[dest];
      if(COLOR(target) == his)
        captures[mine] |= victimMask[piece] & attackerMask[target];
      else if(COLOR(target) == mine)
        protects[mine] |= victimMask[piece] & attackerMask[target];
    }
  }

So even for slides there is no ray scan, but the single piece you have to actually generate moves for 'leaps' directly on the first obstruction along the ray. It is also easily adapted for finite-range sliders, which is important for Shogi variants, where many pieces have slides of maximally 2, 3 or 5 squares in some directions. King and Pawns can have range = 1 (we are only using this for their captures moves!). Only Knight moves do not fit in this scheme. So you would have to test first if 'piece' is a Knight, and use a different piece of code to generate the moves when it is.

Also note that getting the bit describing a single move as victimMask[piece] & attackersMask[victim], ANDing 256-bit sets, could be replaced by a shift: (int256) attackerBit[piece] << shift[victim]. The latter might be less taxing on the memory system, as the attackerBit could be tabulated as a 32-bit int.

[stegemma]

[...]

Code: Select all

range[NPIECES][8]; // range in each of the 8 major directions of the given piece

  // generate moves of piece from its new location
  for(dir=0; dir<8; dir++) {
    int dist = view[to][dir];
    if(dist <= range[piece][dir]) {
      dest = to + dist*step[dir];
      target = board[dest];
      if(COLOR(target) == his)
        captures[mine] |= victimMask[piece] & attackerMask[target];
      else if(COLOR(target) == mine)
        protects[mine] |= victimMask[piece] & attackerMask[target];
    }
  }

[..]

I don't know if this could give some more information or just avoid some jump:

Code: Select all

      target = board[dest];
      capt_prot_empty[COLOR(target)][mine] |= victimMask[piece] & attackerMask[target];

The idea is to merge captures and protect in a single array, with 3 entries: one for "his" color, one for "mine" color and one for "empty" color. Maybe the "empty" section of the array could give some extra information that could be used or just discarded?

[hgm]

Indeed, it would be better if 'captures' and 'protects' were two rows of the same array. In the code above, there is no possibility that the 'target' of a move is EMPTY, as the nearest-neighbor table directly points you to an occupied square. But there is the possibility that the target is EDGE, i.e. off board. And when generating Knight moves (or in general, leaper moves), it would also hit upon empty squares. So I guess they should be part of an array of 4 elements, two of them dummies.

Or perhaps EMPTY and EDGE could just test as WHITE or BLACK, but with a piece number that has a 0 attackerMask. I guess this is a shortcoming of the code as presented anyway, that it assumes that white and black pieces are similarly numbered, so that there really is no way for COLOR() to distinguish them. If the board[] does contain color information, it should have been added when performing the move through board[to] = piece (e.g. board[to] = piece | (mine << 4)).

[hgm]

This is the improved version, doing away with 'protects', making it just another element of the 'captures' array:

Code: Select all

const int256 ONE = 1;

typedef enum { Pawn1=0, Pawn2, Pawn3, Pawn4, Pawn5, Pawn6, Pawn7, Pawn8,
               Knight1, Knight2, Bishop1, Bishop2, Rook1, Rook2, Queen1, King } PieceNumber;

int256 captures[NCOLOR][NCOLOR]; // bitmap of all (pseudo-)captures in MVV/LVA order of 1st color on 2nd
int256 attackerMask[NPIECES];    // bitmap of all potential captures of the given piece
int256 victimMask[NPIECES];      // bitmap of all potential captures performed by the given piece

PieceNumber attacker[256];  // move decoding, contains (i%32)/2               { 0,0,1,1,2,2,...15,15,0,0,1,1,...}
PieceNumber victimNr[256];  //                contains (i&1) + 14 - 2*(i/32)  { 14,15,14,15,...14,15,12,13,12,13,...}
int shift[NPIECES];         // contains 224 - 32*(i/2) + (i&1)                { 224,225,192,193,160,161,...32,33,0,1 }
int loc[NCOLOR][NPIECE];    // square number where piece stands
int range[NPIECE][8];       // indicates for each direction whether given piece steps or slides (or neither) there
int board[128];             // number and color of piece that stands on square 
int view[128][8]; // distance to nearest neighbor of square in each direction

for(moveSet = captures[mine][his]; moveSet != 0;) {
  // extract next MVV/LVA capture
  moveNr = LowestBit(moveSet); // returns number of bit
  moveSet &= ~ONE << moveNr;
  // decode move
  piece  = attacker[moveNr];
  victim = victimNr[moveNr];
  from = loc[mine][piece];
  to   = loc[his][victim];
  // futility pruning
  if(depth <= 1 && currentEval + pieceValue[victim] < alpha - MARGIN) break; // we can stop when we get to futile victims
  // update capture set:
  // get attackers and protectors of to-square
  att  = captures[mine][his] >> shift[victim] & 0x55555555;
  prot = captures[his][his]  >> shift[victim] & 0x55555555;
  // delete moves with the captured piece, and attacks on it
  captures[his][mine] &= ~victimMask[victim];
  captures[mine][his] &= ~attackerMask[victim];
  captures[his][his]  &= ~victimMask[victim] & ~attackerMask[victim];
  // remember slider moves to from-square before deleting them from captures sets
  myExtend = captures[mine][mine] >> shift[piece] & SLIDERMASK; // own sliders attacking from-square
  hisExtend = captures[his][mine] >> shift[piece] & SLIDERMASK; // enemy sliders attacking from-square
  // delete (pseudo-)captures that mover could make from its old location
  captures[mine][his]  &= ~victimMask[piece];
  captures[mine][mine] &= ~victimMask[piece];
  // delete (pseudo-)captures on the mover in its old location (before extending, so that we do not clear an extended attack from behind)
  captures[his][mine]  &= ~attackerMask[piece];
  captures[mine][mine] &= ~attackerMask[piece];
  // extend slider moves over evacuated squares, first his ('pin punishments')
  while(hisExtend != 0) {
    slider = LowestBit(hisExtend);    // extract next slider
    hisExtend &= ~1 << slider;
    src = loc[his][slider];           // see where it is
    dir = direction[from - source];   // find direction in which it attacks
    distance = view[from][dir];       // find how far beyond from-square next obstacle in this direction is
    dest = from + distance*step[dir]; // calculate location of that new target
    target = board[dest];             // see what stands there
    captures[his][COLOR(target)] |= victimMask[slider] & attackerMask[TYPE(target)];
  }
  // at this point all opponent captures are known
  // so we can easily check if our move was legal
  if(captures[his][mine] >> shift[King] & 0x55555555) goto illegalMove; // the move put/left us in check, and thus was illegal
  // and we can determine if he has any captures that could push us below beta
  if(depth <= 1) { // TODO: also check if opponent has promotions!
    int mvv = victmNr[LowestBit(captures[his][mine])];
    score = currentEval + pieceValue[victim] - pieceValue[mvv] - MARGIN;
    if(score > beta) goto skipMove; // fail high without searching if all resistance is futile
  }
  // make move
  board[to]   = COLORED_PIECE(piece,mine);
  board[from] = EMPTY;
  loc[mine][piece] = to;
  loc[his][victim] = ABSENT;
  // extend own slider moves over evacuated squares ('discovered threats')
  while(myExtend != 0) {
    slider = LowestBit(myExtend);     // extract next slider
    myExtend &= ~1 << slider;
    src = loc[mine][slider];          // see where it is
    dir = direction[from - source];   // find direction in which it attacks
    distance = view[from][dir];       // find how far beyond from-square next obstacle in this direction is
    dest = from + distance*step[dir]; // calculate location of that new target
    target = board[dest];             // see what stands there
    captures[mine][COLOR(target)] |= victimMask[slider] & attackerMask[TYPE(target)];
  }
  // make mover inherit attacks on to-square
  captures[his][mine] |= prot << shift[piece];
  captures[mine][mine] |= att << shift[piece];
  // update nearest-neighbor map due to evacuation of from-square
  for(dir=0; dir<4; dir++) {
    int upDist = view[from][dir], downDist = view[from][dir+4];
    int up = from + upDist*step[dir], down = from - downDist*step[dir];
    view[up][dir+4] = view[down][dir] = upDist + downDist;
  }
  // generate moves of piece from its new location
  if(IS_KNIGHT(piece)) { // leapers
    for(dir=0; dir<8; dir++) {
      dest = from + knightStep[dir]; // kludge: knightStep could be stored as range[Knight]?
      target = board[dest];
      captures[mine][COLOR(target)] |= victimMask[piece] & attackerMask[TYPE(target)];
    }
  } else {
    for(dir=0; dir<8; dir++) {
      int dist = view[from][dir];
      if(dist <= range[piece][dir]) {
        dest = from + dist*step[dir];
        target = board[dest];
        captures[mine][COLOR(target)] |= victimMask[piece] & attackerMask[TYPE(target)];
      }
    }
  }
}

Selective generation of checks is also comparatively cheap: there could be tables for Rooks and Bishops to indicate how far they are removed from the points where they could potentially check, and how far the King is removed from those, as a function of their location relative to the King. E.g. for Re4 and Kg8 the potential checking squares would be g4 and e8, and the table would contain (2 right, 4 backward) and (4 forward, 2 left). The coude could then compare the 'view' from the nearest-neighbor array in the tabulated directions, from both the Rook and the King, to check if they are indeed looking upon g4 or e8. (And if the distance from the Rook is just enough, check if the occupant of e8 is capturable.)