How to implement KPK ?
Moderators: hgm, Rebel, chrisw
-
- Posts: 27842
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: How to implement KPK ?
From probing a few hundred randomly generated positions I could not find an error. So it seems the code is OK.
-
- Posts: 588
- Joined: Thu Mar 09, 2006 4:47 pm
- Location: Singapore
Re: How to implement KPK ?
Muller's public domain kpk bitbase generator should be working. I probe the bitbase for a few kpk positions and they are in agreement with match results when the positions are played by stockfish vs komodo.hgm wrote:I see KPK quite often.
Anyway, to further the public-domain cause, the following code actually runs, and prints some numbers that seem to make sense (like the number of stalemates, which matches what I calculated by hand). I even put in the initial double-push, which is important for rule-of-squares situations.
Btw, this is the dumb algorithm, which does not use any unmoves. It just attempts regular moving from all not-yet-decided positions, to look for a move to a won position for white, and to a non-lost position for black.
Printing the stats of the positions with the Pawn on rank 2-7 afterwards gives:Code: Select all
/* Public-domain KPK bitbase code by H.G. Muller */ #define WTM 0 #define BTM 1 char dtc[2][64][64][64]; // 512 KB char bitbase[2*64*64*3]; char steps[] = {1, -1, 16, -16, 15, -15, 17, -17}; // 0x88 King steps void Init () { /* 3 = bK captured, 2 = can capture bK, 1 = won, 0 = undecided, -1 = broken or wK captured */ int wk, bk, p; for(wk=0; wk<64; wk++) for(p=0; p<64; p++) for(bk=0; bk<64; bk++) { if(bk == wk) dtc[BTM][wk][p][bk] = 3, dtc[WTM][wk][p][bk] = -1; else if(wk == p) dtc[BTM][wk][p][bk] = dtc[WTM][wk][p][bk] = -1; else if(bk == p) dtc[BTM][wk][p][bk] = -3; else // with WTM black just captured P if(p >= 56) dtc[WTM][wk][p][bk] = 1; // promoted and on move = win } } void Pass (int stm, int first, int def, int esc) { int wk, bk, p, d; for(wk=0; wk<64; wk++) for(p=0; p<64; p++) for(bk=0; bk<64; bk++) { int k = stm == WTM ? wk : bk; int O88 = (k & 070) + k; // 0x88 square number of King if(dtc[stm][wk][p][bk]) continue; // already decided dtc[stm][wk][p][bk] = def; // assume lost if btm, undecided if wtm if(bk != p && stm == WTM) { // pawn not captured, so can move if(p+8 != bk && (dtc[BTM][wk][p+8 ][bk] > first || p < 16 && p+16 != bk && dtc[BTM][wk][p+16][bk] > first)) { dtc[WTM][wk][p][bk] = esc; continue; } if(p+7 == bk && (p & 7) != 0) { dtc[WTM][wk][p][bk] = 2; continue; } if(p+9 == bk && (p & 7) != 7) { dtc[WTM][wk][p][bk] = 2; continue; } } for(d=0; d<8; d++) { int to = O88 + steps[d]; if(to & 0x88) continue; // off board to -= to>>1 & 070; if(stm == WTM ? dtc[BTM][to][p][bk] > first : dtc[WTM][wk][p][to] <= first) { dtc[stm][wk][p][bk] = esc; break; } } } } void Pack () { int wk, bk, p, i; for(wk=0; wk<64; wk++) for(p=8; p<56; p+=2) for(bk=0; bk<64; bk++) { // calculate probe address and bit int index = (bk >> 3) + 8*wk + 8*64*(p-8>>1); bitbase[2*index] |= (dtc[WTM][wk][p][bk] > 0) << (bk & 7); bitbase[2*index+1] |= (dtc[BTM][wk][p][bk] > 0) << (bk & 7); } } void Build () { int i; Init(); Pass(WTM, 2, 0, 2); Pass(BTM, 1, -2, 0); // calculate King captures and stalemates for(i=0; i<25; i++) // won't take more than 25 moves Pass(WTM, 0, 0, 1), Pass(BTM, 0, 1, 0); Pack(); }
where + means won to white, = means draw, - illegal by white's fault or black stalemated. (White stalemates are not separately identified, they count with the other draws.)Code: Select all
white to move: 124960+, 41044=, 6096-, 0 stalemate, 24508 K-capture black to move: 97604+, 89866=, 6066-, 18 stalemate, 0 K-capture
The various programs I have all could play kpk endings perfectly. Even the weakest, simplex, which is about at the level of my engine, could do so. I noticed that when these engines analyse a typical kpk position, the PV remains almost unchanged (the first four moves) from a very early depth of 9 or 10 till 30 or more plies. But my implementation of the kpk evaluation is still not working. In analysis mode, the PV keeps changing.
My kpk evaluation returns 0/1 when it is a draw. If a win, it will return 5 x pawn and some simple evaluation terms. Maybe, someone who have implemented kpk sucessfully may check my codes to see if it should work. If it should work, then it means there are bugs in my search that somehow escaped detection.
The code for my kpk evaluator has the probe codes for Muller's bitbase:
Code: Select all
int evalkpk(const int side) {
const int pCol = !bits[0][Pawn];
const int pOnMove = (pCol == side);
const int pK = king[pCol], loneK = king[pCol ^ 1], p = firstone(bits[pCol][Pawn]);
int probeWk, probeBk, probeWp;
int win, index, stm;
if (kMap[king[side]] & bits[side ^ 1][Pawn] & ~kMap[king[side ^ 1]]) {
/* insurance - safe capture of pawn */
return 1;
}
/* probe kpk bitbase (as white with the pawn) */
if (pCol == 0) {
/* my internal chess board square mapping is unusual, (a1, a2, a3,...) -> (0, 1, 2, ...)
* convert to mapping of bitbase */
probeWk = sqMapA1B1[pK];
probeBk = sqMapA1B1[loneK];
probeWp = sqMapA1B1[p];
stm = side;
} else {
/* flip everything */
probeWk = 63 - sqMapA1B1[pK];
probeBk = 63 - sqMapA1B1[loneK];
probeWp = 63 - sqMapA1B1[p];
stm = side ^ 1;
}
index = 2 * ((probeBk >> 3) + 8 * probeWk + 8 * 64 * ((probeWp - 8) >> 1)) + 1 * stm;
/* probe bitbase; 1 == win, 0 == draw */
win = (bitbase[index] >> (probeBk & 7)) & 1;
if (!win) {
return 1;
}
const int promSq = PROMOTE_SQ(p, pCol);
const int pFrontSq = pCol ? p - 1 : p + 1;
int x = v5Pawn
- DIST(p, promSq)
- (pFrontSq == loneK ? 8 : 0)
- (DIST(pK, p) > DIST(loneK, p) ? 8 : -8)
- (DIST(pK, pFrontSq) > DIST(loneK, pFrontSq) ? 8 : -8)
- (DIST(pK, promSq) > DIST(loneK, promSq) ? 16 : -16);
ASSERT_COLOR_SYMM(side ? (pCol ? x : -x) : (pCol ? -x : x));
return (pOnMove ? x : -x);
}
Rasjid.
-
- Posts: 2929
- Joined: Sat Jan 22, 2011 12:42 am
- Location: NL
Re: How to implement KPK ?
Returning a draw is fine when you detect that the position is a draw, but I wouldn't do anything if the position is not a draw. You already know that the position is either drawn or won, so if it isn't drawn what you have to do is make sure that the engine makes progress towards winning. You do that with just the regular scoring of passed pawns/king position in the end game. The engine will then automatically seek out lines where the pawn is advanced and eventually promotes (by the way, make sure you get the value of a passed pawn that is about to promote right; if it's too high the engine may prefer to keep the pawn around rather than promote it). Introducing a "bonus" for having a won position will confuse things and may cause problems if you don't always give that bonus in a won position (as per above: the engine could prefer keeping the pawn around because it sees promoting the pawn as a drop in score).Chan Rasjid wrote:My kpk evaluation returns 0/1 when it is a draw. If a win, it will return 5 x pawn and some simple evaluation terms. Maybe, someone who have implemented kpk sucessfully may check my codes to see if it should work. If it should work, then it means there are bugs in my search that somehow escaped detection.
-
- Posts: 27842
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: How to implement KPK ?
If they already play the right moves at low depth they must have knowledge (like a hefty bonus for King in front of Pawn, or for having opposition). They will all have a bonus for advancing the Pawn, and the quickest way to do that is supporting it with your King from behind, which is of course exactly what draws. But there is no way for the engine to see it draws before it actually reaches all the way across the board, which takes more depth.
Fairy-Max is a good example of what you get without any specific knowledge:
You can see that it considers many drawing moves (Kf1, Kd1, e3) before it finally sees the promotion.
Fairy-Max is a good example of what you get without any specific knowledge:
Code: Select all
26 +8.20 10.9M 0:18.73 e1f2 e8f8 f2e3 f8g7 e3d4 g7f6 d4e4 f6e6
25 +1.85 4.4M 0:08.19 e1f2 e8f8 f2e3 f8e7
24 +1.86 4.0M 0:07.43 e1f2 e8d7 f2e3 d7e7 e3f4 e7e6 f4e4 e6d6 e4f5
23 +1.86 3.6M 0:06.83 e1f2 e8d7 f2e3 d7e7 e3f4 e7e6 f4e4 e6d6 e4d4
22 +1.87 3.0M 0:05.72 e1f2 e8d7 f2e3 d7e7 e3f4 e7d6 f4f5 d6e7 e2e4
21 +1.90 2.0M 0:04.15 e1f2 e8d7 f2e3 d7d6 e3d4 d6e6 e2e4 e6d6 e4e5 d6e6 d4e4 e6e7 e4f5 e7d7
20 +1.93 1.3M 0:02.88 e1f2 e8d7 f2e3 d7d6 e3d4 d6e6 e2e4 e6d6 e4e5 d6e7 d4e4 e7e6
19 +1.51 761909 0:01.94 e1f2 e8d7 f2e3 d7d6 e3f4 d6e6 e2e3 e6f6 e3e4 f6g6 e4e5 g6g7 f4f5 g7f7 e5e6 f7e7 f5e5 e7e8 e5e4
18 +1.48 612798 0:01.66 e1f2 e8d7 f2e3 d7d6 e3f4 d6e6 e2e4 e6f6 e4e5 f6e6 f4e4 e6e7 e4f5
17 +1.44 478310 0:01.39 e1f2 e8d7 f2e3 d7d6 e3f4 d6d5 e2e4 d5d6 f4f5 d6e7 e4e5 e7f7 f5f4
16 +1.44 322845 0:01.10 e1f2 e8d7 f2e3 d7d6 e3f4 d6d5 e2e4 d5d6 f4f5 d6c5
15 +1.32 220508 0:00.88 e1f2 e8d7 f2e3 d7d6 e3d4 d6c6 e2e4 c6d6 e4e5 d6e6 d4e4 e6e7 e4f5 e7f7 e5e6
14 +0.94 180226 0:00.74 e1f2 e8d7 f2e3 d7d6 e3d4 d6c6 e2e4 c6d6 e4e5 d6e6 d4e4
14 +0.80 140703 0:00.59 e1d1 e8e7 e2e4 e7e6 d1e2
14 +0.79 127866 0:00.54 e1f1 e8e7 e2e4 e7f7 f1e2 f7e6 e2f2 e6f6 f2e3
13 +0.85 110176 0:00.47 e1f1 e8e7 e2e4 e7e6 f1e2 e6e5
13 +0.83 99812 0:00.43 e2e3 e8f7 e1e2 f7f6 e3e4 f6e6 e2f2 e6e5 f2e3
12 +0.80 88763 0:00.38 e2e3 e8f7 e1d2 f7e6 e3e4 e6e5 d2e3 e5f6 e3f2 f6e6
12 +0.71 72541 0:00.30 e1f2
12 +0.70 69094 0:00.28 e1f2 e8e7 f2e3 e7f6 e3f4 f6e6 e2e4 e6f6 e4e5 f6e6 f4e4 e6e7
11 +0.87 47144 0:00.18 e1f2 e8e7 f2f3 e7e6 f3f4 e6d5 e2e4 d5d4 e4e5 d4d5
10 +0.82 35746 0:00.15 e1f2 e8e7 f2f3 e7f6 f3g4 f6e5 g4g5 e5e4 g5f6 e4f4
10 +0.75 30842 0:00.13 e1f1 e8f7 e2e4 f7e6 f1e2 e6e5 e2f3
9 +0.75 26114 0:00.11 e1f1 e8f7 f1f2 f7f6 e2e4 f6e5 f2f3
9 +0.66 20762 0:00.09 e1d2 e8d8 e2e4 d8d7 d2d3 d7e6
8 +0.90 10710 0:00.06 e1d2 e8e7 d2d3 e7e6 d3e4 e6f6 e2e3 f6e6
7 +0.94 8916 0:00.06 e1d2 e8e7 d2d3 e7f6 d3d4 f6f5
7 +0.83 5931 0:00.03 e1f2 e8e7 e2e4 e7e6 f2e3 e6e5 e3f3
7 +0.81 5386 0:00.01 e1f1 e8e7 e2e4 e7f6 f1g2 f6e6
7 +0.77 3874 0:00.01 e1d1 e8e7 e2e4 e7e6 d1d2 e6e5 d2e3
6 +0.74 2188 0:00.00 e1d1 e8e7 e2e4 e7e6 d1d2 e6e5
6 +0.73 1912 0:00.00 e1f2 e8e7 e2e4 e7e6 f2e3 e6e5
5 +0.92 1029 0:00.00 e1f2 e8e7 e2e4 e7e6 f2e3
5 +0.71 759 0:00.00 e1d1 e8e7 e2e4 e7e6 d1e2
4 +0.75 429 0:00.00 e1d1 e8e7 e2e4 e7e6
4 +0.71 364 0:00.00 e1f1 e8e7 e2e4 e7e6
4 +0.60 293 0:00.00 e1d2 e8e7 e2e4 e7e6
3 +0.90 192 0:00.00 e1d2 e8e7 e2e4
3 +0.84 158 0:00.00 e1f2 e8e7 e2e4
3 +0.64 126 0:00.00 e1f1 e8e7 e2e4
3 +0.59 89 0:00.00 e1d1 e8e7 e2e4
2 +0.78 35 0:00.00 e1d1 e8e7
2 +0.74 17 0:00.00 e1f2 e8e7
1 +0.84 9 0:00.00 e1f2
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: How to implement KPK ?
Why would you need any king properties for evaluating a bitbase-won position? Wouldn't it be fully sufficient to use the distance to promotion to guide the search (where you only use one king property if the winner's king is on the promotion path so the distance gets incremented by one)? Advancing the pawn at the wrong time will be covered by getting a draw score from probing, and the same applies to "wrong" king moves leading to a draw.Evert wrote:Returning a draw is fine when you detect that the position is a draw, but I wouldn't do anything if the position is not a draw. You already know that the position is either drawn or won, so if it isn't drawn what you have to do is make sure that the engine makes progress towards winning. You do that with just the regular scoring of passed pawns/king position in the end game. The engine will then automatically seek out lines where the pawn is advanced and eventually promotes (by the way, make sure you get the value of a passed pawn that is about to promote right; if it's too high the engine may prefer to keep the pawn around rather than promote it). Introducing a "bonus" for having a won position will confuse things and may cause problems if you don't always give that bonus in a won position (as per above: the engine could prefer keeping the pawn around because it sees promoting the pawn as a drop in score).Chan Rasjid wrote:My kpk evaluation returns 0/1 when it is a draw. If a win, it will return 5 x pawn and some simple evaluation terms. Maybe, someone who have implemented kpk sucessfully may check my codes to see if it should work. If it should work, then it means there are bugs in my search that somehow escaped detection.
Sven
-
- Posts: 588
- Joined: Thu Mar 09, 2006 4:47 pm
- Location: Singapore
Re: How to implement KPK ?
When things don't go as I expected, I usually start with a 'healthy' dose of doubts about my own understanding. But now, what you and Muller said confirms that my understanding of how chess search works here is still sound - an alpha-beta engine with just material evaluation will still not make weird chess moves. So my kpk routine should be very much better.Evert wrote:Returning a draw is fine when you detect that the position is a draw, but I wouldn't do anything if the position is not a draw. You already know that the position is either drawn or won, so if it isn't drawn what you have to do is make sure that the engine makes progress towards winning. You do that with just the regular scoring of passed pawns/king position in the end game. The engine will then automatically seek out lines where the pawn is advanced and eventually promotes (by the way, make sure you get the value of a passed pawn that is about to promote right; if it's too high the engine may prefer to keep the pawn around rather than promote it). Introducing a "bonus" for having a won position will confuse things and may cause problems if you don't always give that bonus in a won position (as per above: the engine could prefer keeping the pawn around because it sees promoting the pawn as a drop in score).Chan Rasjid wrote:My kpk evaluation returns 0/1 when it is a draw. If a win, it will return 5 x pawn and some simple evaluation terms. Maybe, someone who have implemented kpk sucessfully may check my codes to see if it should work. If it should work, then it means there are bugs in my search that somehow escaped detection.
My implementation of 'win' is exactly as what you said, basically about the pawn promoting successfully. Only thing is that the usual passed pawn codes are more complex.
Lately, strange things is happening with my engine. As in what I posted in the other thread "An Evaluation Mystery", I almost have to doubt that the GCC compiler is failing in a strange manner! I'll just re-install GCC in my Arch Linux system though it is unbelievable it could be in error over such simple lines of codes.
I'll sit back for a while and may try to solve these bugs through a more well rounded and holistic approach - adding 'prayer'.
Best Regards,
Rasjid.
-
- Posts: 588
- Joined: Thu Mar 09, 2006 4:47 pm
- Location: Singapore
Re: How to implement KPK ?
Exactly as I understand!Sven Schüle wrote:Why would you need any king properties for evaluating a bitbase-won position? Wouldn't it be fully sufficient to use the distance to promotion to guide the search (where you only use one king property if the winner's king is on the promotion path so the distance gets incremented by one)? Advancing the pawn at the wrong time will be covered by getting a draw score from probing, and the same applies to "wrong" king moves leading to a draw.Evert wrote:Returning a draw is fine when you detect that the position is a draw, but I wouldn't do anything if the position is not a draw. You already know that the position is either drawn or won, so if it isn't drawn what you have to do is make sure that the engine makes progress towards winning. You do that with just the regular scoring of passed pawns/king position in the end game. The engine will then automatically seek out lines where the pawn is advanced and eventually promotes (by the way, make sure you get the value of a passed pawn that is about to promote right; if it's too high the engine may prefer to keep the pawn around rather than promote it). Introducing a "bonus" for having a won position will confuse things and may cause problems if you don't always give that bonus in a won position (as per above: the engine could prefer keeping the pawn around because it sees promoting the pawn as a drop in score).Chan Rasjid wrote:My kpk evaluation returns 0/1 when it is a draw. If a win, it will return 5 x pawn and some simple evaluation terms. Maybe, someone who have implemented kpk sucessfully may check my codes to see if it should work. If it should work, then it means there are bugs in my search that somehow escaped detection.
Sven
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: How to implement KPK ?
Yes, but I get the impression that your evaluation is a bit too complex and has some parts which are not needed. For instance, if you already know that the position is won then IMO it does not matter whether the enemy king is on the square in front of the pawn. There are only very few cases where this can occur in a won position (e.g. wKd6, Pc7, bKc8, btm) and the search will immediately find the winning line on its own. Also your two conditions regarding the distances of the kings to the pawn square and their distances to the square in front of the pawn are almost redundant, i.e. at most one of them would be sufficient. Finally I believe that you should give a bigger weight to the distance to promotion itself, e.g. by applying a factor of 8. Otherwise your program might frequently miss to play the fastest path to promotion since it gives equal weight to "good" king moves.Chan Rasjid wrote:Exactly as I understand!Sven Schüle wrote:Why would you need any king properties for evaluating a bitbase-won position? Wouldn't it be fully sufficient to use the distance to promotion to guide the search (where you only use one king property if the winner's king is on the promotion path so the distance gets incremented by one)? Advancing the pawn at the wrong time will be covered by getting a draw score from probing, and the same applies to "wrong" king moves leading to a draw.Evert wrote:Returning a draw is fine when you detect that the position is a draw, but I wouldn't do anything if the position is not a draw. You already know that the position is either drawn or won, so if it isn't drawn what you have to do is make sure that the engine makes progress towards winning. You do that with just the regular scoring of passed pawns/king position in the end game. The engine will then automatically seek out lines where the pawn is advanced and eventually promotes (by the way, make sure you get the value of a passed pawn that is about to promote right; if it's too high the engine may prefer to keep the pawn around rather than promote it). Introducing a "bonus" for having a won position will confuse things and may cause problems if you don't always give that bonus in a won position (as per above: the engine could prefer keeping the pawn around because it sees promoting the pawn as a drop in score).Chan Rasjid wrote:My kpk evaluation returns 0/1 when it is a draw. If a win, it will return 5 x pawn and some simple evaluation terms. Maybe, someone who have implemented kpk sucessfully may check my codes to see if it should work. If it should work, then it means there are bugs in my search that somehow escaped detection.
Sven
As I already mentioned, I would only take care about the friendly king's position at all if it is on the promotion path.
Sven
-
- Posts: 838
- Joined: Thu Jul 05, 2007 5:03 pm
- Location: British Columbia, Canada
Re: How to implement KPK ?
In case you haven't read it already, read how Heinz et al. handled this in Darkthought 15 years ago.
They had bitbases for W/D or W/L/D and then the interior node recognizers would make a heuristic score to help drive it towards the win when in a won position (or try to delay a loss etc).
An important thing they discovered was that the had to make the heuristic scoring range for each recognized ending compatible with the normal evaluation scores. If the heuristic was too high or low, odd play would result (such as the engine trying to avoid promoting, etc).
[edit: in one of Heinz's papers somewhere, they list all of the heuristic scoring functions they used for all 3- and 4-man endings. "Knowledgable Encoding and Querying of Endgame Databases", it can be found with Google]
They had bitbases for W/D or W/L/D and then the interior node recognizers would make a heuristic score to help drive it towards the win when in a won position (or try to delay a loss etc).
An important thing they discovered was that the had to make the heuristic scoring range for each recognized ending compatible with the normal evaluation scores. If the heuristic was too high or low, odd play would result (such as the engine trying to avoid promoting, etc).
[edit: in one of Heinz's papers somewhere, they list all of the heuristic scoring functions they used for all 3- and 4-man endings. "Knowledgable Encoding and Querying of Endgame Databases", it can be found with Google]
-
- Posts: 588
- Joined: Thu Mar 09, 2006 4:47 pm
- Location: Singapore
Re: How to implement KPK ?
Hello Wylie,
Thanks for the links. I'll see whether it is bugs or some failure in my understanding.
Bets Regards,
Rasjid.
Thanks for the links. I'll see whether it is bugs or some failure in my understanding.
Bets Regards,
Rasjid.