https://talkchess.com/forum3/viewtopic.php?t=76773

--------------------------------------------------------------------------------
Perhaps it is a good idea to introduce some of the more advanced concepts before starting to code and present actual searches. So let me start with this:

Neighbor Table

The neighbor table is an array indexed by square number and direction. For every occupied square it holds the square number of the nearest occupied square in that direction. There is a rim of 'edge guards' around the board on 'virtual squares' just beyond the edge; this excludes simple 0-63 square numbering, but requires at least a 10x10 board.

For convenience of saving / restoring elements of the neighbor table, the 8 neighbors of a given square would be packed as bytes into one 64-bit word. The table would have to be updated every time a square is evacuated (easy), or occupied (hard). Fortunately in QS squares only get evacuated; on the destination the attacker replaces the victim. (Forget e.p. for now.)

Code: Select all

typedef union {
  unsigned char dir[8]; // indexed by direction number
  uint64_t all;
} Neighbors;

Neighbors neighbor[10*10]; // neigbor table (8x8 playing area, plus surrounding rim)

void Evacuate(int sqr)
{
  int i;
  for(i=0; i<4; i++) { // for all orientations
    int up = neighbor[sqr].dir[i];   // upstream neighbor
    int dn = neighbor[sqr].dir[i+4]; // downstream neighbor
    neighbor[up].dir[i+4] = dn;      // let those see each other
    neighbor[dn].dir[i] = up;
  }
}

void Reoccupy(int sqr)
{ // for 'unmaking' Evacuate()
  int i;
  for(i=0; i<4; i++) { // for all orientations
    int up = neighbor[sqr].dir[i];   // upstream neighbor
    int dn = neighbor[sqr].dir[i+4]; // downstream neighbor
    neighbor[up].dir[i+4] = sqr;     // let those see the given square
    neighbor[dn].dir[i] = sqr;
  }
}

Of course the loops over the four ray orientations would be unrolled in practice; there would be no looping or branching here.

The neighbor table is very useful for generating slider captures: it tells you directly where the potential victims are in the directions the slider can move in. No need to scan through a possibly large number of empty squares to find them. It also makes it relatively easy to calculate the mobility of a piece: just sum the distances between the square the piece is on, and its neighbors.

Attack Map

The attack map attackers[victim] indicates which pieces attack the given victim. This is indicated as an integer where each bit corresponds to a certain attacker, and would be set to 1 if that attacker indeed can capture the given victim. The bits are assigned in order of increasing attacker value, such that standard bit-extraction techniques (which find the least-significant 1 bit first) would extract the attackers in LVA order. This makes the attack map very suitable for generating captures: just run through the opponent's piece list to visit potential victims in MVV order, and for each victim extract the attackers in LVA order.

The attack map is also very helpful in updating itself after a move: discovered slider moves all went to the square evacuated by the move, and will thus be recorded in the old attack-map element for the moved piece. We can mask out the slider attackers from that, extract them one by one to get their piece numbers, look up their location, look up in which direction this is relative to the evacuated square, and displace the attack to the neighbor in the opposit direction. Sounds a bit cumbersome, but the upside is that usually you have to do it zero times, because the moved piece was not blocking any sliders.

The Present Mask

The attack map defines a mapping of pieces on bits; we can use the same mapping to keep track of which pieces are still present, and which are currently captured. If we AND the attack-map elements each time we use those with this 'present mask', there is no need to update the map for the disappearence of the moves of captured pieces. We can also use the present mask when we want to loop over the piece list, skipping the captured pieces, by extracting the bits for the pieces that are present, and only processing those.
--------------------------------------------------------------------------------
Knowing where the non-royal pieces are is useful in move generation. If you have only a few pieces on the board, having to loop through all 64 squares to find them is relatively expensive. A piece list for Chess has only 16 entries (at worst) for each color, so even when you leave all captured pieces in there too, you will find your own pieces 4 times faster. But you could compact the list in the root to squeeze out captured pieces, so that only the pieces that were captured in the search provide overhead. Or you could loop through the list non-sequentially, by having each piece specify its non-captured successor, and go directly to that. This would provide some extra overhead when updating the list for a capture.

Another common application is for detecting pinned pieces. You could do that by scanning the board away from the King in 8 directions, to the second obstacle, in order to test whether that is a slider that moves in the corresponding direction. But it is faster to loop through (maximally) 5 sliders, and test whether any of these is aligned with the King, through a table aligned[sliderSqr][kingSqr] that tells you the direction of the connecting ray, if there is one. Usually there will be no alignment, or an unsuitable alignment (e.g. diagonal, while the slider was a Rook), and then you are done. Only if there is an alignment you would have to verify there is exactly one piece between the two. And depending on its color that would then be a pinned piece. (And you could exclude that from the normal move generation, to avoid generating illegal moves.) But to do this you would have to know where all the sliders are; if you would have to scan the board for that it would defeat the purpose.

In a more advanced evaluation it could be useful to know where pieces are. E.g. are your Rooks on open files? Are my Bishop and the opponent's on the same square shade? If I have Bishop + Pawn, is it a Rook Pawn and a Bishop of the wrong shade?

If your mailbox board contains the piece types, it is not easy to maintain a complete piece list. Because there will be multiple pieces of the same type, and if one of those moves or gets captured, you would not immediately know what entry in the piece list should be used for updating its location. You could still use a 'semi-piecelist', though. That just requires two extra statements in MakeMove() and UnMake(). E.g. for MakeMove():

Code: Select all

piece = board[fromSqr]; victim = board[toSqr]; // save for unmake
board[toSqr] = piece; board[fromSqr] = EMPTY; // update board
location[piece] = toSqr; location[victim] = CAPTURED; // update (semi-)piece list

Since all pieces of the same type would map to the same entry in location[], this would only work when there is a single piece of the corresponding type left. But since you start with only a single King, it would always be useful for the King. It could also be useful when by other means (e.g. by keeping counters for how many pieces of each type there are) you have established that you are in an end-game with only a single piece of the relevant type (e.g. KPK), and want the evaluation to calculate whether the Pawn can still be stopped. Or whether in KBPPPKBPP the Bishops are on the same or different square shade. I use this method in KingSlayer.

But the commonly used solution is to not populate the mailbox board directly with piece types, but with piece numbers. Where the two Rooks would then get 2 different numbers, etc. If you want to know the type of a piece of given number, you can get it from a table pieceType[pieceNr]. But most of the time there is no need to do that, as you could tabulate properties of the pieces not by type, but by piece number. So that you can directly lookup (say) pieceValue[pieceNr] instead of pieceTypeValue[pieceType[pieceNr]].
--------------------------------------------------------------------------------
Some Design Details [revised once]

Perhaps running ahead of myself, I will already specify some details of how the attack map in the 'ultimate design' should work.

Pieces will be encoded by numbers, 16-31 for the white pieces, 32-47 for the black pieces. Empty squares will be 0. For simplicity all piece lists will have 48 elements. (No matter what info about the piece they contain; I suppose some infos would never be used for an empty square, and in principle the lists for these could be reduced to 32 elements, and accessed as table[pieceNr-16].) The entries 1-15 would never be used, but treating 0 as a piece makes that we don't really have to make a distinction between captures and non-captures in MakeMove(). We just give the empty square a piece value 0, and a PST and Zobrist table of all zeros. That saves if-statements to test for captures, and most moves will be captures anyway.

The attack map attackers[80] will consist of 64-bit integers. The attackers of piece number n will be stored in attackers[n], its protectors in attackers[n+32]. The reason for using the same array for this is that it is then easier to indicate which members of the attack map have been changed, and how (to facilitate unmake). When piece A captures piece B, it inherits the attackers and protectors of the latter (apart from itself), but swaps those.

The bits representing the attackers are layed out in the word as COMB = 0x1111111111111111. The least-significant of these are the Pawns, the most-significant is the King, so the bits will extract in LVA order. The remaing bits are unused, and will always be 0. Sliders can be isolated by ANDing with 0x0FFFFF0000000000, which kills King, Knights and Pawns.

There is a slight inconvenience: piece sets representing victims cannot have the same layout as piece sets representing attackers. This because we want the bits to extract in opposit order: MVV vs LVA. There are no sets of victims in the attack map, but the attackedMask associates a bit with each victim, for indicating whether the relevant part of the attack map for that victim is non-zero. (Where 'relevant' means attacker rather than protector, and currently not captured.) Since the format cannot be the same, there is also no need to make the attackedMask 64 bits; a normal 32-bit integer suffices for the 2x16 pieces.

During move generation the attackers of the victims in a certain value group will have to be combined, and the protectors removed, before extracting the attackers in the (combined) LVA order. This explains the COMB pattern: it makes it easy to interleave the attackers of up to 4 pieces. (The value group for Pawns has 8 of those, so there we need a different trick.) We can use the attackedMask to loop through the attacked opponent pieces, and add it to the combined attack set after left-shifting it by an amount (0, 1, 2 or 3) determined by the victim, until we get to the next value group. Then we can extract the captures from the combined attackers sets in LVA order to get the captures before we continue. Somewhat like

Code: Select all

int victimSet = attackedMask & playerMask[xstm]; // opponent pieces with attacks on them

int oldg = -1; // invalid group number
uint64_t attackerSet = 0; // collects the attackers for a value group
while(victimSet) {
  int v = NrOfTrailingZeros(victims);
  int victim = bit2victim[v];  // next attacked piece
  int g = group[victim]; // value group it belongs in
  if(g != oldg) { // we got to a new value group; flush the old one
    Flush(attackerSet); // generate all captures for this value group of victims in MVV/LVA order
    oldg = g; // remember last group we did. Note that attackerSet is again empty at this point
  }
  attackerSet |= attackers[victim] << shift[victim]; // merge the attacks on this victim with the total set
  victimSet &= victimSet - 1;
}
Flush(attackerSet); // generate captures of final value group of victims


void Flush(uint64_t attackerSet)
{
  while(attackerSet) { // first time this is still zero
    int a = NrOfTrailingZeros(todo); // extract a capture (MVV/LVA order)
    int piece = bit2attacker[a];      // attacker
    int victim = capt2victim[a] + oldg; // victim
    int fromSqr = location[piece];
    int toSqr = location[victim];
    SearchMove(fromSqr, toSqr, piece, victim); // process the move
    attackerSet &= attackerSet - 1; // remove this capture
  }
}

--------------------------------------------------------------------------------
Handling the Leaf Nodes

This is some sample code for handling the leaf nodes where no non-futile captures are available. These nodes are expected to be the most common in the tree (possibly by far), so the project focuses on making the search of those as fast as possible. The strategy is to not do any update of the attack map before we are sure there are captures to search. We just make an updated copy of the presentMask of the stm's pieces (as the preceding move made one of those disappear), and an updated copy of the attackedMask that accounts for our attacks on the just moved piece (the 'recaptures'), and the punishing of moving away a (soft-pinned) piece, by extending the stm's old slider attacks on the moved piece to the next target downstream.

There is still one flaw in this: it does not update the attackedMask for the captures that could be made by the piece that was just captured. Updating the presentMask for the disapperence of it would prevent we generate moves for that piece, but we still would attempt it. If there were no other attackers of that same victim, we would then be wasting our time. Worst of all, we might overlook that there are no non-futile captures at all, and waste time on fully updating the attack map. The old attacks of the captured piece are scattered all over the map, though, and it would require move generation for that piece to know which victims it was hitting. I will have to ponder about this...

Code: Select all

#define WHITE 16    // white pieces 16-31; 16-23 = Pawns, 31 = King
#define BLACK 32    // black pieces 32-47

int location[48];   // piece list: square the given piece is on

typedef uint64_t PieceSet;

PieceSet attackers[2*48];             // the attack map: attackers and protectors of the given piece
#define COMB    0x1111111111111111ull // valid bits in attack-map elements (KQRRBBNNPPPPPPPP)
#define SLIDERS 0x0FFFFF0000000000ull // bits for slider attackers

PieceSet presentMask[33]; // non-captured attackers; only elements 16 (white) and 32 (black) are used

PieceSet piece2aBit[48] = { // encoding of attackers in attack map
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  1ull<<0,  1ull<<4,  1ull<<8,  1ull<<12, 1ull<<16, 1ull<<20, 1ull<<24, 1ull<<28, // white pieces (PPPPPPPP)
  1ull<<32, 1ull<<36, 1ull<<40, 1ull<<44, 1ull<<48, 1ull<<52, 1ull<<56, 1ull<<60, //              (NNBBRRQK)
  1ull<<0,  1ull<<4,  1ull<<8,  1ull<<12, 1ull<<16, 1ull<<20, 1ull<<24, 1ull<<28, // black pieces
  1ull<<32, 1ull<<36, 1ull<<40, 1ull<<44, 1ull<<48, 1ull<<52, 1ull<<56, 1ull<<60  // (same as white!)

int bit2attacker[64] = {  // decoding of bits in attackers[] and presentMask[]
  0,  0,  0,  0,  1,  1,  1,  1,  2,  2,  2,  2,  3,  3,  3,  3,
  ...                                   ..., 14, 15, 15, 15, 15
};

int attackedMask; // pieces that curently are attacked (both colors)

int piece2vBit[] = { // encoding of victims in attackedMask
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  1<<15, 1<<14, 1<<13, 1<<12, 1<<11, 1<<10,  1<<9,  1<<8, // white victims in low-order 16 bits
  1<<7,  1<<6,  1<<5,  1<<4,  1<<3,  1<<2,   1<<1,  1<<0,
  1<<31, 1<<30, 1<<29, 1<<28, 1<<27, 1<<26, 1<<25, 1<<24, // black victims in high-order 16 bits
  1<<23, 1<<22, 1<<21, 1<<20, 1<<19, 1<<18, 1<<17, 1<<16
};

int playerMask[33] = { // colors in attackedMask; only elements 16 (white) and 32 (black) are used
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0xFFFF,  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0xFFFF0000
};

int nonFutiles[] = { // victim sets in attackedMask that are non-futile for various gaps
  0xFFFFFFFF, 0x00FF00FF, 0x00FF00FF, 0x00FF00FF, 0x000F000F, 0x000F000F,
  0x00030003, 0x00030003, 0x00030003, 0x00030003, 0x00030003, 0x00030003  // only K & Q
};

// fromSqr, toSqr, piece and victim represent the move that led to the current node

  // calculate updated presentMask (for disappearence of the captured piece)
  PieceSet newPresence = presentMask[stm];    // attacker bits of stm's non-captured pieces
  newPresence &= ~piece2aBit[victim];         // remove the just-captured piece from it

  // calculate attackedMask update for stm's captures
  int moverBit = piece2vBit[piece];           // victim bit for the mover
  int newAttacked = attackedMask & ~moverBit; // remove any previous attacks on mover
  PieceSet protects = attackers[victim+48];   // protectors of (now captured) victim
  protects &= newPresence;                    // limit to those still present
  newAttacked |= (protects ? moverBit : 0);   // those become attackers of the capturer
  int disc = 0;                               // no discovered attacks yet
  PieceSet pinnerSet = attackers[piece];      // (stm's) attackers of evacuated square
  pinnerSet &= SLIDERS & newPresence;         // limit to sliders that are not currently captured
  while(pinnerSet) {                          // the common case is an empty pinnerSet: do 0 times!
    int n = NrOfTrailingZeros(pinnerSet);     // extract next slider attack
    int pinner = bit2attacker[n] + stm;       // piece number of attacker
    int src = location[pinner];               // square attack comes from
    int d = dirTable[src - fromSqr + OFFSET]; // direction of attack (OFFSET prevents negative index)
    int dest = neighbor[fromSqr].dir[d];      // location of downstream obstacle
    int anchor = board[dest];                 // piece that is there
    if(anchor != EDGE) {                      // can also run into edge
      PieceSet b = piece2vBit[anchor];        // victim bit for the new target
      b &= playerMask[xstm];                  // kill it if the target is a friend
      newAttacked |= b;                       // otherwise, mark target as attacked
      discovered[disc] = anchor;              // remember this pin to facilitate later update of attack map
      source[disc++] = pinner;
    }
    pinnerSet &= pinnerSet - 1;               // one more done, clear its bit
  }

  // we now know which pieces we attack; test for non-futiles amongst those
  int gap = alpha - curEval;                  // how much do we need to up the eval to alpha?
  if(gap > QUEENVALUE + MARGIN) return alpha; // hopeless if we must capture more than Queen
  gap = (gap < 0 ? 0 : gap >> 6);             // piece values chosen so they are close to multiples of 64
  todo = newAttacked & nonFutiles[gap];       // mask away futile victims
  todo &= playerMask[xstm];                   // leave only opponents
  if(!todo) return alpha;                     // no non-futile captures exist; fail low
  

At this point we would be done with the node. Only when there are non-futile captures (so that this is not a leaf node), we would now have to fully update the attack map, not only for our own captures, but also for those of the opponent.
--------------------------------------------------------------------------------
The Targets Map

Perhaps it is a good idea to also keep the existing captures per attacker, next to the attackers[] array that stores them per victim. Basically the attack map is a 32x32 array of bits. The attackers[] array stores this by row. A copy stored by column would put the targets of a given piece in a single machine word.

So we could maintain an array targets[2*48] very similar to attackers[], indexed by the piece number (for the enemy targets) or piece + 48 (for the friends it protects). The used bits would be spaced out according to the same COMB pattern, except that their association with pieces runs in the reverse order. (Because we are using this info for victims, which we want to extract in order of decreasing value.)

Instead of keeping track of the pieces that are under attack in a single 32-bit integer attackedMask, we could split the attacks on white and on black pieces over two 64-bit integers, attackedMask[WHITE] and attackedMask[BLACK]. These could be organized as 16 packed 4-bit counters, which register the number of attacks on the corresponding piece. We can still extract bits from such a packed set of counters in the usual way, when we map all bits of a given counter to the same piece number. It is just that after finding one non-zero bit, we have to clear all bits of the counter it belonged to, before attempting to find the next non-zero counter.

The attackedMask[color] then becomes the sum of all targets[piece] of the pieces of the opposit color. When a piece gets captured its targets[] can be simply subtracted from the attackedMask. When a piece is moved, the attacks it made from its old location can be similarly subtracted. We would of course have to determine the attacks it makes from its new location. But we have to do that anyway, for updating the attackers[] elements for those targets. This is the unavoidable remnant of move generation: the rules for moving pieces must affect the process somewhere. So from the new location we would have to generate the captures the piece can make (of friends and foes, for attack and protection). Each attack is then recorded twice, by setting the corresponding bits in targets[piece] and attackers[victim]. That is not so much extra work. Once all the moved piece its attacks have been recorded in targets[piece], this can be added to attackedMask to provide the overview of attacked pieces.

The targets[] array can actually help earn the cost of its update back, perhaps even more than that. When a piece moves, the attacks it made from its old location would all have to be removed from the attackers[] sets of its targets. I originally planned to do that by move generation. But when the set of attacks is already specified, we could use bit-extraction to see what was attacked, and apply the modification there. This can be expected to be faster, because move generation might bring you to the board edge in some of the directions the slider moves. But those off-board moves would not be recorded in the targets[] of the piece. The same procedure can be used during unmake. So it is only necessary to generate captures for a piece once, when it is moved to a new location. The record of these moves in the targets[] map can then be used to quickly visit all the targets at other times (i.e. on a later move when the piece moves away again, or on unmaking the move to remove the new attacks and restore the old).
--------------------------------------------------------------------------------
I am starting to like this design more and more. It has a nice symmetry. The basis is formed by 'piece sets', 16 bits representing pieces of one player evenly spread out in a 64-bit word (0x1111111111111111 pattern). When the set represents attackers, the bits are assigned in LVA order, when they represent victims, in MVV order. There are two arrays of such piece sets, indexed by piece number: attackers[victim] and targets[attacker]. Each bit in such an array correspond to one capture, and each capture occurs in each array once. Both arrays have a section for true captures, and an equally large section for 'friendly captures', i.e. protection rather than attack, where both attacker and victim have the same color. (In attackers[victim+FRIENDLY] and targets[attacker+FRIENDLY].) There are 'summaries' attackedMask[color], which contain the sum over all targets[n] for the pieces n of the other color (16 packed 4-bit counters, true captures only).

Updating these data structures when a capture is made requires:
1) removing the captures by the moved piece from its old location
2) adding the captures by the moved piece from its new location
3) removing the attacks by the captured piece
4) adding the attacks on the moved piece in its new location
5) removing the attacks on the moved piece in its old location
6) discovering the slider attacks on the evacuated square
7) discovering the slider protections of the evacuated square

The updates (1), (2) and (7) concern moves of the player that moved, and are needed only 2 ply later, when that player moves again. Only (3-6) are needed for the immediately following ply, and it is not so difficult to do a 'preview' of those updates to see if we will do an immediately following ply. And if we don't, we will never get to the position where we need the updates (1), (2) and (7). We could do that by applying the partial update (3-6), but if that doesn't result in any interesting (non-futile) captures, we must immediately undo them, and wasted a lot of time.

So the idea is to just do the update in (a copy of) the 'summary' attackedMask[opponent], to determine if we will have any worthwile captures. This is only a single 64-bit word, so easily copied. And some of the updates are very easy to do:

For (3) we just subtract the targets[victim] of the victim of the preceding capture. This decrements the 4-bit counter of all the pieces that were attacked by this victim, SIMD fashion, to indicate these now have one fewer attacker.
For (5) we clear the 4-bits counter for the attacks on the moved piece. None of these stays if the piece is no longer there.
For (4) we would need to know how many protectors the captured piece had, as these are now attacking its capturer. We would either have to copy that from a summary of the 'friendly attacks', or count those in the attackers[victim+FRIENDLY]. But as this is not a full update, and we do the preview only to know if we do have a capture, we can just test the latter for being non-zero, and set the counter in attackedMask to 1 in that case. (So no need for popcnt.)
So far this was all pretty trivial. The hardest part is (6). But the old attackers[piece] set of the moved piece tells us which of our sliders were attacking that piece (and thus get discovered now it moves away). Most of the time that will be none at all! So although (6) is hard, on average it will not be expensive. What we do is put the piece numbers of all sliders that were attacking the evacuated square on a stack, together with the piece number of the piece they are now hitting in stead. And if that piece was an opponent, increase the counter for attacks on that opponent in our attackedMask.

This gives a good-enough preview of how the new attackedMask will look to judge if we must search any captures in that node. If not, we are done, and return a fail low. The attack map itself was never changed. We just read 3 elements of it: the targets[] set of the victim, the protectors set of the victim, and the attackers[] set of the evacuated square (to conclude it was not attacked by sliders).

Mobility

It will become a bit harder if the evaluation is not just material + PST, but also includes mobility. To be able to get an exact evaluation for the stand-pat test, we would then have to calculate the mobility change caused by the preceding move. (We will of course calculate mobility incrementally, not from scratch.) Since mobility is a rather small evaluation term, (so that its change has to be that as well), it becomes only of importance when the evaluation is very close to alpha. Which we could hope happens only rarely. In other cases we could either decide to fail high on material + PST score alone (which means the parent would already have futility pruned the node), or decide standing pat is hopeless, and directly proceed with looking for nonfutile captures to make.

If we do need a full evaluation, though, we would need to do (7) in a similar way as (6) was done in the preview, while measuring how far the new targets of the discovered slider moves are behind the evacuated square. The mobility of the individual pieces would be recorded in the piece list, so correcting for the disappearence of the captured piece is trivial, and the old mobility of the moved piece can be discarded in the same way. The hardest part is to calculate the new mobility of the moved piece from scratch: this requires generation of its moves. So we cannot wait with that anymore until we are sure we should update the attack map.

The best solution to this seems to do a move generation that creates the set of victims (without storing it in targets[] yet), while calculating the mobility of this single piece on the side, in the case a full evaluation has to be done. This victim set can then be used in the actual update of the attack map, (if there is to be one), by storing it in targets[mover] and targets[mover+FRIENDLY], and for extracting the victims to add the capture in their attackerd[victim] and attackers[victim+FRIENDLY] attack-map elements.
--------------------------------------------------------------------------------
Well, for the first trial it is of course necessary to also code all the boring parts (which will be recycled for use in the other trials): search, position setup, initialization, piece-square tables, Zobrist keys... I now have cooked up the following, rather minimal context for testing the various mailbox implementations:

Code: Select all

typedef struct {
  uint64_t hashKey, oldKey;      // keys
  int pstEval, oldEval, curEval; // scores
  int alpha, beta;
  int from, to;                  // squares
  int piece, victim;             // pieces
  int depth;                     // depth
} UndoInfo;

int MakeMove(int move, UndoInfo *u)
{
  // decode the move
  u->to = move & 255;
  u->from = move >> 8 & 255;
  u->piece = board[u->from];
  u->victim = board[u->to];

  // update the incremental evaluation
  u->pstEval = u->oldEval - PST(u->piece, u->to) + PST(u->piece, u->from) - PST(u->victim, u->to));
  if(u->depth <= 0 && u->pstEval > u->beta + MARGIN) return -INF-1; // futility (child will stand pat)

  // update hash key, and possibly abort on repetition
  u->hashKey = u->oldHash ^ KEY(u->piece, u->to) ^ KEY(u->piece, u->from) ^ KEY(u->victim, u->to);
  // if(REPEAT) return 0;

  // update board and piece list
  board[u->from] = 0;
  board[u->to]   = piece;
  location[u->piece]  = u->to;
  location[u->victim]   = CAPTURED;

  return INF+1; // kludge to indicate success
}

void UnMake(UndoInfo *u)
{
  // restore board and piece list
  board[u->from] = u->piece;
  board[u->to]   = u->victim;
  location[u->piece]  = u->from;
  location[u->victim] = u->to;
}

int Search(UndoInfo *u) // pass all parameters in a struct
{
  UndoInfo undo;
  int first, curMove, mustSort, noncapts, alpha = u->alpha;
  int *myPV = pvPtr;

  nodeCnt++;

  // QS / stand pat
  if(u->depth <= 0) {
    *pvPtr++ = 0; // empty PV
    if(u->pstEval > alpha - MARGIN) { // don't bother with full eval if hopeless
      undo.curEval = Evaluate(u->pstEval); evalCnt++;
      if(undo.curEval > alpha) {
        if(undo.curEval >= u->beta) { patCnt++; return u->beta; }
        alpha = undo.curEval;
      }
    }
  }

  // generate moves
  noncapts = msp += 70;          // reserve space for new move list
  mustSort = first = MoveGen();
  genCnt++;
  if(!first) { alpha = INF; goto cutoff; } // King capture detected
  if(followPV >= 0) {                      // first branch
    int i, m = pv[followPV++];             // get the move
    if(m) {                                // move to follow
      m |= 255<<24;                        // assign highest sort priority
      for(i=first; i<msp; i++) {           // run through move list
        if(!(m - moveStack[i] & 0xFFFF)) { // search it amongst generated moves
          moveStack[--first] = m;          // prepend to move list
          moveStack[i] = 0;                // zap PV move in list
          break;
        }
      }
    } else followPV = -1;
  }

  // set child & make-move parameters that are always the same
  undo.oldKey  =  u->hashKey ^ STMKEY;
  undo.oldEval = -u->pstEval;
  undo.depth   =  u->depth - 1;
  undo.alpha   = -u->beta;
  stm ^= COLOR;

  // move loop
  for(curMove = first; curMove < msp; curMove++) {
    int score, move = moveStack[curMove];

    // move picker
    if(curMove >= mustSort) { // still has to be sorted
      int i, j = curMove;
      for(i=curMove+1; i<noncapts; i++) { // extract best capture
        int m = moveStack[i];
        if(m > move) j = i, move = m;
      }
      moveStack[j] = moveStack[curMove]; moveStack[curMove] = move;
      mustSort++; // is now sorted
    } else if(u->depth <= 0) { // in QS no non-captures at all
      break;
    } else mustSort = msp;     // suppress further sorting
    if(!move) continue;        // skip zapped moves

    // recursion
    undo.beta = -alpha;
    score = MakeMove(move, &undo); // rejected moves get their score here
    if(score < -INF) break;        // move is futile, and so will be all others
    if(score > INF) { // move successfully made
      score = -Search(&undo);
      UnMake(&undo);
    }

    // minimaxing
    if(score > alpha) {
      int *p;
      if(score >= u->beta) {
        alpha = u->beta;
        break;
      }
      alpha = score;
      p = pvPtr; pvPtr = myPV;    // pop old PV
      *pvPtr++ = move;            // push new PV, starting with this move
      while((*pvPtr++ = *p++)) {} // and append child PV
    }
  }
 cutoff:
  msp = noncapts - 70; // pop move list
  pvPtr = myPV;        // pop PV (but remains above stack top)
  stm ^= COLOR;
  return alpha;
}

void SearchRoot(UndoInfo *u, int maxDepth)
{
  nodeCnt = patCnt = evalCnt = genCnt = 0;
  u->alpha = -INF;
  u->beta  = INF;
  followPV = -1;   // nothing to follow at d=1
  for(u->depth=1; u->depth<maxDepth; u->depth++) { // iterative deepening
    int i, score;
    score = Search(&u);
    printf("%2d %6d %6d %d", u->depth, score, nodeCnt, 0);
    for(i=0; pv[i]; i++) PrintMove(pv[i]);
    printf("\n"), fflush(stdout);
    followPV = 0;  // follow this PV on next search
  }
}

Somewhat unusual characteristics compared to the text-book Search() examples are that I pass the parameters (like alpha, beta, depth) to the child in a structure, which also contains the info about the previous move (from, to, piece, victim), and which is also passed to MakeMove/UnMake. This is basically to provide a shared set of local variables to all these routines.

Before updating the game state MakeMove() calculates the new hash key and incremental evaluation. So that it can abort if the move runs into a repetition, or turns out to be futile. Because of the move sorting (MVV), once a move is futile all subsequent moves in that node will be futile, so we can take an 'alpha cutoff' in that case. The futility is currently purely determined from the incremental evaluation. More accurate in general would be to base it on the full evaluation (of the parent), and guess that of the child by accounting incrementally for the capture. But this assumes a full evaluation will be done in the parent, which also isn't always the case. Perhaps some refinement is still needed here when the evaluation contains large non-incremental terms, to prevent that MARGIN has to be taken too large. (Mobility should not be a problem, though.)

As promised, there is no hash table. There is iterative deepening, searching the PV of the previous iteration as first branch, though. There is a separate SearchRoot() that takes care of the iterative deepening. First time I use this design, btw, so it could be buggy. The PV move is purged from the list of generated moves, and then put in front. (Cumbersome, but only done in the nodes of the first branch.) Captures are searched in MVV/LVA order, after the PV move, by extracting them one by one. There is no sorting of the non-captures. (No killer, no history.) Move ordering is not the focus of this study, but MVV capture ordering is necessary to avoid search explosion in QS.

The search is a simple fixed-depth + QS, (no null move, no LMR), but QS is handled by the same Search() routine, by simply breaking from the move loop when you get to the non-captures, and starting with a stand-pat test for increasing alpha when depth <= 0. One of the things that will be tested is how much is gained by using a dedicated capture-only generator. (From my experience with Joker: this should be a lot!) In some of the implementations to be tested capture generation will be done by move generators of entirely different design anyway, and the 'move picker' section in Search() will have to be drastically altered. (E.g. for staged move generation.)

The move-legality issue is currently addressed by having the move generator test for King capture. Normally it returns the start of the move list (as index in the global moveStack[] array). This is necessary because during generation the list grows in two directions: non-captures are added to the end, captures are prefixed to it. Each node reserves enough space on the move stack to make sure added captures could not overwrite the tail of the move list for the rpevious ply. So only after generation it will be clear where the list starts, and this index is returned. But MoveGen() returns the (invalid) value 0 after detecting a King capture. On which the node can return a +INF score. I did not bother to detect stalemate. Perhaps I should still add a check extension.

Note there is no castling, e.p. capture or promotion. For now I assume such details will not have a large impact on the general speed.
--------------------------------------------------------------------------------
OK, I have debugged everything, and tried the following (very basic) move generator:

Code: Select all

#define WHITE 16
#define BLACK 32
#define COLOR (WHITE|BLACK)   // Also used as edge guards around the board

unsigned char rawBoard[12*16];  // 0x88 board + 2-wide rim of edge guards
#define board (rawBoard + 2*17) // playing area of this board

int stm; // side to move (WHITE or BLACK)

int location[48], offs[48], mvv[48]; // piece list

int firstDir[32] = { // start of move list in steps[] table, per piece
  1, 1, 1, 1, 1, 1, 1, 1, 9, 9, 31, 31, 36, 36, 27, 18,
  5, 5, 5, 5, 5, 5, 5, 5, 9, 9, 31, 31, 36, 36, 27, 18,
};

signed char steps[] = { // board steps for various pieces
  0,
  16, 15, 17, 0,                         //  1 wP
  -16, -15, -17, 0,                      //  5 bP
  31, -31, 33, -33, 18, -18, 14, -14, 0, //  9 N
  16, -16, 1, -1, 15, -15, 17, -17, 0,   // 18 K
  16, -16, 1, -1, 15, -15, 17, -17, 0,   // 27 Q   31 B
  16, -16, 1, -1, 0,                     // 36 R
};

unsigned int moveStack[10000];
int msp; // move stack pointer
#define MOVE(F, T) (256*(F) + (T))

int MoveGen()
{
  int i, first = msp;

  for(i=0; i<16; i++) {                        // loop over pieces
    int piece = stm + i;
    int from = location[piece];
    if(from != CAPTURED) {
      int step, dir = firstDir[piece-16];
      while((step = steps[dir++])) {           // loop over directions
        int to = from;
        do {                                   // loop over distance
         int victim = board[to += step];       // occupant of target square
          if(victim) {                         // target square not empty
            if(victim & stm) break;            // own piece or edge guard
            if(!(piece & 8)) {                 // is Pawn
              if(!(step & 7)) break;           // straight not allowed
            }
            if((victim & 15) == 15) return 0;  // captures King; abort
            moveStack[--first] = MOVE(from, to) + mvv[victim] - ((piece & 15) << 24);
            break;                             // capture ends slide
          } else {                             // non-capture
            if(!(piece & 8)) {                 // is Pawn
              if(step & 7) break;              // diagonal not allowed
              if(from - 32 & 64                // is on 2nd or 7th rank
                   && !board[to + step])       // and has a 2nd empty square in front
                moveStack[msp++] = MOVE(from, to + step); // generate double push
            }
            moveStack[msp++] = MOVE(from, to); // generate non-capture
          }
        } while(dir >= 27);                    // sliders make next step
      }
    }
  }
  return first;
}

Again, in these tests we won't bother with rare moves such as castling, e.p. or promotion. The code above already has sections dedicated to Pawns, for enforcing their capture/noncapture divergence, and implementing the double push. Tests for e.p. or promotion could easily go in there without impacting speed much. Castlings would probably be generated separately as an afterthought, when rights exist. (Which during most of the game would not be the case, especially when an opening book is used.)

In a first test I set the MARGIN for futility pruning to 10000, effectively suppressing it completely (as the mate score is only 8000). The evaluation function currently just returns the (incrementally updated) material + PST score. (The piece values are contained in the PST.) This gave the following result for an 8-ply search on the KiwiPete position (3.2 GHz i7):

8 								
7 								
6 								
5 								
4 								
3 								
2 								
1 									
	a	b	c	d	e	f	g	h

r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1

Code: Select all

 1  -16      1603 0 e2a6 b4c3 b2c3 e6d5
 2  -16      3545 0 e2a6 b4c3 b2c3 e6d5
 3  -27     12102 0 e2a6 e6d5 g2h3 b4c3 d2c3 d5e4
 4  -27     39898 0 e2a6 e6d5 g2h3 b4c3 d2c3 d5e4
 5  -37    222427 0 e2a6 e6d5 c3d5 b6d5 e4d5 e7e5
 6  -32   1020403 0 e2a6 e6d5 c3d5 b6d5 a6b7 a8b8 b7d5 f6d5 e5f7 e7f7 e4d5 g7b2 f3f7 e8f7
 7  -32   4751946 0 e2a6 e6d5 c3d5 b6d5 a6b7 a8b8 b7d5 f6d5 e5f7 e7f7 e4d5 g7b2 f3f7 e8f7
 8  -32  24654592 0 e2a6 e6d5 c3d5 b6d5 a6b7 a8b8 b7d5 f6d5 e5f7 e7f7 e4d5 g7b2 f3f7 e8f7
t =  2.580 sec
  24654592 nodes (9.6 Mnps)
  21657300 QS (87.8%)
  21657300 evals (100.0%)
  17699622 stand-pats (81.7%)
   6954970 move gens
captures: 74.4%

Counting the number of calls to Search() (which also is responsible for QS), we get a speed of 9.6Mnps. This is higher than I had expected for such a simple move generator. Some 88% of the nodes are QS nodes, but 82% of those get a stand-pat cutoff, and never get to generating or searching moves. With the ultra-fast (essentially zero-work) evaluation, these nodes are of course nearly free; the only real work done in this program is move generation.

In the next test I switched on futility pruning, by setting a MARGIN of 30cP w.r.t. the incremental eval. This pre-empts most stand-pats, by pruning the nodes that would almost certainly achieve one. Of course in this case, where the full evaluation just is the incremental one, we could have put MARGIN=0, and predict the stand-pat cutoff with absolute accuracy. This, however, should be considered cheating; in a real engine the evaluation will have terms that cannot be obtained nearly as cheaply as the PST score, and, more importantly, cannot be obtained without actually making the move on the board. Such as mobility. With MARGIN=30 we get:

Code: Select all

 1  -16       725 0 e2a6 b4c3 b2c3 e6d5
 2  -16      1543 0 e2a6 b4c3 b2c3 e6d5
 3  -27      4431 0 e2a6 e6d5 g2h3 b4c3 d2c3 d5e4
 4  -27     12302 0 e2a6 e6d5 g2h3 b4c3 d2c3 d5e4
 5  -37     65411 0 e2a6 e6d5 c3d5 b6d5 e4d5 e7e5
 6  -32    282625 0 e2a6 e6d5 c3d5 b6d5 a6b7 a8b8 b7d5 f6d5 e5f7 e7f7 e4d5 g7b2 f3f7 e8f7
 7  -32    988964 0 e2a6 e6d5 c3d5 b6d5 a6b7 a8b8 b7d5 f6d5 e5f7 e7f7 e4d5 g7b2 f3f7 e8f7
 8  -32   7066861 0 e2a6 e6d5 c3d5 b6d5 a6b7 a8b8 b7d5 f6d5 e5f7 e7f7 e4d5 g7b2 f3f7 e8f7
t =  2.190 sec
   7066861 nodes (3.2 Mnps)
   4069697 QS (57.6%)
    748479 evals (18.4%)
    135152 stand-pats (3.3%)
   6931709 move gens
captures: 66.3%

This reduces the number of stand-pats to 3.3% of all QS nodes, by pruning the other 69% of the QS nodes that used to achieve one. Getting rid of the unnecessary make-moves and search calls gave a speed-up of 15% in terms of total time. The fraction of QS nodes has dropped to 58% now, nearly all (97%) of those having to do move generation. So hardly any 'free' nodes, now, and this of course has a huge impact on nps, which is reduced by a factor 3 to 3.2Mnps.

So we see numbers can be misleading: 3 times lower nps made us in fact 15% faster. With a 'heavy' evaluation function the drop would of course be far smaller, as the stand-pat nodes would then also have been costly. So we would never have gotten to 9.6Mnsp in the first place, but would have been limited by the evaluation. Which was done in 100% of the QS nodes. The futility pruning might in fact have given a speedup then, because it is done on the dirt-cheap PST evaluation: we see that only 18% of the QS nodes needed a full evaluation. The 3.3% that achieved a stand-pat cutoff, and apparently 15% of those that did not. The reason is that we apply the futility MARGIN both ways: to judge if we are too far below alpha for a full evaluation to stand a chance to beat it, but also whether we are too far above beta to judge if there is a chance we would not beat that.

So in the hypothetical case that Evaluate() would have taken as long as MoveGen(), the speed without futility pruning would have been 2.4Mnps (as we had about 3 times as many evaluations as move gens, so we drop by a factor 4), while with MARGIN=30 we have 10 times fewer evaluations than move gens, and the speed would be 3.2 Mnps/1.1 = 2.9 Mnps. So then futility pruning would even have increased the nps (as well as reduced the total nodes by more than a factor 3). Anyway, it seems that the case with futility pruning is a far more realistic measure of the performance that could be expected in a real engine. It is not very sensitive to doing significant evaluation effort. The nps is not so spectacularly high, but it could only be so high without futility pruning by counting nodes were no move generation was done, and thus didn't tell a whole lot about the speed of move generation.

Yet another point worth mentioning: the fraction of captures (measured in MakeMove(), when it actually applies the move to the board) is 74% without futility pruning, and drops to 66% with it. This is lower than I had expected, and likely a consequence of not using null-move pruning in search. With NMP, the preferred refutation would be a null move rather than a non-capture. But without NMP, the search will substitute a (usually pointless) non-capture for it, when no good captures are available. This is an important issue, because several of the speedup techniques I had in mind optimize the handling of captures at the expense of non-capture efficiency. So I guess my next step will be to implement NMP after all.
--------------------------------------------------------------------------------
OK, I added null-move pruning. This had the expected effect:

Code: Select all

 1  -16       725 0 e2a6 b4c3 b2c3 e6d5
 2  -16      9497 0 e2a6 b4c3 b2c3 e6d5
 3  -27     12797 0 e2a6 e6d5 g2h3 b4c3 d2c3 d5e4
 4  -27     71479 0 e2a6 e6d5 g2h3 b4c3 d2c3 d5e4
 5  -37    149317 0 e2a6 e6d5 c3d5 b6d5 e4d5 e7e5
 6  -32    399081 0 e2a6 e6d5 c3d5 b6d5 a6b7 a8b8 b7d5 f6d5 e5f7 e7f7 e4d5 g7b2 f3f7 e8f7
 7  -32    838855 0 e2a6 e6d5 c3d5 b6d5 a6b7 a8b8 b7d5 f6d5 e5f7 e7f7 e4d5 g7b2 f3f7 e8f7
 8  -32   4710223 0 e2a6 e6d5 c3d5 b6d5 a6b7 a8b8 b7d5 f6d5 e5f7 e7f7 e4d5 g7b2 f3f7 e8f7
t =  1.380 sec
   4710223 nodes (3.4 Mnps)
   4409258 QS (93.6%)
    905777 evals (20.5%)
    350015 stand-pats (7.9%)
   4134586 move gens
captures: 94.1%

The fraction of non-captures is strongly reduced; only 6% of the real moves is now a non-capture. And far less nodes are needed in total to get the same depth. We also see that QS on the average gets more difficult: there are nearly 15 times as many QS as other nodes now, meaning that each QS must have had on the average at least 15 nodes in its sub-tree. This is because NMP makes the search postpone captures when it is already ahead, preferring to null-move instead, and leaving the resolution of the position to QS.

The complete code I have now is:

Code: Select all

#include <stdio.h>
#include <time.h>
#include <ctype.h>

#define PATH 0 // ply==0 || path[0]==0x1450 && (ply==1 || path[1]==0x3122 && (ply==2 || path[2]==0x1122 && (ply==3 || path[3]==0x5443 && (ply==4))))

#define WHITE 16
#define BLACK 32
#define COLOR (WHITE|BLACK) // also used for edge guards

#define INF 8000

#define CAPTURED 255
#define MARGIN   30         // for futility pruning / lazy eval
#define STMKEY   123456789

#define KIWIPETE "r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1"
#define FIDE     "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1"

#define PST(PIECE, SQR) pstData[offs[PIECE] + SQR]
#define KEY(PIECE, SQR) zobrist[offs[PIECE] + SQR]

int pstData[7*128];
long long int zobrist[7*128];


unsigned char rawBoard[12*16];  // 0x88 board with 2-wide rim of edge guards
#define board (rawBoard + 2*17)

int stm; // side to move (WHITE or BLACK)

int location[48], offs[48], mvv[48]; // piece list

int firstDir[32] = { // offset of move list in steps[] table, per piece
  1, 1, 1, 1, 1, 1, 1, 1, 9, 9, 31, 31, 36, 36, 27, 18, // white pieces
  5, 5, 5, 5, 5, 5, 5, 5, 9, 9, 31, 31, 36, 36, 27, 18, // black pieces
};

signed char steps[] = {
  0,
  16, 15, 17, 0,                         //  1 wP
  -16, -15, -17, 0,                      //  5 bP
  31, -31, 33, -33, 18, -18, 14, -14, 0, //  9 N
  16, -16, 1, -1, 15, -15, 17, -17, 0,   // 18 K
  16, -16, 1, -1, 15, -15, 17, -17, 0,   // 27 Q   31 B
  16, -16, 1, -1, 0,                     // 36 R
};

unsigned int moveStack[10000];
int msp; // move stack pointer

int path[100], ply;
int pv[10000];
int *pvPtr = pv;
int followPV;

int nodeCnt, patCnt, genCnt, evalCnt, qsCnt, captCnt[2]; // for statistics

int pType[] = { 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 6 };
int pieceVal[] = { 0, 90, 325, 350, 500, 950, 0 };

void Init()
{
  int i, r, f;
  char *p;
  // board with rim
  for(i=0; i<12*16; i++) rawBoard[i] = COLOR;
  for(i=0; i<16; i++) {
    offs[i+WHITE] = 128*pType[i];
    offs[i+BLACK] = 128*pType[i] + 8;
    mvv[i+WHITE] = mvv[i+BLACK] = 16*pType[i] << 24;
  }
  for(r=0; r<8; r++) for(f=0; f<8; f++) {
    int s = 16*r+f;
    int d = 14 - (r-3.5)*(r-3.5) - (f-4)*(f-4);
    board[s] = 0;
    for(i=1; i<6; i++) {
      pstData[128*i+s] =
      pstData[128*i+(s^0x70)+8] = pieceVal[i] + d*(i < 4) + 9*(i == 1)*r;
    }
    pstData[128*6+s] = pstData[128*6+(s^0x70)+8] = -d;
  }
  p = (char*) (zobrist + 128);
  for(i=0; i<6*8*128; i++) *p++ = rand()*rand() >> 6;
}

char *Move2text(int move)
{
  static char buf[10];
  sprintf(buf, "%c%d%c%d", (move >> 8 & 7) + 'a', (move >> 12 & 7) + 1, (move &7) + 'a', (move >> 4 & 7) + 1);
  return buf;
}

#define MOVE(F, T) (256*(F) + (T))

int MoveGen()
{
  int i, first = msp;

  for(i=0; i<16; i++) {
    int piece = stm + i;
    int from = location[piece];
    if(from != CAPTURED) {
      int step, dir = firstDir[piece-16];
      while((step = steps[dir++])) {
        int to = from;
        do {
         int victim = board[to += step];
          if(victim) {                         // target square not empty
            if(victim & stm) break;            // own piece or edge guard
            if(!(piece & 8)) {                 // is Pawn
              if(!(step & 7)) break;           // straight
            }
            if((victim & 15) == 15) return 0;  // captures King
            moveStack[--first] = MOVE(from, to) + mvv[victim] - ((piece & 15) << 24);
            break;
          } else {                             // non-capture
            if(!(piece & 8)) {                 // is Pawn
              if(step & 7) break;              // diagonal
              if(from - 32 & 64 && !board[to + step])
                moveStack[msp++] = MOVE(from, to + step);
            }
            moveStack[msp++] = MOVE(from, to); // generate non-capture
          }
        } while(dir >= 27);
      }
    }
  }
  return first;
}

int Evaluate(int pstEval)
{
  return pstEval;
}

typedef struct {
  long long int hashKey, oldKey; // keys
  int pstEval, oldEval, curEval; // scores
  int alpha, beta;               // scores
  int from, to;                  // squares
  int piece, victim;             // pieces
  int depth;                     // depth
} UndoInfo;

int MakeMove(int move, UndoInfo *u)
{
  // decode the move
  u->to = move & 255;
  u->from = move >> 8 & 255;
  u->piece = board[u->from];
  u->victim = board[u->to];

  // update the incremental evaluation
  u->pstEval = -(u->oldEval + PST(u->piece, u->to) - PST(u->piece, u->from) + PST(u->victim, u->to));
//if(PATH) printf("     eval=%d beta=%d MARGIN=%d\n", u->pstEval, u->beta, MARGIN);
  if(u->depth <= 0 && u->pstEval > u->beta + MARGIN) return -INF-1; // futility (child will stand pat)

  // update hash key, and possibly abort on repetition
  u->hashKey =   u->oldKey  ^ KEY(u->piece, u->to) ^ KEY(u->piece, u->from) ^ KEY(u->victim, u->to);
  // if(REPEAT) return 0;

  // update board and piece list
  board[u->from] = 0;
  board[u->to]   = u->piece;
  location[u->piece]  = u->to;
  location[u->victim] = CAPTURED;

path[ply++] = move & 0xFFFF; captCnt[!u->victim]++;
  return INF+1; // kludge to indicate success
}

void UnMake(UndoInfo *u)
{
  // restore board and piece list
ply--;
  board[u->from] = u->piece;
  board[u->to]   = u->victim;
  location[u->piece]  = u->from;
  location[u->victim] = u->to;
}

int Search(UndoInfo *u) // pass all parameters in a struct
{
  UndoInfo undo;
  int first, curMove, noncapts, alpha = u->alpha;
  int *myPV = pvPtr;

  nodeCnt++;
  *pvPtr++ = 0; // empty PV

  // QS / stand pat
  if(u->depth <= 0) {
    qsCnt++;
    if(u->pstEval > alpha - MARGIN) { // don't bother with full eval if hopeless
      undo.curEval = Evaluate(u->pstEval); evalCnt++;
      if(undo.curEval > alpha) {
        if(undo.curEval >= u->beta) { patCnt++; return u->beta; }
        alpha = undo.curEval;
      }
    }
  } else if(u->pstEval > u->beta - MARGIN) { // null-move pruning
    int score;
    undo.hashKey =  u->hashKey ^ STMKEY;
    undo.pstEval = -u->pstEval;
    undo.alpha   = -u->beta;
    undo.beta    = 1 - u->beta;
    undo.depth   = (u->depth > 3 ? u->depth - 3 : 0);
    stm ^= COLOR;
    score = -Search(&undo);
    stm ^= COLOR;
    if(score >= u->beta) return u->beta;
  }

  // generate moves
  noncapts = msp += 70;          // reserve space for new move list
  first = MoveGen();
  genCnt++;
  if(!first) { alpha = INF; goto abort; }  // King capture detected
  if(followPV >= 0) {                      // first branch
    int i, m = pv[followPV++];             // get the move
    if(m) {                                // move to follow
      m |= 255<<24;                        // assign highest sort priority
      for(i=first; i<msp; i++) {           // run through move list
        if(!(m - moveStack[i] & 0xFFFF)) { // search it amongst generated moves
          moveStack[--first] = m;          // prepend to move list
          moveStack[i] = 0;                // zap PV move in list
          break;
        }
      }
    } else followPV = -1;
  }

  // set child & make-move parameters that are always the same
  undo.oldKey  =  u->hashKey ^ STMKEY;
  undo.oldEval =  u->pstEval;
  undo.depth   =  u->depth - 1;
  undo.alpha   = -u->beta;
  stm ^= COLOR;

  // move loop
  for(curMove = first; curMove < msp; curMove++) {
    int score;
    unsigned int move = moveStack[curMove];
    // move picker
    if(curMove < noncapts) { // still has to be sorted
      int i, j = curMove;
      for(i=curMove+1; i<noncapts; i++) { // extract best capture
        unsigned int m = moveStack[i];
        if(m > move) j = i, move = m;
      }
      moveStack[j] = moveStack[curMove]; moveStack[curMove] = move;
    } else if(u->depth <= 0) { // in QS no non-captures at all
      break;
    }
    if(!move) continue;        // skip zapped moves

    // recursion
    undo.beta = -alpha;
    score = MakeMove(move, &undo); // rejected moves get their score here
    if(score < -INF) break;        // move is futile, and so will be all others
    if(score > INF) { // move successfully made
      score = -Search(&undo);
      UnMake(&undo);
    }
if(PATH) printf("%2d:%d %3d. %08x %s %5d %5d\n", ply, u->depth, curMove, move, Move2text(move), score, alpha), fflush(stdout);
    // minimaxing
    if(score > alpha) {
      int *p;
      if(score >= u->beta) {
        alpha = u->beta;
        break;
      }
      alpha = score;
      p = pvPtr; pvPtr = myPV;    // pop old PV
      *pvPtr++ = move;            // push new PV, starting with this move
      while((*pvPtr++ = *p++)) {} // and append child PV
    }
  }
  stm ^= COLOR;
 abort:
  msp = noncapts - 70; // pop move list
  pvPtr = myPV;        // pop PV (but remains above stack top)
  return alpha;
}

void SearchRoot(UndoInfo *u, int maxDepth)
{
  nodeCnt = patCnt = evalCnt = genCnt = qsCnt = captCnt[0] = captCnt[1] = 0;
  u->alpha = -INF;
  u->beta  = INF;
  followPV = -1;   // nothing to follow at d=1
  for(u->depth=1; u->depth<=maxDepth; u->depth++) { // iterative deepening
    int i, score;
    score = Search(u);
    printf("%2d %4d %9d %d", u->depth, score, nodeCnt, 0);
    for(i=0; pv[i]; i++) printf(" %s", Move2text(pv[i]));
    printf("\n"), fflush(stdout);
    followPV = 0;  // follow this PV on next search
  }
}

int Setup(UndoInfo *u, char *fen)
{
  static char pieces[] = "PPPPPPPPNNBBRRQK";
  int r, f, i;
  for(i=WHITE; i<COLOR; i++) location[i] = CAPTURED;
  for(r=0; r<8; r++) for(f=0; f<8; f++) board[16*r+f] = 0;
  u->pstEval = 0; u->hashKey = 0;

  r = 7; f = 0;
  while(*fen) {
    if(*fen == '/') r--, f = 0;
    else if(*fen > '0' && *fen <= '9') f += *fen - '0'; // empties
    else if(*fen >= 'A') {                              // piece
      int color = (*fen >= 'a' ? BLACK : WHITE);
      for(i=0; i<16; i++) {
        if(location[color+i] == CAPTURED && !(*fen - pieces[i] & 31)) {
          location[color+i] = 16*r + f;
          board[16*r+f] = color + i;
          u->pstEval += PST(color + i, 16*r + f)*(color == WHITE ? 1 : -1);
          u->hashKey ^= KEY(color + i, 16*r + f);
          break;
        }
      }
      f++;
    } else break;
    fen++;
  }
  while(*fen == ' ') fen++;
  if(*fen == 'b') u->pstEval *= -1;
  return (*fen == 'b' ? BLACK : WHITE);
}

UndoInfo root;

int main()
{
  time_t t;
  Init();
  stm = Setup(&root, FIDE);
  stm = Setup(&root, KIWIPETE);
  t = clock();
  SearchRoot(&root, 8);
  t = clock() - t;
  printf("t = %6.3f sec\n", t * (1./CLOCKS_PER_SEC));
  printf("%10d nodes (%3.1f Mnps)\n%10d QS (%3.1f%%)\n", nodeCnt, nodeCnt*1e-6*CLOCKS_PER_SEC/t, qsCnt, qsCnt*100./nodeCnt);
  printf("%10d evals (%3.1f%%)\n%10d stand-pats (%3.1f%%)\n", evalCnt, evalCnt*100./qsCnt, patCnt, patCnt*100./qsCnt);
  printf("%10d move gens\ncaptures: %3.1f%%\n", genCnt, captCnt[0]*100./(captCnt[0] + captCnt[1]));
  return 0;
}

--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
