Best was to Recognize Know Endgames?
Moderators: hgm, Rebel, chrisw
-
- Posts: 27811
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Best was to Recognize Know Endgames?
Note that the Spartacus approach is truly O(1). No search of any kind, just straightforward accesses to hash tables. To keep the size of the material table manageable, however, I have to use a more compact material index than just setting apart groups of bits for the counting. The drawback of that is that I cannot handle over-complete material combinations.
-
- Posts: 4675
- Joined: Mon Mar 13, 2006 7:43 pm
A list of endgame classes
Symbolic can recognize all of the 146 different 2-5 man endgame classes. A particular endgame class is identified by a binary search of a table of 292 (= 146 * 2) material distribution signatures (not hashes). The table search looks for both a direct and color reversed match at the same time and is very fast. This code is mostly used for the tablebase probing. (The Zobrist material hash is used for other stuff.)
With the thought that it may be useful to those writing their own chess program, here is Symbolic's lexicographically ordered endgame class name array:
With the thought that it may be useful to those writing their own chess program, here is Symbolic's lexicographically ordered endgame class name array:
Code: Select all
const std::string Material::EndgameNameVec[EgkLen] =
{
"KBBBK",
"KBBK",
"KBBKB",
"KBBKN",
"KBBKP",
"KBBKQ",
"KBBKR",
"KBBNK",
"KBBPK",
"KBK",
"KBKB",
"KBKN",
"KBKP",
"KBNK",
"KBNKB",
"KBNKN",
"KBNKP",
"KBNKQ",
"KBNKR",
"KBNNK",
"KBNPK",
"KBPK",
"KBPKB",
"KBPKN",
"KBPKP",
"KBPKQ",
"KBPKR",
"KBPPK",
"KK",
"KNK",
"KNKN",
"KNKP",
"KNNK",
"KNNKB",
"KNNKN",
"KNNKP",
"KNNKQ",
"KNNKR",
"KNNNK",
"KNNPK",
"KNPK",
"KNPKB",
"KNPKN",
"KNPKP",
"KNPKQ",
"KNPKR",
"KNPPK",
"KPK",
"KPKP",
"KPPK",
"KPPKB",
"KPPKN",
"KPPKP",
"KPPKQ",
"KPPKR",
"KPPPK",
"KQBBK",
"KQBK",
"KQBKB",
"KQBKN",
"KQBKP",
"KQBKQ",
"KQBKR",
"KQBNK",
"KQBPK",
"KQK",
"KQKB",
"KQKN",
"KQKP",
"KQKQ",
"KQKR",
"KQNK",
"KQNKB",
"KQNKN",
"KQNKP",
"KQNKQ",
"KQNKR",
"KQNNK",
"KQNPK",
"KQPK",
"KQPKB",
"KQPKN",
"KQPKP",
"KQPKQ",
"KQPKR",
"KQPPK",
"KQQBK",
"KQQK",
"KQQKB",
"KQQKN",
"KQQKP",
"KQQKQ",
"KQQKR",
"KQQNK",
"KQQPK",
"KQQQK",
"KQQRK",
"KQRBK",
"KQRK",
"KQRKB",
"KQRKN",
"KQRKP",
"KQRKQ",
"KQRKR",
"KQRNK",
"KQRPK",
"KQRRK",
"KRBBK",
"KRBK",
"KRBKB",
"KRBKN",
"KRBKP",
"KRBKQ",
"KRBKR",
"KRBNK",
"KRBPK",
"KRK",
"KRKB",
"KRKN",
"KRKP",
"KRKR",
"KRNK",
"KRNKB",
"KRNKN",
"KRNKP",
"KRNKQ",
"KRNKR",
"KRNNK",
"KRNPK",
"KRPK",
"KRPKB",
"KRPKN",
"KRPKP",
"KRPKQ",
"KRPKR",
"KRPPK",
"KRRBK",
"KRRK",
"KRRKB",
"KRRKN",
"KRRKP",
"KRRKQ",
"KRRKR",
"KRRNK",
"KRRPK",
"KRRRK"
};
-
- Posts: 5106
- Joined: Tue Apr 29, 2008 4:27 pm
Re: Best was to Recognize Know Endgames?
I incrementally update a material only hash table and just use this table to score them. I have done this for a very long time but only recently have I added the general scoring for all positions - in other words the material only score for any position is also computed and hashed just like pawn structure.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
The endgame table has a few fields because you don't always score each position the same way. You might for example only have a score and not want to use the normal evaluation, or you might want to compute a score with a specialized function just for that ending. We can also call the evaluation and modify what is returned in some cases - usually for endings we know are very drawish.
But we can add as many endings as we with without concern for the overhead.
Capital punishment would be more effective as a preventive measure if it were administered prior to the crime.
-
- Posts: 5566
- Joined: Tue Feb 28, 2012 11:56 pm
Re: Best was to Recognize Know Endgames?
This is what I do as well (except for the order). I use the 16 highest bits to store random values which I use as an index into the material hash table.lucasart wrote: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
So:
Code: Select all
uint64 mat_piece_key[] = {
0ULL,
0x5ced000000000001ULL,
0xe173000000000010ULL,
0xd64d000000000100ULL,
0xab88000000001000ULL,
0x680b000000010000ULL,
0x0000000000000000ULL,
0ULL,
0ULL,
0xf209000000100000ULL,
0xbb14000001000000ULL,
0x58df000010000000ULL,
0xa15f000100000000ULL,
0x7c94001000000000ULL,
0x0000000000000000ULL,
0ULL
};
-
- Posts: 3232
- Joined: Mon May 31, 2010 1:29 pm
- Full name: lucasart
Re: Best was to Recognize Know Endgames?
That's a very nice trick. It allows O(1) branching, and in a very elegant way!syzygy wrote:This is what I do as well (except for the order). I use the 16 highest bits to store random values which I use as an index into the material hash table.lucasart wrote: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
Thanks for the tip. I will definitely use your method (16 highest bits for index) when I decide to implement a table lookup (for now only KPK and KBPK so the basic "if method" is fine).
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.
-
- Posts: 4675
- Joined: Mon Mar 13, 2006 7:43 pm
And the table probe code
The endgame descriptor probe code is triggered mostly (maybe only) for tablebase access. No more than nine (= log2 N) probes per call are needed, and the time used is totally swamped by the ensuing system call to access a tablebase file.
Code: Select all
bool Position::IdentifyEndgame(Egk& egk, bool& isreversed) const
{
egk = EgkNil;
isreversed = false;
if (census.GetTotalCount() <= EgkMaxManLen)
{
const ui64 whitedist = census.GetDistribution(ColorWhite);
const ui64 blackdist = census.GetDistribution(ColorBlack);
const ui64 key = (blackdist << 24) | whitedist;
si lo = 0, hi = EgkPairLen - 1;
while (IsEgkNil(egk) && (lo <= hi))
{
const si mi = (lo + hi) / 2;
const ui64 tablekey = Material::EndgameDescriptorVec[mi].key;
if (key == tablekey)
{
egk = Material::EndgameDescriptorVec[mi].egk;
isreversed = Material::EndgameDescriptorVec[mi].isreversed;
}
else
{
if (key < tablekey)
hi = mi - 1;
else
lo = mi + 1;
};
};
};
return IsEgkNotNil(egk);
}
-
- Posts: 3232
- Joined: Mon May 31, 2010 1:29 pm
- Full name: lucasart
Re: Best was to Recognize Know Endgames?
Actually, there is always the back side of the coin in O(1) branching: memory wastage. Your method involves an array of 2^16 pointers of endgame functions (most are null and the rest point to the few endgame functions). That's 512 KB of RAM on x86-64 plateforms...lucasart wrote:That's a very nice trick. It allows O(1) branching, and in a very elegant way!syzygy wrote:This is what I do as well (except for the order). I use the 16 highest bits to store random values which I use as an index into the material hash table.lucasart wrote: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
Thanks for the tip. I will definitely use your method (16 highest bits for index) when I decide to implement a table lookup (for now only KPK and KBPK so the basic "if method" is fine).
Also, since you use a 16 bit material zobrist, why do you need the 40 lower bits ?
In practice I think it's probably best to stick to the simple O(log(N)) method involving dichotomic search by material key. In practice it's only a few iterations, completely negligible...
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.
-
- Posts: 1221
- Joined: Wed Mar 08, 2006 8:28 pm
- Location: Florida, USA
Re: Best was to Recognize Know Endgames?
Thanks everyone - some great input.
Here's what I'm thinking of trying first. I'm going to try something like Steven Edwards' suggestion. I'll hash the material and then use the "n" smallest bits to lookup the hash value in a table and compare the key. This table will be small. If I have 20 endgames I'd like to recognize (40 valid possible keys), I imagine I'll be able to get it in a 64 entry table. The table entry will contain a pointer to the function which will evaluate the endgame.
Thanks again - some good discussion!
Steve
Here's what I'm thinking of trying first. I'm going to try something like Steven Edwards' suggestion. I'll hash the material and then use the "n" smallest bits to lookup the hash value in a table and compare the key. This table will be small. If I have 20 endgames I'd like to recognize (40 valid possible keys), I imagine I'll be able to get it in a 64 entry table. The table entry will contain a pointer to the function which will evaluate the endgame.
Thanks again - some good discussion!
Steve
http://www.chessprogramming.net - Maverick Chess Engine
-
- Posts: 5566
- Joined: Tue Feb 28, 2012 11:56 pm
Re: Best was to Recognize Know Endgames?
You can use the entries in the material hash table also for storing the value of material (applying formulae as complicated as you like, no need to restrict to a simple sum of piece values), weights for king safety, weights for middle game / end game, parameters for adjusting reductions / extensions (in particular null move comes to mind), etc. So it doesn't have to be restricted to end games.lucasart wrote:Thanks for the tip. I will definitely use your method (16 highest bits for index) when I decide to implement a table lookup (for now only KPK and KBPK so the basic "if method" is fine).
Using all 16 bits might be overkill. I think Stockfish uses material hash tables with 8192 entries or so. But that just means 16 bits is enough.
-
- Posts: 5566
- Joined: Tue Feb 28, 2012 11:56 pm
Re: Best was to Recognize Know Endgames?
See my previous reply. Also note that if you only use it for a few endgame functions and only probe the table if there is little material on the board, most of the table will never be accessed, will never see you cache, and will do no harm whatsoever.lucasart wrote:Actually, there is always the back side of the coin in O(1) branching: memory wastage. Your method involves an array of 2^16 pointers of endgame functions (most are null and the rest point to the few endgame functions). That's 512 KB of RAM on x86-64 plateforms...
Btw, there is no real need to store an 8-byte function pointer. You can store a byte that you use as an index into an array of function pointers if non-zero. Or just do a switch() on the value of the byte if non-zero. The important thing is to reduce overhead as much as possible for the great majority of the positions for which you do not have special endgame knowledge.
It is not Zobrist, because it is a sum and not a xor.Also, since you use a 16 bit material zobrist, why do you need the 40 lower bits ?
You need to detect collisions. The lower 40 bits unique identify the material, so give a perfect way to check for collisions. It may also be useful if somewhere in your engine you want to quickly test for a particular combination of material without having to store corresponding flags in the material hash table. It's quite flexible.
And again, 8192 entries might well be enough to have a 99.9% hit rate. I never bothered to test this. But I can already tell that there is not much if anything to lose by having a table that is too big, since the parts that are not accessed will simply not enter your cache.
In any event, my main point is that, as far as I can tell, my approach has clear advantages and no disadvantages over Steven's and Stockfish's way of calculating a material signature by xor'ing numbers. I just add numbers taken from a 1-dimensional array indexed by piece type. If you use xor, you have to take numbers from a 2-dimensional array indexed by piece type and by an index running from 1 to the number of pieces of a particular type and color. In addition, my hashing scheme is perfect, i.e. there are no collisions.