Questions about chess programming from a newbie

[hgm]

Btw, I guess that even without this attack-map complexity, there could be gain in a scheme that moves move generation to the parent node. I.e. instead of the usual

Code: Select all

int QS(int stm)
{
    Move moveList[256];
    int nr = GenerateCaptures(stm, moveList);
    for&#40;next = 0; next < nr; next++) &#123;
      move = moveList&#91;next&#93;;
      int from = FROM&#40;move&#41;; // decode move
      int piece = board&#91;from&#93;;
      MakeMove&#40;move&#41;;
      score = -Search&#40;!stm&#41;;
      UnMake&#40;move&#41;;
    &#125;
&#125;

you could do

Code: Select all

int QS(int stm, Move *moves, int nr, Move previousPly)
{
    Move moveList[256];
    int oppoNr = -1; // kludge to flag moves have not been generated yet
    for&#40;next = 0; next < nr; next++) &#123;
      move = moveList&#91;next&#93;;
      int from = FROM&#40;move&#41;; // decode move
      int to = TO&#40;move&#41;;
      if&#40;TO&#40;previousPly&#41; == from&#41; continue; // skip moves of captured piece
      if&#40;FROM&#40;previousPly&#41; == to&#41; &#123;
        int piece = board&#91;from&#93;;
        if&#40;!IS_SLIDER&#40;piece&#41;) continue; // move to old from-square is no longer capture
        to = Extrapolate&#40;from, to&#41;; // elongate slider move
        if&#40;Color&#40;board&#91;to&#93;) != !stm&#41; continue; // unblocked slider hits nothing
      &#125;
      if&#40;oppoNr < 0&#41; oppoNr = GenerateCaptures&#40;!stm, moveList&#41;; // opponent moves!
      MakeMove&#40;move&#41;;
      score = -Search&#40;!stm, moveList, oppoNr, move&#41;; // pass move listto all daughters
      UnMake&#40;move&#41;;
    &#125;
&#125;

So you would have moved the generation of moves one level up to share the work, but then you would have to skip the moves of the piece that was captured when you use that list in the daughter.

There is still one omission in this, however: the preceding capture changed the color of the occupant of its to-square, so that moves that before where pseudo-captures to this square (and thus were not in the shared move list) would now become real captures. So in the daughter we could simply skip the moves of the captured piece, but we would have to supplement the shared move list with two kind of moves:

1) recaptures
2) pin punishments (slider captures over the evacuated square)

The shared move list could have already been sorted MVV/LVA-wise in the parent that generated it, to also share the sorting effort. Where the recaptures would fit in is easily determined, as they all have the moved piece as victim. It is not obvious how to generate those, though. (Perhaps doing a 0x88 attack test with all non-Pawns in the stm's piece list, and testing 2 board squares for Pawns.) The pin punishments are already in the shared move list, but with a wrong to-square. And they are sorted by what is on that to-square. This is an even more nasty problem, as the target might have grown more valuable. (If it was less valuable we could simply postpone the move when we encounter it; in practice we are likely to have a mechanism of postponing HxL captures anyway.) It would be unfortunate if we had to run through the complete move list to find captures of the piece that moved away, to elongate the slider captures and determine the victim values before we could search any moves. It might be cheaper to run through the slider section of the stm piece list to determine through a 0x88 test which of those were attacking the the previous from-square than to dig that out of the move list. Still, genrating pin punishments by 0x88 tests on up to 5 sliders, and recaptures by up to 8 such tests and two board probes for Pawns seems cheaper than a full move generation.

This still fails to exploit that the pin punishments and the recaptures could actually be shared too, amongst sibling nodes. Not as widely as the list of opponent captures (which would actually be the ove list in the null-move daughter), but there could be a piece that makes several captures. And then each of the daughters reached by these captures would have the same pin punishments. Similarly, an opponent piece couldbe captured in different ways, and then the recaptures could be shared between those daughters.

So it could actual pay to keep an administration of pin punishments for each from-square and recaptures for each to-square, that tells you if that from or to-square has already been used in the current node. If not, you could generate the pin punishments or recaptures for it, append those to the move list, but store the move-list index of first and last such move with the square to which they apply. And pass them to the daughter node. If that same square was then used again, you could pass the indexes straight away, without having to generate the moves again.

So the move list would be passed to the daughter in 3 parts: the list from their null-move sibbling (the same for all) with some moves in it they would have to skip, the recaptures, and the pin punishments. The latter could also be sorted MVV/LVA, so that the only sorting left to do in the daughters is basically merge these lists, i.e. compare the MVV/LVAkey of the leading element of each of them, and take the best. Note that generating and sorting the lists in the parent would actually already tell the parent if there would be any non-futile captures in the daughter. If there are not, it can prune the move to that daughter straight away.