The Poor Man's KP Bitbase

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
D Sceviour
Posts: 417
Joined: Mon Jul 20, 2015 3:06 pm
Contact:

The Poor Man's KP Bitbase

Post by D Sceviour » Fri Jun 07, 2019 1:05 am

Why use the poor man's king-pawn (KP) bitbase? First, the bitbase is only 3K and thus very easy on resources. It could be compressed even further to 1.5K, but 3K is small enough to easily fit into the modern hardware cache. More compression may not be desirable because it will require extra decompression calculation. For comparison, a fully compressed KPK bitbase can cost 96K.

Second, timer tests show the pKprobe() is at least 30,000 times faster than the syzygy WDL probe. In most cases it will report the same result. Endgame table bases are often not probed until a certain depth and there may still be no horizon static evaluation for KPK endgames using endgame table bases.

Third, all piece and pawn endgames eventually search a position reduced to KPK. When the KP bitbase is used for horizon evaluations, it can help reduce the size of the endgame tree(test it!). Piece and pawn endgame evaluation is likely to fail at some point without some sort of KPK draw evaluation after exchanges.

Here is how I have developed the KP bitbase:

The bit table returns a draw=0, wtm unknown score=1, or btm unknown score=2 from the positions of the white pawn and the black king.

For KPK endgames, be careful on what final score to return for a known win. If the win score is returned as a value greater than the value of a queen, then the pawn may never queen. Undesirably, the position loops deeper trying not to queen the pawn. Thus, wins and unknown scores can be returned as the same small material (say 100) and position(PSQT) value. That is; the static evaluation does not change for non-drawn positions.

Observe from various table inspections that most KPK endgames are a win. If wins and unknown are values treated the same then we only have to look for forced draws. There are three drawing possibilities in KPK endings:

(1) outside passed pawn
(2) where weak king can force the opposition
(3) kings race for the pawn

Notice that for the first two possibilities, the position of the strong king is irrelevant. The draw only depends on the position of the weak black king. We can almost solve the entire KPK ending without knowing the position of the white king!

For example, in the following position the white king can be on any legal square and the position is still a draw with either side to move first:

[d]8/8/K1k5/P7/8/8/8/8 w - - 0 1

For the third possibility of kings racing for the pawn, the position has to be searched as "unknown but assume a win". The is safe in most cases. If the pawn can be captured on the next move then the position will resolve quickly as a draw. The bitbase can also help the weak side to triangulate into a drawn position. This is the small price the poor man has to pay.

Will the bitbase improve elo? Not much. But neither will syzygy WDL probes from my findings. This seems theoretically correct to include and should help solve endgame problems.

Finally, you will have to write your own code for your engine to probe the pKtable.

Code: Select all

// The Poor Man's KP Bitbase by Dennis Sceviour, 2019

static uint8_t pKtable[48][64];

void init_KP_bitbase() {
int sq,c,r;
int kingc,kingr,kingsq;

//preset table values as win or unknown
   memset (&pKtable[0][0], 3 , 48 * 64);

   for (sq = 8 ; sq < 56; sq++) {
	c = sq & 7;
	r = sq >> 3;

	for (kingsq = 0 ; kingsq < 64; kingsq++) {
	   kingc = kingsq & 7;
	   kingr = kingsq >> 3;

//outside pawn
	   if (!c) {
		if (kingc < 3) {
              if (kingr>r) pKtable[sq-8][kingsq] = 0; //draw
              if (kingr==r && kingc<2) {
			pKtable[sq-8][kingsq] &= 1;      //draw ktm
              }
		}
	   }
	   if (c==7) {
		if (kingc > 4) {
              if (kingr>r) pKtable[sq-8][kingsq] = 0;
              if (kingr==r && kingc>5) {
                 pKtable[sq-8][kingsq] &= 1;  //draw ktm
              }
		}
	   }

//add in front of pawn info
//if the losing king is one or two squares in front of the pawn, and the pawn has not reached the sixth then it is at least draw. White cannot get in front of the pawn. Black has the opposition or can take it.

	   if (r<5 && kingc==c) {
		if (kingr>r && kingr<r+3) pKtable[sq-8][kingsq] = 0;
	   }

	   if (r==5 && kingc==c) {
		if (kingr==(r+1)) pKtable[sq-8][kingsq] &= 1;  //draw ktm
	   }
	}
   }
}

Daniel Anulliero
Posts: 669
Joined: Fri Jan 04, 2013 3:55 pm
Location: Nice

Re: The Poor Man's KP Bitbase

Post by Daniel Anulliero » Mon Jun 10, 2019 5:32 am

Hello Denis
Amazing small code for this base , good work ! :)
I'll try It in my new engine BeLL (need some code's changes, as BeLL is 0x88)
Just a question : in your code, kingsq is the square of the losing king right ?
Does the kp table is filled when you run the engine?
Sq-8 is the square in front , right but can be sq+8 with a WP ?
Can you explain a little bit more ?
Thanks

Best
Dany Isa.BeLL

D Sceviour
Posts: 417
Joined: Mon Jul 20, 2015 3:06 pm
Contact:

Re: The Poor Man's KP Bitbase

Post by D Sceviour » Mon Jun 10, 2019 11:44 am

Daniel Anulliero wrote:
Mon Jun 10, 2019 5:32 am
Just a question : in your code, kingsq is the square of the losing king right ?
Hello Dany,
Yes. The position of the winning king is always ignored!
Does the kp table is filled when you run the engine?
Yes, the initialization code is very fast - in pica seconds? :-)
Sq-8 is the square in front, right but can be sq+8 with a WP ?
The wpawn-8 is for table decompression. You do not need to follow this until extracting the score. When probing you have to subtract 8 from the square of your pawn. The result returns draw = 0 or win/unknown = 1:

Code: Select all

// your probe
   result = pKtable[WPawn-8][BKing];

   if (side_to_move == WHITE)
       return (result & 1);
   else
       return (result >> 1);

Sven
Posts: 3771
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: The Poor Man's KP Bitbase

Post by Sven » Mon Jun 10, 2019 12:56 pm

D Sceviour wrote:
Fri Jun 07, 2019 1:05 am
Notice that for the first two possibilities, the position of the strong king is irrelevant. The draw only depends on the position of the weak black king. We can almost solve the entire KPK ending without knowing the position of the white king!

For example, in the following position the white king can be on any legal square and the position is still a draw with either side to move first:

[d]8/8/K1k5/P7/8/8/8/8 w - - 0 1
Not always true, the exception is wKb8 with White to move (a6 Kb6 a7 1-0) :-)
Sven Schüle (engine author: Jumbo, KnockOut, Surprise)

D Sceviour
Posts: 417
Joined: Mon Jul 20, 2015 3:06 pm
Contact:

Re: The Poor Man's KP Bitbase

Post by D Sceviour » Mon Jun 10, 2019 1:36 pm

Sven wrote:
Mon Jun 10, 2019 12:56 pm
D Sceviour wrote:
Fri Jun 07, 2019 1:05 am
Notice that for the first two possibilities, the position of the strong king is irrelevant. The draw only depends on the position of the weak black king. We can almost solve the entire KPK ending without knowing the position of the white king!

For example, in the following position the white king can be on any legal square and the position is still a draw with either side to move first:
[d]1K6/8/2k5/P7/8/8/8/8 w - - 0 1

Not always true, the exception is wKb8 with White to move (a6 Kb6 a7 1-0) :-)
Hello Sven,
That was a good find. It should read "with black king to move (ktm) first". I will update the code after some more bugs or ideas can be found.

D Sceviour
Posts: 417
Joined: Mon Jul 20, 2015 3:06 pm
Contact:

Re: The Poor Man's KP Bitbase

Post by D Sceviour » Tue Jun 11, 2019 3:55 pm

This KP bitbase version updates a few more draw positions. Some test positions are included. The extra draws will not make much difference. The strength of the KP bitbase is in its resiliency and residency, and not its completeness. The idea is to prune known positional draws and to reduce nodes on the horizon. It is not intended to report wins. Wins still have to be proven by queening the pawn. That should be true of all KPK table bases used on the horizon. Table bases used at the root such as Syzygy DTZ are a different matter. They require a much higher degree of accuracy. The KP bitbase should not be used for a true root score during games, even if it does report correctly 99% of all positions.

Code: Select all

#define QA8 ((1ull << A8) | (1ull << A7) | (1ull << B8) | (1ull << B7))
#define QH8 ((1ull << H8) | (1ull << H7) | (1ull << G8) | (1ull << G7))

void init_KP_bitbase() {
int sq,c,r;
int kingc,kingr,kingsq;

//preset table values as win or unknown
   memset (&pKtable[0][0], 3 , 48 * 64);

   for (sq = 8 ; sq < 56; sq++) {
      c = sq & 7;
      r = sq >> 3;

      for (kingsq = 0 ; kingsq < 64; kingsq++) {
         if (sq == kingsq) continue;
         kingc = kingsq & 7;
         kingr = kingsq >> 3;

//outside pawn
         if (!c) {
		if (kingc < 3) {
              if (kingr>r) {
// 1K6/8/2k5/P7/8/8/8/8 b - - 0 1
                 pKtable[sq-8][kingsq] &=1 ; //draw ktm
// 8/1k6/8/P1K5/8/8/8/8 w - - 0 1
                 if (kingc < 2) pKtable[sq-8][kingsq] = 0; //draw
              }
// 8/1K6/8/Pk6/8/8/8/8 b - - 0 1
              if (sq == kingsq-1) 
                 pKtable[sq-8][kingsq] &=1 ; //draw ktm
		}
// 8/Pk6/8/K7/8/8/8/8 w - - 0 1
           if ((1ull << kingsq) & QA8) pKtable[sq-8][kingsq] = 0;
	   }
	   if (c==7) {
		if (kingc > 4) {
              if (kingr>r) {
                 pKtable[sq-8][kingsq] &= 1; //draw ktm
                 if (kingc > 5) pKtable[sq-8][kingsq] = 0; //draw
              }
              if (sq == kingsq+1) 
                 pKtable[sq-8][kingsq] &=1 ; //draw ktm
		}
           if ((1ull << kingsq) & QH8) pKtable[sq-8][kingsq] = 0;

	   }

//add in front of pawn info
//if the losing king is one or two squares in front of the pawn, and the pawn has not reached the sixth then it is at least draw. White cannot get in front of the pawn. Black has the opposition or can take it.

	   if (r<5 && kingc==c) {
		if (kingr>r && kingr<r+3) pKtable[sq-8][kingsq] = 0;
	   }

	   if (r==5 && kingc==c) {
		if (kingr==(r+1)) pKtable[sq-8][kingsq] = 0;  //draw
// 3k4/8/3PK3/8/8/8/8/8 b - - 0 1
		if (kingr==(r+2)) pKtable[sq-8][kingsq] &= 1; //ktm draw
	   }
	}
   }
}

Post Reply