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 (WHITE_PAWNS <= 1 && BLACK_PAWNS <= 1){
...
}
Steve
Moderators: hgm, Rebel, chrisw
Code: Select all
If (WHITE_PAWNS <= 1 && BLACK_PAWNS <= 1){
...
}
Code: Select all
static Hash MaterialHash[ManRCLen][PieceMultLen];
Code: Select all
void FoldMaterialHash(const Man man, const ui lowercount)
{
*this ^= MaterialHash[man][lowercount];
}
Code: Select all
mtrlhash.FoldMaterialHash(BlackPawn, 7); // Count is AFTER the capture
Ernst A. Heinz (1998) Efficient Interior-Node Recognition. ICCA Journal, Vol. 21, No. 3Steve Maughan wrote: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:Is there a better way?Code: Select all
If (WHITE_PAWNS <= 1 && BLACK_PAWNS <= 1){ ... }
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:Steve Maughan wrote: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:Is there a better way?Code: Select all
If (WHITE_PAWNS <= 1 && BLACK_PAWNS <= 1){ ... }
Steve
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
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.lucasart wrote: 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.
Oops. I meant O(log(N)) obviously, where N is the number of endgame functions.lucasart wrote: 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.
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...mcostalba wrote: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.lucasart wrote: 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.
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.