Amoeba : A Modern TSCP Type Engine

[hgm]

Some more thoughts. If we tabulate piece type indexed by piece number, to use that as an index for getting the piece properties, it should be colored types. Because pieces of the same type, but different color would need to use other PST and Zobrist tables.

Another idea would be to tabulate a bit mask indexed by piece number to indicate the 'classes' the represented piece would belong to. For instance white, black, edge guard, empty, royal, pawn. By testing that byte with the capabilities byte in the move table, the move generator could always decide in a single test when it should abort the ray scan because it hits something invalid. E.g. for a Pawn diagonal step it could reject edge guards, own pieces and empty squares. And for the sideway move of a charged Rook it could allow capture of its own royal. This could then be interpreted as castling, similar to how UCI encodes it for Chess 960.

[Mike Sherwin]

Some more thoughts. If we tabulate piece type indexed by piece number, to use that as an index for getting the piece properties, it should be colored types. Because pieces of the same type, but different color would need to use other PST and Zobrist tables.

Another idea would be to tabulate a bit mask indexed by piece number to indicate the 'classes' the represented piece would belong to. For instance white, black, edge guard, empty, royal, pawn. By testing that byte with the capabilities byte in the move table, the move generator could always decide in a single test when it should abort the ray scan because it hits something invalid. E.g. for a Pawn diagonal step it could reject edge guards, own pieces and empty squares. And for the sideway move of a charged Rook it could allow capture of its own royal. This could then be interpreted as castling, similar to how UCI encodes it for Chess 960.

If each piece has its own id number then a piece structure can hold a lot of useful information including a pointer to a special function or to the correct permissions table. Or something like that.

[hgm]

I have an interesting idea. Insttead of using an array as piece list, we put all the pieces in a doubly linked list. That is, for every occupied square of the board we also keep track of where the 'next' piece is, and where the 'previous' piece is. This way we can quickly hop from occupied square to occupied square, by using the 'next' info.

If a square gets evacuated we can remove it from the list by letting the next and previous square point to each other. When a piece gets captured we evacuate its square first, in the same way. When the moved piece then lands (now always on an empty square!), we put it back in the list, at the beginning. (As we do not really care about the order of the pieces in the list.) We do this by setting the 'next' of the newly occupied square to the formerly first square in the list, and the 'previous' of the latter to the newly occupied square, and record the latter as new list start.

We can maintain several lists; the color and type of the piece that arrived decides in what list it goes. So white and black each have their own list, and Pawns can be in separate lists from other pieces. The board can now hold the colored piece type directly, and there can be as many pieces of the same type as you want. On promotion the arriving type is different from the moving type, and would automatically go into the list it belongs. While the Pawn would be deleted from the Pawn list.

Of course on UnMake you would have to restore the old state of the list.

[Edit] Some code:

Code: Select all

typeDef struct {
unsigned char type, unused, next, prev;
} Square;

Square board[SIZE];

int GenerateMoves(int sideToMove)
{
  int fromSquare = headSquare[sideToMove]; // off-board list header
  fromSquare = board[fromSquare].next; // location of first piece in list
  while(fromSquare) { // (invalid) square number 0 indicates end of list
    pieceType = board[fromSquare].type; // type of piece there
    direction = firstDirection[pieceType]; // where to find its moves
    while((step = moveTable[direction])) {
      ... // generate moves of this piece
    }
    fromSquare = board[fromSquare].next; // location of next piece in list
  }
  return 0; // move generation completed (without capturing a King)
}

void MakeMove(Move move, UndoInfo *u)
{
  u->origin = board[move.fromSquare];
  u->destination = board[move.toSquare];
  switch(move.specialEffect) {
    ... // perform side effects, and determine (promoted) newType
  }
  // remove moved origin from list of occupied squares
  board[(u->origin).next].prev = fromSquare;
  board[(u->origin).prev].next = fromSquare;
  board[move.fromSquare] = { EMPTY, 0, 0, 0 };
  // remove capture victim from this list
  board[(u->destination).next].prev = toSquare;
  board[(u->destination).prev].next = toSquare;
  // place moved (promoted?) piece
  listHead = listTable[newType];
  oldFirstSquare = board[listHead].next;
  board[move.toSquare].next = oldFirstSquare;
  board[move.toSquare].prev = listHead;
  board[listHead].next = move.toSquare;
  board[oldFirstSquare].prev = move.toSquare;
  board[move.toSquare].type = newType;
}

The doubly linked lists of squares are organized such that they start in an off-board square (where type is EDGE_GUARD). The first real square in the list then 'points' back to this 'list head' with its 'prev' field. So that removing it from the list can be done like for any other internal square in the list.

Likewise, the last square in the list points with its 'next' field to 0, another off-board square. On removing this last square the 'prev' field of square 0 would be made to point back to the formerly forelast square in the list, but no one would ever use that prev field.

Note that empty board squares will be made to point to the 0 square too, in order to fake that these are part of a list. When a piece lands on such an empty square during a non-capture, the 'next' and 'prev' fields of the 0 square would be altered.

Each list would need its own (non-0) off-board square to act as list head. The presented code for the move generator assumes there are only two lists: one for the squares occupied by white pieces, one for those occupied by black pieces. To know which off-board squares are used as list heads we tabulate this in an array headSquare, indexed by color.

This could be refined; in principle each piece type could have its own list. This would require en extra (outer) loop in the move generator over all the lists of a given color. It would make sense to have separate lists for Pawns and Kings: we want to loop through all Pawns for the purpose of Pawn-structure evaluation, and we might want to keep track of the King location for having a dedicated in-check test.

The inconvenience of the extra loop over lists could be avoided by forging all lists for a given color into one: instead of having the last square in the list point to 0 with its 'next' field, it could point to the list head of the next piece type there is a list for. This would make the list heads point back to the last piece of the previous list, but again no one would use those 'prev' pointers. So effectively there would be a single list for each color, but the various sub-lists would be separated from each other by off-board squares containing an edge guard.

The edge guards should be skipped during move generation. But this would happen automatically when we treat EDGE_GUARD as a valid piece type, of a piece that has no moves at all. This could be indicated by having firstDirection[EDGE_GUARD] refer to an element of the moveTable that has step = 0; the while-loop over directions would then terminate immediately. Moved pieces would be inserted just behind the list head of the list they belong in, as always. Loops that want to run through all pieces in a sub-list would have to test for the end of the list by testing whether type == EDGE_GUARD. Or, presumably, they would know the square number of the edge guard at the end of this list (e.g. the sub-list for pieces might follow that for Pawns), and they could just test for that square number to see whether they are done.

Code: Select all

enum Sizes { eight = 8, sixteen = 16 };

void Init()
{
  int i, rank, file;
  // make empty 16x8 board
  for(i=0; i<256; i++) board[i] = { EDGE_GUARD, 0, 0, 0 };
  for(rank = 0; rank < eight; rank++) for(file = 0; file < eight; file++) {
    int square = rank*sixteen + file + 64; // 0x88-style numbering with offset 64
    board[square] = {EMPTY, 0, 0, 0 };
  }
  // make square lists
  // assign list heads to off-board squares 1-6
  for(type = 1; type <= NR_OF_TYPES; type++) {
    headSquare[WHITE+type] = 1;
    headSquare[BLACK+type] = 2;
  }
  headSquare[WHITE+T_PAWN] = headSquare[WHITE+T_CHARGED_PAWN] = 3;
  headSquare[BLACK+T_PAWN] = headSquare[BLACK+T_CHARGED_PAWN] = 4;
  headSquare[WHITE+T_KING] = headSquare[WHITE+T_CHARGED_KING] = 5;
  headSquare[BLACK+T_KING] = headSquare[BLACK+T_CHARGED_KING] = 6;
  // create empty lists (i.e. only the spacer squares)
  board[1].next = 3; board[3].prev = 1; // white list
  board[3].next = 5; board[5].prev = 3;
  board[5].next = 0;
  board[2].next = 4; board[4].prev = 2; // black list
  board[4].next = 6; board[6].prev = 4;
  board[6].next = 0;
}

void PlacePiece(int type, int square)
{
  int list = headSquare[type]; // head of list this piece should go in
  int oldFirst = board[list].next;
  board[square] = { type, 0, oldFirst, list };
  board[oldFirst].prev = square;
  board[list] = square;
}

The King (charged or not) will always be the only piece in the list of royals, and its location will be board[5].next (white) or board[6].next (black). Perhaps the list heads should be assigned a bit more cleverly to off-board squares, so that they would have numbers that are a bit easier to derive from the color codes. E.g. if WHITE = 16 and BLACK = 32 (the 0x30 bits of piece-type codes, leaving room for 15 piece types), we could use square 16, 17 and 18 for the white list headers, and 32, 33 and 34 for the black list headers. (Squares 0-63 are all off board.) The King locations would then be board[color+2].next.

[Mike Sherwin]

I have an interesting idea.

The most amazing thing about your interesting idea is that I understood every word of it. And the code is easy to understand as well. And if I can understand it then most others should be able too also. And the code is still small. So it looks like exactly what is needed as requested in that other thread.

[hgm]

I like this design because it is very easy to adapt to other board sizes (even with 15x15 playing area in a 17x15 board valid square numbers would still fit in a byte), and more piece types (63 types per color, if we use WHITE = 64 and BLACK =128). Furthermore, it is easy to track the location of special piece types (e.g. Immobilizers, which paralyze adjacent pieces), by putting those in their own list. The only overhead this causes is that you need to insert an extra list head in the lists.

For not-too-large boards, e.g. 12x10 playing area, you can still use a 0x88-style layout, which uses double the number of files (so 24x10). This would be good for making an efficient IsSquareAttacked test, based on an initial test based on the square-number difference for whether a piece in principle is located such that it could attack the square. (And only then test for whether the attack is blocked.)

For orthodox Chess we use 16x8 layout, and we needed 9 types per player. (6 classical types, and 3 charged).

A disadvantage is that the move encoding (without sort key) requires 3 bytes. But with a 16-byte hash entry there is enough room for that. (8 bytes signature, 3 bytes move, 1 byte depth, 2 bytes score, 1 byte bound type, 1 byte age.) So I don't think it would be worth it to pack that into 2 bytes. (Which for Chess would require 2x 6 bits for the square numbers, so that there would be 4 bits left for the specialEffect. This would be enough if there is one code for e.p. capture, implying the e.p. victim is at toSquare ^ 16.)

[hgm]

I wrote some code for the search function. It is not very special (using vanilla alpha-beta). Only the captures are sorted by the sort key included in the Move struct. (Presumably set to MVV/LVA.)

Code: Select all

Move moveStack[MOVE_STACK_SIZE];

typedef struct {
  uint64_t signature; // stores the full key, including redundant part that provided index
  Move move; // also stores the (unneeded) sort key
  int16_t score;
  unsigned char flags; // indicates bound type, hash-move validity, busy
  unsigned char depth;
} HashEntry;

int ExtractBestCapture(int start, int end)
{ // get move with highest sort key in front of move list
  if(start + 1 < end) { // if only 1 move remaining there is nothing to do
    Move move = moveStack[start];
    int best = start, bestKey = move.key; // set first as best

    for(n = start; n < end; n++) { // more moves?
      otherKey = moveStack[n].key;
      if(bestKey < otherKey) {
        bestKey = otherKey; best = n;
      }
    }

    moveStack[start] = moveStack[best]; // swap best to front
    moveStack[best] = move;
  }
}

int Search(int sideToMove,
           int originalAlpha,
           int beta,
           int incrementalEval,
           int epRights,
           int lastTo,
           int depth,
           int ply)
{
  int alpha, nrOfBestMove, legalMoves, replyDepth;
  int firstMove, noncaptures, unsorted; // move-list descriptors
  int nonCaptures = moveStackPointer 
  int iterDepth = -1;
  int haveMove = 0;
  UndoInfo undo;
  HashEntry *e = HashProbe(hashKey);

  if(e->flags & BUSY) return 0; // assume repetition, return draw score (sloppy...)
  if(e->signature == hashKey) { // hit
    if((e->score >= beta  || (e->flags & UPPER_BOUND)) &&
       (e->score <= alpha || (e->flags & LOWER_BOUND))) { // stored score is meaningful
      if(e->depth >= depth) return e->score; // if also sufficient depth, we are done
      iterDepth = e->depth; // otherwise we can build further on this result
    }
    if(e->flags & HAVE_MOVE) haveMove++; // in any case use the move, if there is one
  } else e->signature = hashKey; // requisition this entry for current position

  unsorted = noncaptures = moveStackPointer += SPACE_FOR_CAPTURES; // set up new (empty) move list
  if(GenerateMoves(sideToMove, epRights, &firstMove)) // put all pseudo-legal moves on move stack
    return INFINITY; // punished illegal preceding move by capturing King
  unsorted = firstMove; // nothing sorted yet

  e->flags |= BUSY; // mark position as being searched
  if(haveMove) moveStack[--firstMove] = e->move; // prepend hash move to move list

  while(++iterDepth <= depth) { // Internal Iterative Deepening

    alpha = originalAlpha;
    nrOfBestMove = 0; // no best move yet

    if(iterDepth == 0) { // QS pass
      int score = Evaluate(sideToMove, incrementalEval);
      if(score > alpha) {
        alpha = score;
        if(score > beta) continue; // stand-pat cutoff
      }
      if(depth == 0) moveStackPointer = nonCaptures; // discard all non-captures
      replyDepth = 0; legalMoves = 1; // assume there was a legalm move amongst noncaptures
    } else replyDepth = iterDepth - 1, legalMoves = 0;


    for(moveNr = firstMove; moveNr < moveStackPointer; moveNr++) { // loop through moves
      UndoInfo u;
      Move move;

      if(moveNr >= unsorted) {
        if(moveNr < nonCaptures) { // move is capture (or promotion)
          ExtractBestCapture(moveNr, nonCaptures); // MVV/LVA sorting
          unsorted = moveNr + 1; // declare this move sorted
        else {                   // we reached non-captures
          unsorted = lastMove;   // declare all moves sorted
          if(iterDepth == 0) {   // QS pass of deeper search
            if(!nrOfBestMove) {  // all captures worse than expected non-capture score
              while(firstMove < nonCaptures) // copy all captures to end
                moveStack[moveStackPointer++] = moveStack[firstMove++];
              alpha = originalAlpha; // undo potential effect of stand pat
            }
            iterDepth = 1; // continue with next depth
          }
        }
      }

      move = moveStack[moveNr]; // next move to search
      if(move.key == INVALID) continue; // skip duplicats

      // recursion
      MakeMove(move, &undo);
      score = -Search(sideToMove ^ COLOR,
                      -beta,
                      -alpha,
                      -newEval,
                      epFlag,
                      move.toSquare,
                      replyDepth,
                      ply + 1);
      UnMake(&undo);

      // score handling
      if(score > alpha) {
        alpha = score;
        nrOfBestMove = moveNr;
        if(score >= beta) break; // cutoff: do not search any more moves
      } else if(score != -INFINITY) legalMoves++;
    }

    if(!legalMoves) {
      if(!incheck) alpha = 0; // stalemate exception
      else alpha = -INFINITY + ply;
      break;
    }

    if(nrOfBestMove > firstMove) { // best move not yet in front
      moveStack[--firstMove] = moveStack[nrOfBestMove]; // put it there
      moveStack[nrOfBestMove].key = INVALID; // and zap the duplicat
    }
  }

  // Hash Store
  e->score = alpha;
  e->depth = depth;
  e->flags = (bestScore > alpha ? LOWER_BOUND : 0) |  // N.B. alpha < score < beta sets both bound types
             (bestScore < beta  ? UPPER_BOUND : 0);   // note this clears BUSY flag
  if(nrOfBestMove) {
    e->flags |= HAVE_MOVE;
    e->move = moveStack[nrOfBestMove];
  }

  moveStackPointer = noncaptures - SPACE_FOR_CAPTURES; // clean up move stack
  return alpha;
}

There still are a few loose ends. E.g. check detection is not yet implemented, and it is needed for distinguishing checkmate and stalemate. It could be done where this is handled, by calling Search after a null move. But that is at the end of the routine, and eventually we will want to know it at the start of the routine, e.g. to award a check extension.

Handling the mate scores is also not fully implemented. I am still in doubt whether this should be done through adapting the stored hash score w.r.t. 'ply', or by a delayed-loss bonus.

Repetition detection during search is done in a bit of a sloppy way: hash entries for positions that are in the currently searched branch are marked by setting a BUSY bit in their flags. This bit protects them from overwriting, as I don't want accedental overwriting mess with the repetition logic. But since the hash table uses always-replace for simplicity, this means that when a position accidentally maps to a BUSY entry for another position (i.e. with a different signature) it cannot be stored.

I now solve this by not searching it at all, and also score it as a draw. That is of course completely wrong; proper thing to do was to search it anyway, and suppress the hash store at the end. But the idea is that the chances for this to happen are astronomically small; only 10-20 entries in the hash table will be marked BUSY, while there are millions in total. So you must be very unlucky to accidentally hit an BUSY entry for an unrelated position. And it has been shown that an occationally completely wrong score has virtually no effect on the result of an alpha-beta search. So when hitting a BUSY entry I don't compare the full signature, but consider the fact that the index part of the key matches (or you would not have hit on this entry) sufficient evidence that we have the same position.

Another problem is that there is no testing for whether the hash move is a capture. Which could give a problem when a QS nodes gets an over-deep hit that has a noncapture hash move, but has incompatible score bounds. Then the QS node would have to be searched, but it cannot use the hash move. As there currently is no validation of hash moves at all (with a full 64-bit signature that seems unnecessary paranoia), it is not trivial to see whether a hash move is a capture. Perhaps there should be another flag stored in the hash table to indicate that.

[hgm]

Perhaps some more explanation: moves are put on a global move stack. This contains the move lists of all currently active nodes. The global variable moveStackPointer indicates the first free entry at the top of this stack.

But not all moves are added to the top of the stack. When a new node is entered, themoveStackPointer is increased by SPACE_FOR_CAPTURES to reserve an empty area behind the move list of the parent node. This basically creates to back-to-back stacks, one for the nonc-captures growing upward, the other for the captures and promotions growing downwards into the reserved area.

Initially both these stacks will be empty, and the respective stack pointers will have the same value. Which is also remembered by the variable 'noncaptures', which will not change anymore in that instance of Search, and indicates the start of the non-captures section on the stack. The local variable 'firstMove' is the stackpointer for the downward growing stack for captures and other prioritized moves, and will be pre-decremented on pushing a move. The moveStackPointer will continue to indicate the end of the move list, and is post-incremented on pushing, so that it points to just behind the last move in the move list.

There also is a variable 'unsorted', demarcating the boundary between the (initial) part of the list that is already sorted, and the unsorted moves after it. It points to the first unsorted move. After move generation this should be equal to firstMove, as the entire list is unsorted. By having the move generator already separate the captures from the non-captures, it does not take much effort to dig out the captures from the entire list during the MVV/LVA sort.

If there is a hash move, it will be pushed on the capture stack, so that it becomes first move in the list. The variable 'unsorted' will not be adapted, as we do want to search the hash move first, so that it is already in the right place. As long as we are faced with unsorted captures, the move-picker code will extract the next move from the captures section, and swap it to the entry of the upcoming move. When a non-capture is reached, 'unsorted' is put behind the list, so that for all other moves the sorting code is skipped. In a later stage we would extract killers to put those in the leading positions of the noncaptures section. And perhaps sort the remaining moves based on history.

Note that when we put the hash move in front of the list, we don't take the trouble to remove the duplicat of it that was generated by the move generator. In principle this means it will be searched twice, if the first time it did not already cause a cutoff. (Like it did in a previous search at lower depth, or it would not have become hash move.) But the second search should give you a hash cutoff immediately in the daughter. So the duplicat hash move should not be very damaging.

When there is no useful info from the hash table the node will do IID, starting to look for a hash move at low depth. The best move of each iteration will then be pushed in front of the list, do that the next iteration will start with it. In this case the duplicat will be zapped by a special code in its key field, which will cause the move to be skipped in later iterations.

[hgm]

An idea for when we would want to implement the killer heuristic. The thing that always annoys me most there is that in order to test whether a given killer is a pseudo-legal move you either have to do a quite complicated and very much rule-dependent test on it, or you have to search through a potentially long list of generated non-captures to check whether it is amongst those.

To speed up the latter it would be possible to let the move generator store the move-stack pointer every time it starts generating for a new piece. E.g. in a board-size array of integers declared as a local variable, in the element corresponding to the square that piece is on. When searching for a given killer, we could then start at the location in the move stack recorded for the from-square of that killer. Like

Code: Select all

int VetKiller(Move move, int movePointers[])
{
  int index = movePointers[move.fromSquare];
  while(move.fromSquare == moveStack[index].fromSquare) {
    if(move.toSquare == moveStack[index].toSquare && move.effect == moveStack[index].effect) return index;
    index++;
  }
  return 0; // killer not found
}

The caller can then swap the killers to the front of the non-captures section. I suppose it would have to vet both killers before doing any swapping. You have to make local copies of the killers in the global killer array anyway, as Search itself might alter the killer array before it has searched both killers. So the sort code would have to check for the case where the second killer would already be the first non-capture, so that it would get swapped with the first killer when moving that to front.

I guess one would also have to test for the while loop running out of the move stack; it might accidentally encounter moves that have the same from-square beyond the top of the stack when the killer is a move with the last piece moves were generated for. Rather than testing for index >= moveStackPointer in every iteration of the loop, it might be faster to just store an invalid move just above the top of the move stack before starting the vetting.

It would be possible to limit the number of moves you have to search through even more, by subdividing the move stack in sections for a certain move direction (i.e. that were using the same step descriptor in the moveTable). There is a tradeoff, though, between the time spend on recording all these move pointers during generation, and the time spend on searching through the thus-defined sections. My gut feeling says that this would be overdoing it. Of course there is the nasty fact that piece that have many moves are also more likely to supply a killer move, which you then have to locate in a larger section.

[Edit] A less memory-wasting solution to record the non-capture sections would be to use the so far unused byte of the Square structures in the board[] array. These are too small to hold the move-stack index for where the moves of the piece standing on that square start. But we could simply store the index relative to the start of the move list. At least if the move list is never longer than 256 bytes, which for orthodox Chess would be true.

Otherwise we could use that byte to request information for some of the squares: before move generation we could store 1 and 2 in the 'unused' byte (which otherwise contains 0) of the from-squares the killers. And then pass the address of a 4-element array movePointers[] to the move generator, which will be filled through

Code: Select all

movePointers[board[fromSquare].unused] = moveStackPointer;

every time we start generating for a new piece. This would dump the start index of the noncaptures of most pieces all in movePointers[0], but the start index of the moves of the killer pieces would go into element 1 and 2. After move generation we could then clear these three 'unused' fields again. This has the drawback that we have to invest some effort in vetting of the killers before we are sure that we would actually need those.

[hgm]

As for evaluation: what I have plans for so far are
* PST (positional bonus and piece values, updated incrementally in MakeMove)
* Pawn structure (passers, isolatedPawns, doubled Pawns, through Pawn hash)
* Material (B-pair bonus, drawishness, through material table)
* Rooks on (half-)open files

I haven't decided yet what we should do for King Safety. Definitely the Pawn shield should count for something here, and its quality on both wings can be determined as part of the Pawn-structure evaluation. Castling rights should add safety too, depending on the quality of the Pawn shield in the castling direction.

To efficiently calculate the open-file bonuses we should probably put the Rooks in a separate sub-list too. The open files themselves are determined in the Pawn-structure evaluation.

For the material evaluation it would be good to incrementally keep a materialCount variable, which packs counters for all piece types. It would probably pay to consider the light and dark Bishops as separate piece types, to facilitate detection of unlike-Bishops end-games. We don't have to count Kings; Pawn counts can run up to 8, which required 4 bits. If we take 2 bits for N, R and Q, we can accomodate up to 3 of those (and up to 1 Bihop per shade). Which leaves ample room for extra Queens from promotion, and even for some under-promotion. Note that when the counters would overflow, this would thoroughly mess up the material evaluation. But this is just a minor evaluation term, so who cares?

The layout of the materialCount in an int32_t would then be 00000000.ppppPPPP.qqQQrrRR.nnNNbbBB. For the Bishop counters value 3 would mean a Bishop pair; 1 and 2 would mean a single Bishop (on light or dark squares), and 0 of course no Bishops. So 24 bits are used, which would mean 16M elements in a full table (many of those for impossible material compositions). It would be possible to construct a much more compact material counter, but then it would be very difficult to derive the individual piece counts from it. So I prefer to use a hash table instead, which only has to hold material compositions that actually occur in the tree. The key for hashing this could simply be the materialCounts multiplied by some 'magic' constant, the high bits used as table index, the low bits (or the entire counts word) as signature.

I try to keep in mind how generally useful things are, as opposed to exploiting special properties that only orthodox Chess has. And this way of doing it seems pretty flexible. Other variants could have many more piece types, making implementation of a complete table a hopeless endeavor. There might be so many types that the counters can no longer be packed into a 32-bit int, but one could easily expand that to 64-bit. And it might not be needed to count all individual types; it might be sufficient to put several types with similar properties in one 'class', and only count the total number of pieces in that class. For orthodox Chess one might be inclined to do that for the minors. But Bishop and Knight are sufficiently different to make that a bad idea: we really want to have different drawishness and pair-bonus evaluations for a pair of Knights and a pair of Bishops. But if a variant would have, say, three color-bound types that can all force checkmate as a pair, there would be no need to distinguish those, and you could use two 2-bit counters for each square shade.

So perhaps it is better to not consider these counters for Q, R, B and N per se, but more as counters for pieces in the classes 'majors that can beat a minor in a Pawnless end-game', 'majors that cannot', 'color-bounds' (which of course are always minors) and 'minors that cannot checkmate in pairs'. And then reserve some extra bits for these counters, e.g. in a layout ppppPPPP.qqQQrrrR.RRnnnNNN.bbb'b'BBB'B'. Which would faithfully represent up to 15 Pawns, 3 super-pieces, 7 other majors, 2x3 color bounds and 7 other minors.

The EvaluateMaterial code could then test for balance of light and dark color-bounds for awarding a pair bonus and unlike-Bishop type drawishness, complete lack of power on one shade, other lack of mating power, insufficient pawn-less material to subdue the opponent. And it would not be very costly to defer the actual decision of whether a pair of minors has mating potential (if you cannot see that from their color binding) to the actual evaluation, and let the material table only flag the fact that you have to do this. This matter only becomes relevant when these two minors are your only pieces, and it won't take much effort to get the type of those by looking in the piece list: they would be the only two pieces in the non-pawn-non-royal section. You could then have a table matingPotential[type1][type2] that tells you whether the two pieces can force checkmate.

Code: Select all

MaterialEntry *m;

if(eval > 0) { // white is ahead
  if(m->flags & WHITE_MINOR_PAIR) {
    int type1, type2;
    int square = listHead[WHITE+T_KNIGHT];
    square = board[square].next;
    type1 = board[square].type & TYPE_MASK; // strip off color bits
    square = board[square].next;
    type2 = board[square].type & TYPE_MASK;
    factor = matingPotential[type1][type2];
  } else factor = m->whiteFactor;
  eval = eval*factor/16;
}

[Edit] A convenient way to determine the total number of pieces from the individual counts in the materialCount would be to store the counts in the format ppppPPPP.qqQQrrrR.RRnnnNNN.bbBBb'b'B'B', so that the white non-Pawn counts can be extracted by ANDing with 0x31C733, and for the black counts with 0xCE38CC. Each count is then in its own field of 4 contiguous bits, so that the sum can be obtained as (materialCount & 0x31C733)*0x11104100 >> 28 and (materialCount & 0xCE38CC)*0x4441040 >> 28. As long as these totals are not larger than 15. (Which for orthodox Chess they never are, as Kings are not counted.)

This total is relevant for one of the two drawishness cases, where the player that is ahead has 0 or 1 Pawns, and up to 2 other non-royal pieces. Without Pawns non-winnable piece combinations should be recognized (like Rook vs minor) and their score severely discounted (like divided by 8), while winnable combinations should still be discounted by a factor 2. (Except against a bare King, which is always easy.) With 1 Pawn it would depend whether a winnable combination results if the weak side sacrifices his lowest-valued piece for the Pawn.

The other case is unlike color-bounds as only pieces. These should be discounted by a factor 2 if the difference in Pawns is not overwhelming (i.e. > 2), even when there are many Pawns. This can be triggered by testing whether (materialCount & ~0xFF) == 0 (no non-color-bounds), and then testing whether ANDing with 0xC3 or 0x3C gives 0 and ANDing with 0x33 and 0xCC give both non-zero.

[hgm]

As a later add-on, the material table could also be used to flag that a special evaluation routine has to be used, dedicated to that particular material composition. Such as for the KPK and KBPK end-game. These routines could then detect known draws in those end-games based on the actual position, and use a large factor to discount the score in those cases. We don't want the score to be set to a hard zero for a theoretical draw, or it would, for instance, not caring at all about losing the Pawn in KPK, making it impossible to benefit from sub-optimal defense by a fallible opponent.

It would also be useful to have a detection of 'unstoppable passers' in the evaluation, applied when a player has only King and Pawns. (A flag in the material-hash entries could indicate for which players this is the case.) To speed that up the pawn-hash entry should contain some additional info about passers, such as the promotion square, and how many moves they would need to reach it. The evaluation can the compare that with the distance of the King from the promotion square.

I implemented a partial recognizer for KPK in KingSlayer, and that already gave an enormous speedup in either finding the promotion, or concluding the position was a draw in positions that were not recognized. The reason that such searches take very long in an engine that does not have any knowledge is that drawn positions can keep looking promising for a long time, and will only resolve when the Pawn gets to 6th rank. There the strong side gets the choice of advancing the Pawn for a stalemate, give up the Pawn or eventually run into a repetition after having stalled many moves to avoid that.

Positions that are won because of an unstoppable passer, or drawn because the defending King reaches the passer first and gobbles it up resolve much faster. But since these are easy to detect by comparing a few distances it still helps to recognize these too. The 'tedious draws' are properly handled when positions with the defending King 1 or 2 steps in front of the Pawn, or a forward Knight jump in front of it while the attacking King is not next to the Pawn on the other side as a draw, and would return a discounted score without further search in that case. For Rook Pawns any position where the defending King is in front of the Pawn in the same file or that next to it can be recognized as a draw.

BTW, because we are already working with different Pawn types that morph into each other depending on where they stand, it would be a possibility to define Pawns on the board edge as a different piece type, with their own counters. I am not sure this would have sufficient advantage to justify the added conceptual complexity, though. (One advantage woul be that the KBPK recognizer could only be invoked if we already know there is a Rook Pawn. But it still would have to check the shade of the Bishop and whether the defending King can actually get in the path of the Pawn, so you cannot do without a dedicated recognizer.)