Best was to Recognize Know Endgames?

[Steve Maughan]

I'd like to add some basic endgame knowledge to Maverick. At first I'd like to add basic stuff - N + B + K vs. K etc. In the medium term I'd like to add knowledge which is a little more complex e.g. Philidor's endgame with P + R + K vs. R + K.

My question is - what's the best (fastest) way to recognize these positions?

The most obvious way is to do a series of "if then" statement:

Code: Select all

If &#40;WHITE_PAWNS <= 1 && BLACK_PAWNS <= 1&#41;&#123;
...
&#125;

Is there a better way?

Steve

[sje]

Symbolic, and many other programs I suspect, keeps a hash of the material distribution. The hash changes whenever a man is added or deleted. The Zobrist code array declaration looks like:

Code: Select all

static Hash MaterialHash[ManRCLen][PieceMultLen];

Where ManRCLen is 12 (2 * 6) and PieceMultLen is 10 (2 + 8).

The material hash for an empty board is zero. When a piece is added or deleted, the method called is:

Code: Select all

  void FoldMaterialHash(const Man man, const ui lowercount)
  {
    *this ^= MaterialHash[man][lowercount];
  }

If in the game, the first capture is White taking a black pawn, the call would be:

Code: Select all

mtrlhash.FoldMaterialHash(BlackPawn, 7);  // Count is AFTER the capture

When retracting that move, the exact same call is made. But the comment would be different ("Count BEFORE the uncapture").

When the program is initialized, a separate array of constant material hashes is created: one entry for each endgame of interest for each color. This table is stored in numeric order and is probed by a binary search. An alternative is to use a transposition table instead of array.

[hgm]

In Spartacus I keep an incrementally updated material index, which is a unique code for the material on the board (e.g. nrWhiteQueens + 2*nrWhiteKnights + 6*nrWhiteRooks + 12*nrWhiteLightBishops + 24*nrWhiteBlackBishops + 48*...). This is used as index in a (huge) table (the 'material table').

Normally the table contains a score, to be added to the evaluation (from white POV). This way you can award / penalize certain material combinations (for instance the Bishop pair, or the presence of Rooks when you have Q vs 3 minors).

I only use material corrections in the range {-100 cP, 100 cP}, so the table contains bytes (to limit its size). In fact steps of 1 cP is needlessly fine-grained, so the two lowest-order bits double as indicators for whether null-move for either side is allowed. But the values that would correspond to eval corrections over 100 cP are used to flag material combinations that need special handling. To cheaply test for those, I encode the material table in 'excess-100 encoding', i.e. 0 correspnds to -100 cP and 200 corresponds to +100 cP. I then narmally add eval += material[materialIndex] - 100, but first test if materialMaterialIndes] > 200.

If the latter is the case I execute a special code section, that distingushes two different cases: one sub-range (say 201-224) flags cases where the evaluation has to be multiplied with 0.5, 0.25 or 0.125 in various combinations (white only, black only, both), because that leading side is lacking in mating potential. The remaining codes are used as an index in a table of pointers to special evaluation routines (e.g. for KPK or KBNK). The latter could do anything, and are typically used when the eval correction should not only depend on material. but on the actual location of the pieces.

[Gerd Isenberg]

I'd like to add some basic endgame knowledge to Maverick. At first I'd like to add basic stuff - N + B + K vs. K etc. In the medium term I'd like to add knowledge which is a little more complex e.g. Philidor's endgame with P + R + K vs. R + K.

My question is - what's the best (fastest) way to recognize these positions?

The most obvious way is to do a series of "if then" statement:

Code: Select all

If &#40;WHITE_PAWNS <= 1 && BLACK_PAWNS <= 1&#41;&#123;
...
&#125;

Is there a better way?

Steve

Ernst A. Heinz (1998) Efficient Interior-Node Recognition. ICCA Journal, Vol. 21, No. 3
http://people.csail.mit.edu/heinz/dt/node33.html
http://people.csail.mit.edu/heinz/dt/node41.html
http://people.csail.mit.edu/heinz/dt/node42.html

[hgm]

I can add that in Pair-o-Max (a Fairy-Max derivative paying attention to mating potential, where efficiency is a hopeless cause anyway) I do use the if-then method. Fairy-Max counts the number of pieces of each (colored) type anyway, for the purpose of determining unusual game-end conditions (e.g. with multiple royal pieces, extinction chess). And that info also comes in useful for awarding pair bonuses. So I can test on those numbers.

The burdon this puts on the normal evaluation can be kept very small, by organizing the conditionals as a tree. E.g. I first test if the number of Pawns is > 1, because no end-game I want to correct the material score of has 2 or more Pawns for the leading side. So that automatically disables the entire code block during the middle game with a simple test. Only if I detect Pawn scarcity, it starts to really calculate.

[lucasart]

I'd like to add some basic endgame knowledge to Maverick. At first I'd like to add basic stuff - N + B + K vs. K etc. In the medium term I'd like to add knowledge which is a little more complex e.g. Philidor's endgame with P + R + K vs. R + K.

My question is - what's the best (fastest) way to recognize these positions?

The most obvious way is to do a series of "if then" statement:

Code: Select all

If &#40;WHITE_PAWNS <= 1 && BLACK_PAWNS <= 1&#41;&#123;
...
&#125;

Is there a better way?

Steve

Yes, use material hash keys. You can construct them using a zobrist approach, but I prefer a more comprehensive method, that allows me to understand the values of the keys directly:

Code: Select all

uint64_t mat_key;

bits 0..3: number of white pawns
bits 4..7: number of black pawns
bits 8..11: number of white knights
bits 12..15: number of black knights
(...)
bits 32..35: number of white queens
bits 36..39: number of black queens

Currently I only have a couple of endgame functions (KPK and KBPK), but if their number increases and the cost of branching becomes a problem, I will use an array of pairs: (mat_key, function_pointer) and branching will become a O(1) operation.

Stockfish does something similar but with a lot of C++ obfuscation and using std::map. I really doubt that using maps is faster than using a sorted array with a binary search, but anyway, that's what they do.

[velmarin]

Your code with Bitboards
and good instructions popcount should not suffer with the method you choose.

Would start by defining the piezes, you will write many times:
Example:
# define BB_PawnW (board-> piecelist [WHITEPAWN])

After all pieces:
# define BB_Occupied (BB_PawnW | BB_PawnB | ect, ect, BB_KingB)

And only a couple of "if" has the required position.
if (popcount (BB_Occupied) == 4) {
if ((popcount (BB_NKnigthW) == 1)& & (popcount (BB_BishopW) == 1) {
}
}

[mcostalba]

Stockfish does something similar but with a lot of C++ obfuscation and using std::map. I really doubt that using maps is faster than using a sorted array with a binary search, but anyway, that's what they do.

Actually std::map do is a sorted container with a binary search. The only difference with your suggestion is that it is already written, debugged, correctly implemented and ready to use.

Regarding obfuscation, yes , I indulged in some C++ exotic here, my bad, but temptation was too strong. Actually I _usually_ try to just use the C++ that is needed along the code, not more...but in this case I made a small exception and pushed the pedal...anyhow I challenge someone to rewrite it in a shorter form, keeping the same functionality and flexibility.

[lucasart]

Currently I only have a couple of endgame functions (KPK and KBPK), but if their number increases and the cost of branching becomes a problem, I will use an array of pairs: (mat_key, function_pointer) and branching will become a O(1) operation.

Oops. I meant O(log(N)) obviously, where N is the number of endgame functions.

[lucasart]

Stockfish does something similar but with a lot of C++ obfuscation and using std::map. I really doubt that using maps is faster than using a sorted array with a binary search, but anyway, that's what they do.

Actually std::map do is a sorted container with a binary search. The only difference with your suggestion is that it is already written, debugged, correctly implemented and ready to use.

Regarding obfuscation, yes , I indulged in some C++ exotic here, my bad, but temptation was too strong. Actually I _usually_ try to just use the C++ that is needed along the code, not more...but in this case I made a small exception and pushed the pedal...anyhow I challenge someone to rewrite it in a shorter form, keeping the same functionality and flexibility.

Wouldn't it be possible to use a sorted vector instead of a map ? Simply a vector of pairs (mat_key, function_pointer), where the sorting predicate is along the material key. In <algorithm> there is a binary search for a sorted vector, so it would work more or less the same (and you have to do sorted inserts when you add your functions to the vector in the initialisation phase). It may be a little less elegant (or obfuscated depending on one's taste) than using a map, but it should be more efficient since a vector is implemented as a compact and cache friendly array, while a map is a horribly cache unfriendly RB-tree...

There's also the added complexity that SF uses two kinds of endgame functions: those returning a score and those returning a factor.

Well, I'm just giving ideas here, but I don't think I have the C++ skills to rewrite this kind of code (or even to understand it more than superficially). One of the drawback of this kind of code, is that only you and a handful of C++ gurus are capable of modifying it in non trivial ways, which can somehow hinder developpement. But I understand the temptation to write some show-off code from time to time