finding where pieces are in eval()?

Discussion of chess software programming and technical issues.

Moderator: Ras

jesper_nielsen

Re: finding where pieces are in eval()?

Post by jesper_nielsen »

My engine is a combined bitboard and "array of 64 squares".

I do not have a need to run through all pieces. I only need to run through all pieces of the same type.

So what I do is to have arrays of ints plus an int as index, telling me the last piece in the list, max_index.

I have a list per piece type: WhitePawn, BlackPawn, WhiteKnight, ... etc.

And in my board representation for a square, i have the index in the list the particular piece is located in.

So when i remove a piece from the board i do this:
1. Find the index of the list in my board representation
2. copy the last piece in the list to where the removed piece was.
3. Update the index of the square for the last piece to point to the new place in the list
4. subtract one from the max_index indicator for the list

And when i add a piece:
1. add the piece to the end of the list
2. update the board to point to this index
3. add one to the max_index indicator.

Finally, moving a piece:
1. update the board, so the to-square points to the same index as the from-square.
2. clear the index in the from-square

Hope you can follow the idea, even if i might have missed a step or two in the description! :D

Anyway, writing it down, is sounds kind of complicated?! :?

Maybe i could improve on this?

But there are plenty of bigger weaknesses in my engine to look at!

Kind regards,
Jesper
Top
Uri Blass
Posts: 10793
Joined: Thu Mar 09, 2006 12:37 am
Location: Tel-Aviv Israel

Re: finding where pieces are in eval()?

Post by Uri Blass »

<snipped>
hgm wrote:Bitscanning is quite slow: it neads multiple instructions to extract the square number of the next piece. For a piece list this is just a single memory load from the list.
I can only see that strelka is fast even in 32 bit system and it is using bit scanning both in the move generator and in the evaluation.

there are many loops like

for (mask_from = Board->mp[WhiteKnight]; mask_from != 0; mask_from &= (mask_from-1))

I guess the alternative is simply slower(at least if you want to evaluate patterns and strelka clearly evaluates patterns).

Uri
Top
Alessandro Scotti

Re: finding where pieces are in eval()?

Post by Alessandro Scotti »

hgm wrote:I got rid of the links when it turned out thet just slowed matters down. I had not expected this, but branch-prediction logic on modern CPUs is so good that it hardly hurts to put an "if(position[piece] < 0) continue;" everywhere you would like to to something with the piece.
Yes it's probably counter-intuitive sometimes, I guess one just has to prototype and measure! :-)

Or take a look at Fruit, Fabien knew all of this years ago! ;-)
Top
Guetti

Re: finding where pieces are in eval()?

Post by Guetti »

Uri Blass wrote:<snipped>
hgm wrote:Bitscanning is quite slow: it neads multiple instructions to extract the square number of the next piece. For a piece list this is just a single memory load from the list.
I can only see that strelka is fast even in 32 bit system and it is using bit scanning both in the move generator and in the evaluation.

there are many loops like

for (mask_from = Board->mp[WhiteKnight]; mask_from != 0; mask_from &= (mask_from-1))

I guess the alternative is simply slower(at least if you want to evaluate patterns and strelka clearly evaluates patterns).

Uri
There is another advantage of the bitcanning vs list approach. The list you have to update incrementally with every call to makemove(). The bitscanning in eval you might however be able to avoid im many positions by leaving eval early (lazy_eval).

I think that is the reason that makes it competitive.
Top
Dann Corbit
Posts: 12777
Joined: Wed Mar 08, 2006 8:57 pm
Location: Redmond, WA USA

Re: finding where pieces are in eval()?

Post by Dann Corbit »

Guetti wrote:
Dann Corbit wrote:
If you have bitboards, then you can find where your chessmen are by:
1. Make a copy of the bitboard of type <piece_type>
2. GetAndClearFirstBit() from your copy of the bitboard.
3. Repeat step 2 until the bitboard copy is empty.
I always thought Bitscanning is quite slow, so this would still be a time consuming operation, would it not?

- Andy
I guess that it is faster than maintianing a separate piece list.

Here are some bitscan functions:

Code: Select all

///////////////////////////////////////////////////////////////////////////////

#include <stdio.h>
#include <time.h>

///////////////////////////////////////////////////////////////////////////////

typedef unsigned long long Bitboard;

///////////////////////////////////////////////////////////////////////////////

// Each bitscan will run max*64 times

const int       max = 10000000;

////////////////////////////////////////////////////////////////////////////////

const Bitboard  mask[64] = {
    0x0000000000000001ULL, 0x0000000000000002ULL,
    0x0000000000000004ULL, 0x0000000000000008ULL,
    0x0000000000000010ULL, 0x0000000000000020ULL,
    0x0000000000000040ULL, 0x0000000000000080ULL,
    0x0000000000000100ULL, 0x0000000000000200ULL,
    0x0000000000000400ULL, 0x0000000000000800ULL,
    0x0000000000001000ULL, 0x0000000000002000ULL,
    0x0000000000004000ULL, 0x0000000000008000ULL,
    0x0000000000010000ULL, 0x0000000000020000ULL,
    0x0000000000040000ULL, 0x0000000000080000ULL,
    0x0000000000100000ULL, 0x0000000000200000ULL,
    0x0000000000400000ULL, 0x0000000000800000ULL,
    0x0000000001000000ULL, 0x0000000002000000ULL,
    0x0000000004000000ULL, 0x0000000008000000ULL,
    0x0000000010000000ULL, 0x0000000020000000ULL,
    0x0000000040000000ULL, 0x0000000080000000ULL,
    0x0000000100000000ULL, 0x0000000200000000ULL,
    0x0000000400000000ULL, 0x0000000800000000ULL,
    0x0000001000000000ULL, 0x0000002000000000ULL,
    0x0000004000000000ULL, 0x0000008000000000ULL,
    0x0000010000000000ULL, 0x0000020000000000ULL,
    0x0000040000000000ULL, 0x0000080000000000ULL,
    0x0000100000000000ULL, 0x0000200000000000ULL,
    0x0000400000000000ULL, 0x0000800000000000ULL,
    0x0001000000000000ULL, 0x0002000000000000ULL,
    0x0004000000000000ULL, 0x0008000000000000ULL,
    0x0010000000000000ULL, 0x0020000000000000ULL,
    0x0040000000000000ULL, 0x0080000000000000ULL,
    0x0100000000000000ULL, 0x0200000000000000ULL,
    0x0400000000000000ULL, 0x0800000000000000ULL,
    0x1000000000000000ULL, 0x2000000000000000ULL,
    0x4000000000000000ULL, 0x8000000000000000ULL,
};

Bitboard  smashableMask[64] = {
    0x0000000000000001ULL, 0x0000000000000002ULL,
    0x0000000000000004ULL, 0x0000000000000008ULL,
    0x0000000000000010ULL, 0x0000000000000020ULL,
    0x0000000000000040ULL, 0x0000000000000080ULL,
    0x0000000000000100ULL, 0x0000000000000200ULL,
    0x0000000000000400ULL, 0x0000000000000800ULL,
    0x0000000000001000ULL, 0x0000000000002000ULL,
    0x0000000000004000ULL, 0x0000000000008000ULL,
    0x0000000000010000ULL, 0x0000000000020000ULL,
    0x0000000000040000ULL, 0x0000000000080000ULL,
    0x0000000000100000ULL, 0x0000000000200000ULL,
    0x0000000000400000ULL, 0x0000000000800000ULL,
    0x0000000001000000ULL, 0x0000000002000000ULL,
    0x0000000004000000ULL, 0x0000000008000000ULL,
    0x0000000010000000ULL, 0x0000000020000000ULL,
    0x0000000040000000ULL, 0x0000000080000000ULL,
    0x0000000100000000ULL, 0x0000000200000000ULL,
    0x0000000400000000ULL, 0x0000000800000000ULL,
    0x0000001000000000ULL, 0x0000002000000000ULL,
    0x0000004000000000ULL, 0x0000008000000000ULL,
    0x0000010000000000ULL, 0x0000020000000000ULL,
    0x0000040000000000ULL, 0x0000080000000000ULL,
    0x0000100000000000ULL, 0x0000200000000000ULL,
    0x0000400000000000ULL, 0x0000800000000000ULL,
    0x0001000000000000ULL, 0x0002000000000000ULL,
    0x0004000000000000ULL, 0x0008000000000000ULL,
    0x0010000000000000ULL, 0x0020000000000000ULL,
    0x0040000000000000ULL, 0x0080000000000000ULL,
    0x0100000000000000ULL, 0x0200000000000000ULL,
    0x0400000000000000ULL, 0x0800000000000000ULL,
    0x1000000000000000ULL, 0x2000000000000000ULL,
    0x4000000000000000ULL, 0x8000000000000000ULL,
};


///////////////////////////////////////////////////////////////////////////////

const int       lsz64_tbl[64] =
{
    0, 31, 4, 33, 60, 15, 12, 34,
    61, 25, 51, 10, 56, 20, 22, 35,
    62, 30, 3, 54, 52, 24, 42, 19,
    57, 29, 2, 44, 47, 28, 1, 36,
    63, 32, 59, 5, 6, 50, 55, 7,
    16, 53, 13, 41, 8, 43, 46, 17,
    26, 58, 49, 14, 11, 40, 9, 45,
    21, 48, 39, 23, 18, 38, 37, 27,
};
//Gerd Isenberg's implementation of bitscan:
int             GerdBitScan(Bitboard bb)
{
    const Bitboard  lsb = (bb & -(long long) bb) - 1;
    const unsigned int foldedLSB = ((int) lsb) ^ ((int) (lsb >> 32));
    return lsz64_tbl[foldedLSB * 0x78291ACF >> 26];
}

//Gerd Isenberg's implementation of bitscan with clear:
int             GerdBitScanReset(Bitboard *bb)
{
    const Bitboard  lsb = (bb[0] & -(long long) bb[0]) - 1;
    const unsigned int foldedLSB = ((int) lsb) ^ ((int) (lsb >> 32));
    bb[0] &= (bb[0] - 1);
    return lsz64_tbl[foldedLSB * 0x78291ACF >> 26];
}

void            TestGerdBitscan()
{
    clock_t         start,
                    stop;
    int             count,
                    i;
    unsigned long   total = 0;

    start = clock();
    for (count = 0; count < max; count++) {
        for (i = 0; i < 64; i++) {
            total += GerdBitScan(mask[i]);
        }
    }
    stop = clock();
    printf("%15s %10u %.3f\n", "gerd", total, (float) (stop - start) / CLOCKS_PER_SEC);
}

unsigned int    bitScanReverse(Bitboard bb)
{
    union {
        double          d;
        struct {
				 unsigned int    mantissal:32;
				 unsigned int    mantissah:20;
				 unsigned int    exponent:11;
				 unsigned int    sign:1;
        };
    }   ud;
    ud.d = (double) (bb & ~(bb >> 32));
    return ud.exponent - 1023;
}

void            TestBitscanReverse()
{
    clock_t         start,
                    stop;
    int             count,
                    i;
    unsigned long   total = 0;

    start = clock();
    for (count = 0; count < max; count++) {
        for (i = 0; i < 64; i++) {
            total += bitScanReverse(mask[i]);
        }
    }
    stop = clock();
    printf("%15s %10u %.3f\n", "reverse", total, (float) (stop - start) / CLOCKS_PER_SEC);
}

////////////////////////////////////////////////////////////////////////////////

int             main()
{
    int i;
    
    TestGerdBitscan();
    TestGerdBitscan();
    TestGerdBitscan();
    TestGerdBitscan();
    printf("  ------------------------------\n");


    TestBitscanReverse();
    TestBitscanReverse();
    TestBitscanReverse();
    TestBitscanReverse();

    puts("Gerd+Reverse");    
    for (i = 0; i < 64; i++) {
        printf("%20llu, %4u, %4u\n", mask[i], GerdBitScan(mask[i]), bitScanReverse(mask[i]));
    }
    puts("Bitscan/reset");    
    for (i = 0; i < 64; i++) {
        
        printf("smashableMask[%d] before = %20llu\n",i, smashableMask[i]);
        printf("Bit number was %u\n", GerdBitScanReset(&smashableMask[i]));
        printf("smashableMask[%d] after = %20llu\n",i, smashableMask[i]);
    }

    return 0;
}
/*
           gerd 2980130816 2.750
           gerd 2980130816 2.750
           gerd 2980130816 2.750
           gerd 2980130816 3.531
  ------------------------------
        reverse 2980130816 15.141
        reverse 2980130816 14.985
        reverse 2980130816 14.969
        reverse 2980130816 14.922
Gerd+Reverse
                   1,    0,    0
                   2,    1,    1
                   4,    2,    2
                   8,    3,    3
                  16,    4,    4
                  32,    5,    5
                  64,    6,    6
                 128,    7,    7
                 256,    8,    8
                 512,    9,    9
                1024,   10,   10
                2048,   11,   11
                4096,   12,   12
                8192,   13,   13
               16384,   14,   14
               32768,   15,   15
               65536,   16,   16
              131072,   17,   17
              262144,   18,   18
              524288,   19,   19
             1048576,   20,   20
             2097152,   21,   21
             4194304,   22,   22
             8388608,   23,   23
            16777216,   24,   24
            33554432,   25,   25
            67108864,   26,   26
           134217728,   27,   27
           268435456,   28,   28
           536870912,   29,   29
          1073741824,   30,   30
          2147483648,   31,   31
          4294967296,   32,   32
          8589934592,   33,   33
         17179869184,   34,   34
         34359738368,   35,   35
         68719476736,   36,   36
        137438953472,   37,   37
        274877906944,   38,   38
        549755813888,   39,   39
       1099511627776,   40,   40
       2199023255552,   41,   41
       4398046511104,   42,   42
       8796093022208,   43,   43
      17592186044416,   44,   44
      35184372088832,   45,   45
      70368744177664,   46,   46
     140737488355328,   47,   47
     281474976710656,   48,   48
     562949953421312,   49,   49
    1125899906842624,   50,   50
    2251799813685248,   51,   51
    4503599627370496,   52,   52
    9007199254740992,   53,   53
   18014398509481984,   54,   54
   36028797018963968,   55,   55
   72057594037927936,   56,   56
  144115188075855872,   57,   57
  288230376151711744,   58,   58
  576460752303423488,   59,   59
 1152921504606846976,   60,   60
 2305843009213693952,   61,   61
 4611686018427387904,   62,   62
 9223372036854775808,   63,   63
Bitscan/reset
smashableMask[0] before =                    1
Bit number was 0
smashableMask[0] after =                    0
smashableMask[1] before =                    2
Bit number was 1
smashableMask[1] after =                    0
smashableMask[2] before =                    4
Bit number was 2
smashableMask[2] after =                    0
smashableMask[3] before =                    8
Bit number was 3
smashableMask[3] after =                    0
smashableMask[4] before =                   16
Bit number was 4
smashableMask[4] after =                    0
smashableMask[5] before =                   32
Bit number was 5
smashableMask[5] after =                    0
smashableMask[6] before =                   64
Bit number was 6
smashableMask[6] after =                    0
smashableMask[7] before =                  128
Bit number was 7
smashableMask[7] after =                    0
smashableMask[8] before =                  256
Bit number was 8
smashableMask[8] after =                    0
smashableMask[9] before =                  512
Bit number was 9
smashableMask[9] after =                    0
smashableMask[10] before =                 1024
Bit number was 10
smashableMask[10] after =                    0
smashableMask[11] before =                 2048
Bit number was 11
smashableMask[11] after =                    0
smashableMask[12] before =                 4096
Bit number was 12
smashableMask[12] after =                    0
smashableMask[13] before =                 8192
Bit number was 13
smashableMask[13] after =                    0
smashableMask[14] before =                16384
Bit number was 14
smashableMask[14] after =                    0
smashableMask[15] before =                32768
Bit number was 15
smashableMask[15] after =                    0
smashableMask[16] before =                65536
Bit number was 16
smashableMask[16] after =                    0
smashableMask[17] before =               131072
Bit number was 17
smashableMask[17] after =                    0
smashableMask[18] before =               262144
Bit number was 18
smashableMask[18] after =                    0
smashableMask[19] before =               524288
Bit number was 19
smashableMask[19] after =                    0
smashableMask[20] before =              1048576
Bit number was 20
smashableMask[20] after =                    0
smashableMask[21] before =              2097152
Bit number was 21
smashableMask[21] after =                    0
smashableMask[22] before =              4194304
Bit number was 22
smashableMask[22] after =                    0
smashableMask[23] before =              8388608
Bit number was 23
smashableMask[23] after =                    0
smashableMask[24] before =             16777216
Bit number was 24
smashableMask[24] after =                    0
smashableMask[25] before =             33554432
Bit number was 25
smashableMask[25] after =                    0
smashableMask[26] before =             67108864
Bit number was 26
smashableMask[26] after =                    0
smashableMask[27] before =            134217728
Bit number was 27
smashableMask[27] after =                    0
smashableMask[28] before =            268435456
Bit number was 28
smashableMask[28] after =                    0
smashableMask[29] before =            536870912
Bit number was 29
smashableMask[29] after =                    0
smashableMask[30] before =           1073741824
Bit number was 30
smashableMask[30] after =                    0
smashableMask[31] before =           2147483648
Bit number was 31
smashableMask[31] after =                    0
smashableMask[32] before =           4294967296
Bit number was 32
smashableMask[32] after =                    0
smashableMask[33] before =           8589934592
Bit number was 33
smashableMask[33] after =                    0
smashableMask[34] before =          17179869184
Bit number was 34
smashableMask[34] after =                    0
smashableMask[35] before =          34359738368
Bit number was 35
smashableMask[35] after =                    0
smashableMask[36] before =          68719476736
Bit number was 36
smashableMask[36] after =                    0
smashableMask[37] before =         137438953472
Bit number was 37
smashableMask[37] after =                    0
smashableMask[38] before =         274877906944
Bit number was 38
smashableMask[38] after =                    0
smashableMask[39] before =         549755813888
Bit number was 39
smashableMask[39] after =                    0
smashableMask[40] before =        1099511627776
Bit number was 40
smashableMask[40] after =                    0
smashableMask[41] before =        2199023255552
Bit number was 41
smashableMask[41] after =                    0
smashableMask[42] before =        4398046511104
Bit number was 42
smashableMask[42] after =                    0
smashableMask[43] before =        8796093022208
Bit number was 43
smashableMask[43] after =                    0
smashableMask[44] before =       17592186044416
Bit number was 44
smashableMask[44] after =                    0
smashableMask[45] before =       35184372088832
Bit number was 45
smashableMask[45] after =                    0
smashableMask[46] before =       70368744177664
Bit number was 46
smashableMask[46] after =                    0
smashableMask[47] before =      140737488355328
Bit number was 47
smashableMask[47] after =                    0
smashableMask[48] before =      281474976710656
Bit number was 48
smashableMask[48] after =                    0
smashableMask[49] before =      562949953421312
Bit number was 49
smashableMask[49] after =                    0
smashableMask[50] before =     1125899906842624
Bit number was 50
smashableMask[50] after =                    0
smashableMask[51] before =     2251799813685248
Bit number was 51
smashableMask[51] after =                    0
smashableMask[52] before =     4503599627370496
Bit number was 52
smashableMask[52] after =                    0
smashableMask[53] before =     9007199254740992
Bit number was 53
smashableMask[53] after =                    0
smashableMask[54] before =    18014398509481984
Bit number was 54
smashableMask[54] after =                    0
smashableMask[55] before =    36028797018963968
Bit number was 55
smashableMask[55] after =                    0
smashableMask[56] before =    72057594037927936
Bit number was 56
smashableMask[56] after =                    0
smashableMask[57] before =   144115188075855872
Bit number was 57
smashableMask[57] after =                    0
smashableMask[58] before =   288230376151711744
Bit number was 58
smashableMask[58] after =                    0
smashableMask[59] before =   576460752303423488
Bit number was 59
smashableMask[59] after =                    0
smashableMask[60] before =  1152921504606846976
Bit number was 60
smashableMask[60] after =                    0
smashableMask[61] before =  2305843009213693952
Bit number was 61
smashableMask[61] after =                    0
smashableMask[62] before =  4611686018427387904
Bit number was 62
smashableMask[62] after =                    0
smashableMask[63] before =  9223372036854775808
Bit number was 63
smashableMask[63] after =                    0
*/
Top
cyberfish

Re: finding where pieces are in eval()?

Post by cyberfish »

Thanks for the suggestions!
Since my program already uses bitscan for move generation, I guess I will just use it too for eval. I was reluctant to do this because I imagined bitscanning to be a quite expensive function. However, Dann Corbit's post showed me that apparently it's A LOT simpler than what I imagined.
Top
Gerd Isenberg
Posts: 2251
Joined: Wed Mar 08, 2006 8:47 pm
Location: Hattingen, Germany

Re: finding where pieces are in eval()?

Post by Gerd Isenberg »

Dann Corbit wrote: I guess that it is faster than maintianing a separate piece list.

Here are some bitscan functions:

Code: Select all

//Gerd Isenberg's implementation of bitscan:
int             GerdBitScan(Bitboard bb)
{
    const Bitboard  lsb = (bb & -(long long) bb) - 1;
    const unsigned int foldedLSB = ((int) lsb) ^ ((int) (lsb >> 32));
    return lsz64_tbl[foldedLSB * 0x78291ACF >> 26];
}

//Gerd Isenberg's implementation of bitscan with clear:
int             GerdBitScanReset(Bitboard *bb)
{
    const Bitboard  lsb = (bb[0] & -(long long) bb[0]) - 1;
    const unsigned int foldedLSB = ((int) lsb) ^ ((int) (lsb >> 32));
    bb[0] &= (bb[0] - 1);
    return lsz64_tbl[foldedLSB * 0x78291ACF >> 26];
}
The folded De Bruijn routines were invented are by Matt Taylor - not by me. See the chess programming wiki:
http://chessprogramming.wikispaces.com/BitScan
http://chessprogramming.wikispaces.com/ ... ialization

Gerd
Top

Return to “Computer Chess Club: Programming and Technical Discussions”