Stockfish 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.
kongsian
Posts: 46
Joined: Thu Jun 15, 2006 9:21 am

Stockfish bitbase

Post by kongsian » Tue Jun 01, 2010 8:57 am

I'm writing my own KPK bitbase code and using Stockfish bitbase.cpp for debugging. I found that Stockfish bitbase code is imperfect; it is unable to classify 17826 positions.

I was able to classify all positions and decide to implement the changes to Stockfish 1.7.1.

Code: Select all

diff --git a/bitbase.cpp b/bitbase.cpp
index 801815e..818b679 100755
--- a/bitbase.cpp
+++ b/bitbase.cpp
@@ -152,6 +152,28 @@ namespace {
       if(whiteKingSquare == SQ_A8 && pawnSquare == SQ_A7 &&
          (blackKingSquare == SQ_C7 || blackKingSquare == SQ_C8))
         return true;
+
+      // Case 3: white king in front of white pawn and no opposition
+      if(whiteKingSquare == pawnSquare+DELTA_N &&
+         blackKingSquare == pawnSquare+3*DELTA_N &&
+         pawnSquare < SQ_A5&#41;
+       return true;
+    &#125;
+
+    //  Case 4&#58; black king in front of white pawn
+    if&#40;blackKingSquare == pawnSquare+DELTA_N && pawnSquare < SQ_A7&#41;
+      return true;
+
+    //  Case 5&#58; rook file
+    if&#40;square_file&#40;pawnSquare&#41; == FILE_A&#41;
+    &#123;
+      if &#40;blackKingSquare == SQ_A8&#41;
+        return true;
+
+      if &#40;square_file&#40;whiteKingSquare&#41; == FILE_A &&
+          square_file&#40;blackKingSquare&#41; == FILE_C &&
+          blackKingSquare > pawnSquare&#41;
+        return true;
     &#125;

     return false;

Kong Sian

mcostalba
Posts: 2684
Joined: Sat Jun 14, 2008 7:17 pm

Re: Stockfish bitbase

Post by mcostalba » Tue Jun 01, 2010 6:05 pm

kongsian wrote:I'm writing my own KPK bitbase code and using Stockfish bitbase.cpp for debugging. I found that Stockfish bitbase code is imperfect; it is unable to classify 17826 positions.

I was able to classify all positions and decide to implement the changes to Stockfish 1.7.1.
Hi Kongsian,

thanks a lot for this patch. I will test and apply to current development branch.

Thanks ! :-)

Tord Romstad
Posts: 1808
Joined: Wed Mar 08, 2006 8:19 pm
Location: Oslo, Norway

Re: Stockfish bitbase

Post by Tord Romstad » Tue Jun 01, 2010 6:51 pm

kongsian wrote:I'm writing my own KPK bitbase code and using Stockfish bitbase.cpp for debugging. I found that Stockfish bitbase code is imperfect; it is unable to classify 17826 positions.

I was able to classify all positions and decide to implement the changes to Stockfish 1.7.1.

Code: Select all

diff --git a/bitbase.cpp b/bitbase.cpp
index 801815e..818b679 100755
--- a/bitbase.cpp
+++ b/bitbase.cpp
@@ -152,6 +152,28 @@ namespace &#123;
       if&#40;whiteKingSquare == SQ_A8 && pawnSquare == SQ_A7 &&
          &#40;blackKingSquare == SQ_C7 || blackKingSquare == SQ_C8&#41;)
         return true;
+
+      // Case 3&#58; white king in front of white pawn and no opposition
+      if&#40;whiteKingSquare == pawnSquare+DELTA_N &&
+         blackKingSquare == pawnSquare+3*DELTA_N &&
+         pawnSquare < SQ_A5&#41;
+       return true;
+    &#125;
+
+    //  Case 4&#58; black king in front of white pawn
+    if&#40;blackKingSquare == pawnSquare+DELTA_N && pawnSquare < SQ_A7&#41;
+      return true;
+
+    //  Case 5&#58; rook file
+    if&#40;square_file&#40;pawnSquare&#41; == FILE_A&#41;
+    &#123;
+      if &#40;blackKingSquare == SQ_A8&#41;
+        return true;
+
+      if &#40;square_file&#40;whiteKingSquare&#41; == FILE_A &&
+          square_file&#40;blackKingSquare&#41; == FILE_C &&
+          blackKingSquare > pawnSquare&#41;
+        return true;
     &#125;

     return false;

Kong Sian
Hello Kongsian,

I am not sure I understand the purpose of this patch. Unless I am missing something, your patch simply adds a few rules for identifying draws which are already detected by the bitbase generation code. The generated bitbase will be (again, unless I am missing something) 100% identical to the one generated by Stockfish 1.7.1. The only thing that perhaps changes is that bitbase generation will be a tiny bit faster.

kongsian
Posts: 46
Joined: Thu Jun 15, 2006 9:21 am

Re: Stockfish bitbase

Post by kongsian » Tue Jun 01, 2010 9:13 pm

Tord Romstad wrote:
kongsian wrote:I'm writing my own KPK bitbase code and using Stockfish bitbase.cpp for debugging. I found that Stockfish bitbase code is imperfect; it is unable to classify 17826 positions.

I was able to classify all positions and decide to implement the changes to Stockfish 1.7.1.

Code: Select all

diff --git a/bitbase.cpp b/bitbase.cpp
index 801815e..818b679 100755
--- a/bitbase.cpp
+++ b/bitbase.cpp
@@ -152,6 +152,28 @@ namespace &#123;
       if&#40;whiteKingSquare == SQ_A8 && pawnSquare == SQ_A7 &&
          &#40;blackKingSquare == SQ_C7 || blackKingSquare == SQ_C8&#41;)
         return true;
+
+      // Case 3&#58; white king in front of white pawn and no opposition
+      if&#40;whiteKingSquare == pawnSquare+DELTA_N &&
+         blackKingSquare == pawnSquare+3*DELTA_N &&
+         pawnSquare < SQ_A5&#41;
+       return true;
+    &#125;
+
+    //  Case 4&#58; black king in front of white pawn
+    if&#40;blackKingSquare == pawnSquare+DELTA_N && pawnSquare < SQ_A7&#41;
+      return true;
+
+    //  Case 5&#58; rook file
+    if&#40;square_file&#40;pawnSquare&#41; == FILE_A&#41;
+    &#123;
+      if &#40;blackKingSquare == SQ_A8&#41;
+        return true;
+
+      if &#40;square_file&#40;whiteKingSquare&#41; == FILE_A &&
+          square_file&#40;blackKingSquare&#41; == FILE_C &&
+          blackKingSquare > pawnSquare&#41;
+        return true;
     &#125;

     return false;

Kong Sian
Hello Kongsian,

I am not sure I understand the purpose of this patch. Unless I am missing something, your patch simply adds a few rules for identifying draws which are already detected by the bitbase generation code. The generated bitbase will be (again, unless I am missing something) 100% identical to the one generated by Stockfish 1.7.1. The only thing that perhaps changes is that bitbase generation will be a tiny bit faster.
Hi Tord. If you print out "UnknownCount" in next_iteration(), you will find that it terminates when UnknownCount == 17826. Here it is.

Code: Select all

cks@phobos&#58;~/chess/stockfish-171-linux/src$ ./stockfish
UnknownCount = 124671
UnknownCount = 105383
UnknownCount = 89411
UnknownCount = 76084
UnknownCount = 66653
UnknownCount = 58110
UnknownCount = 51257
UnknownCount = 40688
UnknownCount = 34235
UnknownCount = 32263
UnknownCount = 30371
UnknownCount = 28930
UnknownCount = 27359
UnknownCount = 25777
UnknownCount = 24327
UnknownCount = 23292
UnknownCount = 22423
UnknownCount = 21692
UnknownCount = 20923
UnknownCount = 20157
UnknownCount = 19507
UnknownCount = 18950
UnknownCount = 18485
UnknownCount = 18196
UnknownCount = 18011
UnknownCount = 17901
UnknownCount = 17846
UnknownCount = 17827
UnknownCount = 17826
UnknownCount = 17826
Stockfish 1.7.1 64bit. By Tord Romstad, Marco Costalba, Joona Kiiski.
With the changes.

Code: Select all

cks@phobos&#58;~/chess/stockfish-171-linux/src$ ./stockfish
UnknownCount = 122032
UnknownCount = 100203
UnknownCount = 81272
UnknownCount = 64474
UnknownCount = 52417
UnknownCount = 42441
UnknownCount = 34629
UnknownCount = 23349
UnknownCount = 16550
UnknownCount = 14451
UnknownCount = 12542
UnknownCount = 11097
UnknownCount = 9532
UnknownCount = 7952
UnknownCount = 6503
UnknownCount = 5468
UnknownCount = 4599
UnknownCount = 3867
UnknownCount = 3097
UnknownCount = 2331
UnknownCount = 1681
UnknownCount = 1124
UnknownCount = 659
UnknownCount = 370
UnknownCount = 185
UnknownCount = 75
UnknownCount = 20
UnknownCount = 1
UnknownCount = 0
UnknownCount = 0
Stockfish 1.7.1 64bit. By Tord Romstad, Marco Costalba, Joona Kiiski.
Kong Sian

Tord Romstad
Posts: 1808
Joined: Wed Mar 08, 2006 8:19 pm
Location: Oslo, Norway

Re: Stockfish bitbase

Post by Tord Romstad » Wed Jun 02, 2010 7:59 am

kongsian wrote:Hi Tord. If you print out "UnknownCount" in next_iteration(), you will find that it terminates when UnknownCount == 17826.
True. These are the positions where neither side can force a mate, a stalemate, or a draw by material. Because neither side can mate, they are drawn, and the existing bitbase code already classifies these positions as drawn. You just add some rules that detect them as drawn from the beginning instead of letting the bitbase generation function detect them as drawn. It probably makes bitbase generation a tiny bit faster, but the generated bitbase will be 100% identical (unless there is some bug I cannot see).

kongsian
Posts: 46
Joined: Thu Jun 15, 2006 9:21 am

Re: Stockfish bitbase

Post by kongsian » Wed Jun 02, 2010 8:28 am

Tord Romstad wrote:
kongsian wrote:Hi Tord. If you print out "UnknownCount" in next_iteration(), you will find that it terminates when UnknownCount == 17826.
True. These are the positions where neither side can force a mate, a stalemate, or a draw by material. Because neither side can mate, they are drawn, and the existing bitbase code already classifies these positions as drawn. You just add some rules that detect them as drawn from the beginning instead of letting the bitbase generation function detect them as drawn. It probably makes bitbase generation a tiny bit faster, but the generated bitbase will be 100% identical (unless there is some bug I cannot see).
Yes, these are likely drawn, but the bitbase code currently classify them as UNKNOWN, not drawn. Just dump the Bitbase[] array after generation and you can see that some values are still 0.

Kong Sian

Tord Romstad
Posts: 1808
Joined: Wed Mar 08, 2006 8:19 pm
Location: Oslo, Norway

Re: Stockfish bitbase

Post by Tord Romstad » Wed Jun 02, 2010 8:41 am

kongsian wrote:
Tord Romstad wrote:
kongsian wrote:Hi Tord. If you print out "UnknownCount" in next_iteration(), you will find that it terminates when UnknownCount == 17826.
True. These are the positions where neither side can force a mate, a stalemate, or a draw by material. Because neither side can mate, they are drawn, and the existing bitbase code already classifies these positions as drawn. You just add some rules that detect them as drawn from the beginning instead of letting the bitbase generation function detect them as drawn. It probably makes bitbase generation a tiny bit faster, but the generated bitbase will be 100% identical (unless there is some bug I cannot see).
Yes, these are likely drawn,
No, they are not likely drawn, they are proven to be drawn. That's the whole point of how the process of bitbase generation works. At the point where the number of unclassified positions doesn't change from one iteration to the next, all the remaining positions with a RESULT_UNKNOWN status must be drawn.
but the bitbase code currently classify them as UNKNOWN, not drawn. Just dump the Bitbase[] array after generation and you can see that some values are still 0.
Correct, but the Bitbase[] array is just something that is used temporarily while generating the bitbase. It is immediately discarded afterwards. The bitbase[] array (with a lowercase 'b') is the one that is used later on. In this array, the positions are compressed to a a single bit per position, where 1 represents a win for the side with the pawn and 0 represents a draw. The compression is done by this function, which is called after the bitbase generation is finished:

Code: Select all

  int compress_result&#40;Result r&#41; &#123;
    return &#40;r == RESULT_WIN || r == RESULT_LOSS&#41;? 1 &#58; 0;
  &#125;
As you can see, positions which are still RESULT_UNKNOWN will get a draw score, which is precisely what we want.

oysteijo

Re: Stockfish bitbase

Post by oysteijo » Wed Jun 02, 2010 8:52 am

I made a md4sum of KBKBitbase[] after compression with and without the suggested patch.

Without the patch:
MD5 Checksum for bitbases: d0a7a886d3f237b62c26e09409c3bf41

with the patch:
MD5 Checksum for bitbases: 5003c4ef8d60d67b19da63587f9ed74f

The patch does indeed make a difference!

-Øystein
from endgame.cpp:

Code: Select all

void init_bitbases&#40;) &#123;
  gchar *checksum;
  generate_kpk_bitbase&#40;KPKBitbase&#41;;
  checksum = g_compute_checksum_for_data&#40; G_CHECKSUM_MD5, KPKBitbase, 24576 * sizeof&#40; uint8_t ));
  printf&#40;"MD5 Checksum for bitbases&#58; %s\n", checksum );
  g_free&#40; checksum );
&#125;

Dann Corbit
Posts: 9894
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Stockfish bitbase

Post by Dann Corbit » Wed Jun 02, 2010 8:58 am

oysteijo wrote:I made a md4sum of KBKBitbase[] after compression with and without the suggested patch.

Without the patch:
MD5 Checksum for bitbases: d0a7a886d3f237b62c26e09409c3bf41

with the patch:
MD5 Checksum for bitbases: 5003c4ef8d60d67b19da63587f9ed74f

The patch does indeed make a difference!

-Øystein
from endgame.cpp:

Code: Select all

void init_bitbases&#40;) &#123;
  gchar *checksum;
  generate_kpk_bitbase&#40;KPKBitbase&#41;;
  checksum = g_compute_checksum_for_data&#40; G_CHECKSUM_MD5, KPKBitbase, 24576 * sizeof&#40; uint8_t ));
  printf&#40;"MD5 Checksum for bitbases&#58; %s\n", checksum );
  g_free&#40; checksum );
&#125;
Now the burning question is:
"Which one is correct?"

Tord Romstad
Posts: 1808
Joined: Wed Mar 08, 2006 8:19 pm
Location: Oslo, Norway

Re: Stockfish bitbase

Post by Tord Romstad » Wed Jun 02, 2010 9:05 am

oysteijo wrote:The patch does indeed make a difference!
That means that there could indeed be a bug somewhere. I'll have a look at it. Thanks to everyone for making me aware of this! :)

Post Reply