Using Stockfish bitbase.cpp from stockfish-23-ja as a start, I've created a pascal unit generating the kpk bitbase at start up.
In total 196608 (2 * 24 * 64 * 64; // stm * wpsq * wksq * bksq = 196608) positions are classified in the bitbase as either won or draw. Only 24 squares for the white pawn (A2..D2..D7..A7) are considered by mirroring the position when the pawn is on E to H file.
The bitbase is generated in less than 55 ms at startup of the engine.
The basic algorithm of the kpk bitbase generation is:
1. Initial evaluation of all 196608 positions, using the set of rules below, resulting in following classification:
After static eval:
Total WIN: 42524
Total DRAW: 12240
Total INVALID: 30932
Total UNKNOWN: 110912
TIME: 8
Rules implemented:
Code: Select all
{Check for INVALID positions}
{1.1. Check if two pieces are on the same square or if king are adjacent
or psq of RANK_1 or RANK_8}
if (wksq=psq) or
(wksq=bksq) or
(bksq=psq) or
(psq<A2) or (psq>H7) or
(distance64(wksq,bksq)<2)
then exit(INVALID);
{1.2. Check if black king can be captured by pawn}
if wtm then
begin
if ((file_of(psq)>FILE_A) and (psq+DELTA_NW=bksq)) or
((file_of(psq)<FILE_H) and (psq+DELTA_NE=bksq))
then exit(INVALID);
end;
{Check for DRAW positions}
lsq:=psq+DELTA_N; //stop square
{2.1. Stalemate}
if (not wtm)
then
begin
if (bksq=A8) and (psq=C7) and ((wksq=A6) or (wksq=B6)) then exit(DRAW);
if (bksq=A8) and (psq=A7) and ((wksq=A6) or (wksq=B6)) then exit(DRAW);
if (bksq=A8) and (psq=B6) and ((wksq=C7) or (wksq=C8)) then exit(DRAW);
if (bksq=B8) and (psq=B7) and (wksq=B6) then exit(DRAW);
if (bksq=C8) and (psq=C7) and (wksq=C6) then exit(DRAW);
if (bksq=D8) and (psq=D7) and (wksq=D6) then exit(DRAW);
end;
{2.2. Black king can capture undefended pawn}
if (not wtm) and
(distance64(bksq,psq)=1) and
(distance64(wksq,psq)>1)
then exit(DRAW);
{2.3. Black king in front of white pawn, black king not on 8th rank}
if (bksq=lsq) and
(psq<A7) //(rank_of(psq)<RANK_7)
then exit(DRAW);
{2.4. White king in front of pawn and black has opposition, i.e white to move
and pawn is not a rook pawn, black king not on 8th rank}
if wtm and
(wksq=lsq) and
(file_of(psq)<>FILE_A) and
(psq<A6) and //(rank_of(psq)<=RANK_5)
(bksq<A8) and //(rank_of(bksq)<=RANK_7)???
(bksq=wksq+DELTA_N+DELTA_N)
then exit(DRAW);
{2.5. Stalemate with rook pawn}
if (bksq=A8) and
(file_of(psq)=FILE_A)
then exit(DRAW);
{2.6. White pawn on A file and Black King on B7 or B8 is always draw}
if (bksq in [B7,B8]) and
(file_of(psq)=FILE_A)
then exit(DRAW);
{2.7. White king trapped on A8}
if wtm and
(wksq=A8) and
(psq=A7) and
((bksq=C8) or (bksq=C7))
then exit(DRAW);
{2.8. White king trapped on the rook file}
if (wksq>psq) and
(file_of(wksq)=FILE_A) and
(file_of(psq)=FILE_A) and
(bksq=wksq+DELTA_E+DELTA_E)
then exit(DRAW);
{2.9. Black king as above, the White king diagonally behind the pawn,
white side to move}
if wtm and
(bksq=lsq) and
(
((file_of(psq)>FILE_A) and (wksq=psq+DELTA_SW)) or
((file_of(psq)<FILE_H) and (wksq=psq+DELTA_SE))
)
then exit(DRAW);
{2.10. Kings stand in the vertical opposition and
the pawn is on the right/left side of the white king,
white to move}
if wtm and
(wksq<A6) and (bksq=wksq+DELTA_N+DELTA_N) and
(
((file_of(wksq)<FILE_H) and (psq=wksq+DELTA_E)) or //pawn right to king
((file_of(wksq)>FILE_A) and (psq=wksq+DELTA_W)) //pawn left of king
)
then exit(DRAW);
{2.11. In the above position the white pawn moves, giving check}
if not wtm and
(wksq<A6) and (bksq=wksq+DELTA_N+DELTA_N) and
(
((file_of(wksq)<FILE_H) and (psq=wksq+DELTA_NE)) or
((file_of(wksq)>FILE_A) and (psq=wksq+DELTA_NW))
)
then exit(DRAW);
{2.12. The following code marks positions as drawn, http://chessprogramming.wikispaces.com/KPK
Black king not on 8th rank, 2 squares in front of pawn,
White king behind pawn, pawn on 5th rank or lower, white to move}
if wtm and
(bksq<A8) and //BK not on 8th rank
(psq<A6) and //WP on fifth rank or lower
(wksq<A5) and //WK on fourth rank or lower
(
((file_of(psq)>FILE_A) and (bksq=lsq+DELTA_NW)) or
((bksq=lsq+DELTA_N)) or
((file_of(psq)<FILE_H) and (bksq=lsq+DELTA_NE))
) and
(
((file_of(psq)>FILE_A) and (wksq=psq+DELTA_SW)) or
((wksq=psq+DELTA_S)) or
((file_of(psq)<FILE_H) and (wksq=psq+DELTA_SE))
)
then exit(DRAW);
{2.13. Rook pawn, white king A6 black king on A8}
if (wksq=A6) and
(bksq=A8) and
(psq<A6) and
(file_of(psq)=FILE_A)
then exit(DRAW);
{If the white king is in front of the pawn and neither of the other two conditions is met,
(b) he has the opposition
(c) his king is on the sixth rank,
so black king is not on wksq+DELTA_NN or wtm; and
white king is not on 6th rank}
{2.14 a. white in front of pawn, black king on same file DELTA_N+DELTA_N+DELTA_N, black to move}
if not wtm and
(wksq=lsq) and
(wksq<A6) and
(bksq=wksq+DELTA_N+DELTA_N+DELTA_N)
then exit(DRAW);
{Check WIN positions}
{3.1. The position is an immediate win if it is white to move and
the white pawn can be promoted without getting captured.}
if wtm and
(psq>H6) and //(rank_of(psq)=RANK_7)
(wksq<>lsq) and
((distance64(bksq,lsq)>1) or (distance64(wksq,lsq)=1))
then exit(WIN);
{3.2. Immediate win if pawn is advanced and has free path}
if wtm and
(psq>bksq) and
(rank_of(psq)>rank_of(bksq)) and
((psq>wksq) or (file_of(psq)<>file_of(wksq)))
then exit(WIN);
{3.3. Win if pawn is on 6th rank and White King is adjacent on 7th rank}
if (rank_of(psq)=RANK_6) and
(
((file_of(psq)>FILE_A) and (wksq=psq+DELTA_NW)) or
((file_of(psq)<FILE_H) and (wksq=psq+DELTA_NE))
)
then exit(WIN);
{3.4. White king in front of pawn and white has opposition, i.e black to move
and pawn is not a rook pawn}
if not wtm and
(wksq=lsq) and
(file_of(psq)<>FILE_A) and
(psq<A6) and //(rank_of(psq)<=RANK_5)
// (bksq<A8) and //(rank_of(bksq)<=RANK_7)???
(bksq=wksq+DELTA_N+DELTA_N)
then exit(WIN);
{3.5. White king in front of pawn and white king on sixth rank,
either side to move and pawn is not a rook pawn}
if (wksq=lsq) and
(rank_of(wksq)=RANK_6) and
(file_of(psq)<>FILE_A)
then exit(WIN);
{3.6. White king on sixth rank, and has opposition, i.e. black to move,
pawn is not a rook pawn and not on seventh rank}
if not wtm and
(rank_of(wksq)=RANK_6) and
(bksq=wksq+DELTA_N+DELTA_N) and
(psq<A7) and
(file_of(psq)<>FILE_A)
then exit(WIN);
{3.7 White king on key sqare DELTA_N+(DELTA_NW,DELTA_N,DELTA_NE),
pawn on 2nd 3rd or 4th rank, not a rook pawn}
if (file_of(psq)<>FILE_A) and
(psq<A5) and
(
(wksq=lsq+DELTA_NW) or
(wksq=lsq+DELTA_N) or
(wksq=lsq+DELTA_NE)
)
then exit(WIN);
{3.8. White king on key square (DELTA_NW,DELTA_N,DELTA_NE) or DELTA_N+(DELTA_NW,DELTA_N,DELTA_NE),
pawn on 5th rank, not a rook pawn}
if (file_of(psq)<>FILE_A) and
(rank_of(psq)=RANK_5) and
(
(wksq=psq+DELTA_NW) or
(wksq=lsq) or
(wksq=psq+DELTA_NE) or
(wksq=lsq+DELTA_NW) or
(wksq=lsq+DELTA_N) or
(wksq=lsq+DELTA_NE)
)
then exit(WIN);
A. if white to move then generate all white king and pawn moves. If one move leads to a WIN position then the current position is a WIN; if all moves lead to a DRAW then the position is a DRAW; else the position remains UNKNOWN.
B. if black to move then generate all black king moves. If one move leads to a DRAW position then the current position is a DRAW; if all moves lead to a WIN then the position is a WIN; else the position remains UNKNOWN.
In total 18 iterations are required to classify all 196608 positions, as:
WIN: 111282
DRAW: 54394
INVALID: 30932
UNKNOWN: 0
TIME: 55
C. Map all positions to the bitbase, an array of 196608 bits grouped in 32bit unsigned integers (total 6144 integers), where 1 indicates a WIN and 0 is a DRAW/INVALID/UNKNOWN position.
Not all of above rules are required to obtain a correct result. Without rules 2.5, 2.6, 2.9-2.14, 3.2-3.8 the WIN positions are correctly identified, however some (1546) position remain classified as UNKNOWN, but in the final bitbase these are encoded as draw positions. Furthermore without these rules the retrograde analysis requires more iterations and thus more time, 88 ms.
In Stockfish a subset of above rules have been implemented, and a comment in the source states that "30 cycles needed" to classify all positions. When I implement the SF subset of rules then the 196608 positions are classified as:
Iter: 24
WIN: 111282
DRAW: 54004
INVALID: 30932
UNKNOWN: 390
TIME: 84
requiring 24 iterations in 60% more time: 84 ms. So all WIN positions are correctly classified, the final bitbase will thus correctly classify all positions.
The implementation of the KPK bitbase in my engine Troy (formerly known as Hector, http://chessprogramming.wikispaces.com/Hector), replacing the KPK evaluation function did hardly increase its playing strength, at least not beyond the level I can measure.
Unfortunately I could not find any source to confirm my statistics on the number WON/DRAW/INVALID positions, can anyone confirm my findings/statistics?
Regards, Maarten
