Poor Man Table Base

[Rebel]

I am in the process of classifying sensible endgames and so far I have identified 62. I like to share its source code as freeware in the hope to receive some feedback. The package is available for download at: http://www.top-5000.nl/PMTB.zip

Shortened version:

Code: Select all

/*********************************************************************************
 ***         Poor Man Table Base - End Game Classification                     ***
 ***                                                                           ***
 ***         Step-1  :   Read classification file "class.mat" into the         ***
 ***                     end_class table                                       ***
 ***                                                                           ***
 ***         Step-2  :   In EVAL fill the 10 material parameters with the      ***
 ***                     numbers matching the position and call the            ***
 ***                     end_class table.                                      ***
 ***                                                                           ***
 ***                     The example KBN_K should return 15                    ***
 *********************************************************************************/

static char end_class [9][9] [3][3] [3][3] [3][3] [2][2];
static int wp,wn,wb,wr,wq,bp,bn,bb,br,bq;
static int category;
FILE *fp;

void main()

/*********************************************************************************
 ***                                                                           ***
 ***                    Initialization at program start                        ***
 ***                                                                           ***
 *********************************************************************************/

{       fp = fopen("class.mat","rb");
        if (fp==NULL) { fclose(fp); printf("File CLASS.MAT not present"); exit (0); }

        for &#40;wp=0; wp<=8; wp++)             // read predefined classifications
        for &#40;bp=0; bp<=8; bp++)             // into the "end_class" table
        for &#40;wn=0; wn<=2; wn++)
        for &#40;bn=0; bn<=2; bn++)
        for &#40;wb=0; wb<=2; wb++)
        for &#40;bb=0; bb<=2; bb++)
        for &#40;wr=0; wr<=2; wr++)
        for &#40;br=0; br<=2; br++)
        for &#40;wq=0; wq<=1; wq++)
        for &#40;bq=0; bq<=1; bq++)
         fread&#40;&end_class &#91;wp&#93;&#91;bp&#93; &#91;wn&#93;&#91;bn&#93; &#91;wb&#93;&#91;bb&#93; &#91;wr&#93;&#91;br&#93; &#91;wq&#93;&#91;bq&#93;,1,1,fp&#41;;

        fclose&#40;fp&#41;;

/*********************************************************************************
 ***                                                                           ***
 ***                                In EVAL                                    ***
 ***                                                                           ***
 ***                Example Bishop + Knight vs lonely black King               ***
 ***                                                                           ***
 *********************************************************************************/

        wp=0; bp=0; wn=1; bn=0; wb=1; bb=0; wr=0; br=0; wq=0; bq=0;

        category = end_class &#91;wp&#93;&#91;bp&#93; &#91;wn&#93;&#91;bn&#93; &#91;wb&#93;&#91;bb&#93; &#91;wr&#93;&#91;br&#93; &#91;wq&#93;&#91;bq&#93;;

        switch &#40;category&#41;

         &#123; case  0  &#58; goto normal;          // no endgame class for this position

           case  1  &#58; goto Kp_Kp;           // pawn ending multiple (>=2&#41; pawns &#40;W/B&#41;

           case  2  &#58; goto Kp_K;            // Kp vs K
           case  3  &#58; goto K_Kp;            // K  vs Kp

           case  4  &#58; goto KN_Kpp;          // lone WN vs multiple (>=2&#41; black pawns
           case  5  &#58; goto Kpp_KN;          // lone BN vs multiple (>=2&#41; white pawns

           case  6  &#58; goto KB_Kpp;          // lone WB vs multiple (>=2&#41; black pawns
           case  7  &#58; goto Kpp_KB;          // lone BN vs multiple (>=2&#41; white pawns

............

           case  61 &#58; goto KBx_KBx;         // bishop ending with pawns &#40;check for unequal bishops&#41;

           case  62 &#58; goto K_K;             // K vs K &#40;draw&#41; almost forgot this one &#58;-)
           
           break; &#125;

Kp_Kp&#58;      goto normal;            // case 1   &#58;   pawn ending multiple (>=2&#41; pawns &#40;W/B&#41;

Kp_K&#58;       goto normal;            // case 2   &#58;   Kp vs K
K_Kp&#58;       goto normal;            // case 3   &#58;   K  vs Kp

KN_Kpp&#58;     goto normal;            // case 4   &#58;   lone WN vs multiple (>=2&#41; black pawns
Kpp_KN&#58;     goto normal;            // case 5   &#58;   lone BN vs multiple (>=2&#41; white pawns

KB_Kpp&#58;     goto normal;            // case 6   &#58;   lone WB vs multiple (>=2&#41; black pawns
Kpp_KB&#58;     goto normal;            // case 7   &#58;   lone BB vs multiple (>=2&#41; white pawns

...............

normal&#58;                             // case 0   &#58;   No endgame class for this position

            return;
&#125;



/*********************************************************************************
 ***         Poor Man Table Base - End Game Classification                     ***
 ***                                                                           ***
 ***                             Remarks                                       ***
 ***                                                                           ***
 ***      1. Make sure the table parameters &#40;wp,wn....bq&#41; don't cross          ***
 ***         their limits, a false result or a crash will the result.          ***
 ***                                                                           ***
 ***      2. The chosen numerology together with the use of SWITCH - CASE      ***
 ***         has the advantage the compiler will lump all the &#40;current&#41; 62     ***
 ***         classifications into a so called jump-table and thus not 62       ***
 ***         instructions but only one is executed via an indirect jump.       ***
 ***                                                                           ***
 ***         This makes the code real fast and justifies a call to a 10        ***
 ***         dimensional table.                                                ***
 ***                                                                           ***
 ***         Its ASM beauty&#58;                                                   ***
 ***                                                                           ***
 ***         mov     ESI,dword ptr category   // load the found table entry    ***
 ***         jmp     DATA&#91;038h&#93;&#91;ESI*4&#93;        // and jump to right place       ***
 ***                                                                           ***
 ***                                                                           ***
 ***      3. The file CLASS.MAT is included in the download and is generated   ***
 ***         by an utility which will be released later when the full          ***
 ***         classification process is finished. You then can organize,        ***
 ***         extend the endgame classifications to your own liking.            ***
 ***                                                                           ***
 ***         For now I would like to hear your comments first before           ***
 ***         proceeding.                                                       ***
 ***                                                                           ***
 *********************************************************************************/

[sje]

While you will have a very quick switch dispatch, you will pay a high price on the category assignment:

Code: Select all

category = end_class [wp][bp] [wn][bn] [wb][bb] [wr][br] [wq][bq];

That will generate a lot of multiply, shift, and add instructions.

My way:

1) Include as part of the incrementally updated position database an 64 bit unsigned integer variable matsig. For an empty board, its initial value is zero.

2) When a man (value 0 through 11) is added to the board, increment matsig by (1ull << (man * 4)). A table indexed by man can help with speed.

3) When a man is removed from the board, decrement matsig by (1ull << (man * 4)).

4) Have an initialized key vector of unsigned 64 bit integers in order. Do a binary search on this vector with current value of matsig. Also include color reversed entry keys. The value of each key vector is a routine address for performing evaluation or tablebase probing. This can all be initialized without an external data file.

[bob]

While you will have a very quick switch dispatch, you will pay a high price on the category assignment:

Code: Select all

category = end_class [wp][bp] [wn][bn] [wb][bb] [wr][br] [wq][bq];

That will generate a lot of multiply, shift, and add instructions.

My way:

1) Include as part of the incrementally updated position database an 64 bit unsigned integer variable matsig. For an empty board, its initial value is zero.

2) When a man (value 0 through 11) is added to the board, increment matsig by (1ull << (man * 4)). A table indexed by man can help with speed.

3) When a man is removed from the board, decrement matsig by (1ull << (man * 4)).

4) Have an initialized key vector of unsigned 64 bit integers in order. Do a binary search on this vector with current value of matsig. Also include color reversed entry keys. The value of each key vector is a routine address for performing evaluation or tablebase probing. This can all be initialized without an external data file.

Other minor issue. You have a completely unpredictable jump. You know the jump is taken, but you have to predict to where it will go, which is an issue with preceding data dependencies....

It might well be faster using 62 conditional jumps that will be predicted correctly some of the time...

[sje]

Other minor issue. You have a completely unpredictable jump. You know the jump is taken, but you have to predict to where it will go, which is an issue with preceding data dependencies....

It might well be faster using 62 conditional jumps that will be predicted correctly some of the time...

Mostly the table will be probed only when the number of men on the board is six or less. At that point, only a few different material signatures will be seen, so any branch prediction should work fine. Also, the ordered material signature table for five men or less needs a maximum of nine probes in a binary search; adding a sixth man adds only two more probes to this (I think).

I have the material signature generation working in the newest BozoChess. This includes the incremental update but not the actual ordered lookup table. Also present in the endgame name generator.

Code: Select all

[] sfen 8/k7/3p4/p2P1p2/P2P1P2/8/8/K7 w - - 0 1
[] dmsig
Material signature: KPPPPKPPP
[] sfen 4k3/8/8/8/8/8/4P3/4K3 w - - 0 1
[] dmsig
Material signature: KPK
[] new
[] dmsig
Material signature: KQRRBBNNPPPPPPPPKQRRBBNNPPPPPPPP

[hgm]

In Spartacus I update the index of the material table incrementally. No need for binary search.

[Rebel]

While you will have a very quick switch dispatch, you will pay a high price on the category assignment:

Code: Select all

category = end_class [wp][bp] [wn][bn] [wb][bb] [wr][br] [wq][bq];

That will generate a lot of multiply, shift, and add instructions.

I checked the ASM output, it's not so bad. I did not notice a drop in NPS also.

[sje]

In Spartacus I update the index of the material table incrementally. No need for binary search.

Hashing will also work; I believe Chess 4.x used such for its material evaluation. It would possible to implement incremental Zobrist updating, too.

The binary signature table search, with its seven or so probes, isn't actually called that much; perhaps only when the total man count is six or less. And if a system call is needed to probe a tablebase, then the binary search becomes very, very fast in comparison.

[hgm]

Fruit uses hashing for the material table. But why emulate in software what the cache hardware already does? Array indexing could be considered perfect hashing.

[sje]

While you will have a very quick switch dispatch, you will pay a high price on the category assignment:

Code: Select all

category = end_class [wp][bp] [wn][bn] [wb][bb] [wr][br] [wq][bq];

That will generate a lot of multiply, shift, and add instructions.

I checked the ASM output, it's not so bad. I did not notice a drop in NPS also.

Perhaps, but what happens if one side has two queens? Your code will have to check the validity of EIGHT (w/b * q/r/b/n) bounds for safety before fetching from the table.

And that table already has 236,196 elements; increasing the subscript bounds will make it even bigger. By contrast, my scheme with the signature binary probe will require less than 512 entries for 2-5 man classes including color reversal. So, nine probes with an average of seven. No external table and no subscript checking.

I hope to have this coded in Bozo for the next release in a week or so.

Already Bozo has a couple of binary search functions on ASCII ordered tables. Here's the one it use to identify a user command verb:

Code: Select all

    function MatchIcpCommand(str: String): icpcxtype;
      var
        myresult: icpcxtype;
        b0, b1, probe: Integer;
    begin
      myresult := icpcnil;
      b0 := 0;
      b1 := icpclen - 1;
      repeat
        probe := (b0 + b1) div 2;
        if str = icpcnames[probe] then
          myresult := icpctype(probe)
        else
          if str < icpcnames&#91;probe&#93; then
            b1 &#58;= probe - 1
          else
            b0 &#58;= probe + 1
      until &#40;myresult <> icpcnil&#41; or &#40;b0 > b1&#41;;
      MatchIcpCommand &#58;= myresult
    end; &#123; MatchIcpCommand &#125;

[Rebel]

While you will have a very quick switch dispatch, you will pay a high price on the category assignment:

Code: Select all

category = end_class [wp][bp] [wn][bn] [wb][bb] [wr][br] [wq][bq];

That will generate a lot of multiply, shift, and add instructions.

I checked the ASM output, it's not so bad. I did not notice a drop in NPS also.

Perhaps, but what happens if one side has two queens? Your code will have to check the validity of EIGHT (w/b * q/r/b/n) bounds for safety before fetching from the table.

Yep, but 2 queens, 3 rooks, 4 knights etc. simply falls outside the scope of a simple poor man table base concept.

Besides, I use the system as a material imbalance table as well, in EVAL I add a pre-calculated bonus to score via a second table lookup.

Code: Select all

score+= material_bonus [wp][bp] [wn][bn] [wb][bb] [wr][br] [wq][bq];