Shift and Address included into Magic number

Discussion of chess software programming and technical issues.

Moderators: hgm, Rebel, chrisw

User avatar
Kotlov
Posts: 266
Joined: Fri Jul 10, 2015 9:23 pm
Location: Russia

Shift and Address included into Magic number

Post by Kotlov »

Code: Select all

const U64 r_magic[64]=
{
    0xd1800040008053ea,0xd48020004000f383,0xd700084020013500,0xd600084022007292,
    0xd500080003009331,0xd600020008049b50,0xd50001000400fa00,0xd10000810000d3e6,
    0xd64c80004000a39b,0xda03004000806f01,0xd802001022004b80,0xd802001020408e00,
    0xd81880430a087ffe,0xd82900080c00ab00,0xd844000d6802afb4,0xd60200006ce6b3f6,
    0xd44000800064bbde,0xd8200040100067c3,0xd820008010006b81,0xd84202001020c3f8,
    0xd9600e000a00c6e0,0xd862008004008680,0xd80144000208e310,0xd4080200038303f4,
    0xd400800100210bc1,0xd8201000400027c7,0xd820010100102bc0,0xd803402a000ee600,
    0xd94a003a00128aa0,0xdb0400808004ea00,0xda008dac0002ef58,0xd40100010000cbb2,
    0xd4008040008014e0,0xd810002000400fcc,0xd810080020200403,0xd805001001001ffd,
    0xda9300a801002ffd,0xd802001400804e80,0xd802000802007b7c,0xd6e7000081003bc2,
    0xd7ffe7fed9fe300b,0xd806010080420064,0xd8a0020400301001,0xd850008100080800,
    0xdafffdfefff02020,0xdbffffbe5fde6008,0xd812408002008100,0xd7ffffdbeb7a4012,
    0xd5fffa7fffdf43f0,0xdbfffbf7ffd323f0,0xdbffffeea7ff27e0,0xdb9ffdbfcbdb2be0,
    0xdb3fff9f6feb2fe0,0xdbffff3bdffd33e0,0xdaefffdfbf733fe0,0xd65fffffbeff4bf0,
    0xd3ffffd77fff13ef,0xd44e8100400163f9,0xd7ffffdfffbf6bf7,0xd7ffff9dffbf73fa,
    0xd7ffffd7ffaf7bfd,0xd7cffffefff783ff,0xd77fffff77ed8bfd,0xd3228785022553fe
};

const U64 b_magic[64]=
{
    0xe858a9ebe999f09f,0xec1090011101ecdf,0xec0848030061ecff,0xed2806004041ed1f,
    0xec0403084001ed3f,0xec05040a4001ed5f,0xee011808040ded7f,0xe885040100a9f0df,
    0xee2840020d05eabf,0xec0a021c1801eadf,0xec2028080101ed9f,0xec8251050201edbf,
    0xed0404102801eddf,0xec0082080405edff,0xec860094515bee1f,0xee8d088c0145ee3f,
    0xec2005684215ea7f,0xed1404878489eaff,0xe428033000cff21b,0xe42401180141f29f,
    0xe7eefeb7eebff31f,0xe4226092d015ebb2,0xee0092040245ee5f,0xec820009b201ee7f,
    0xef7840035911ee9f,0xed100a4c7041ea5f,0xe50370004483f380,0xde04080004012410,
    0xdc02040002018213,0xe40802000991b41f,0xecae008001dfef1f,0xee04e20642c1ea3f,
    0xec65a0300c89ef3f,0xed4c0c8c06c7ef5f,0xe463080802750b3f,0xde12200800010811,
    0xdc3006020011e018,0xe592411200010782,0xec0a1a120803ea97,0xed7df1f23a85eebf,
    0xec1108084001eedf,0xee0402121001eeff,0xe402004a0801e69c,0xe69816012401e60a,
    0xe42010020201f194,0xe7bfb7e7fb5dec3f,0xeca0180102c1e71f,0xee180b21a185ea1f,
    0xec0108080209ef7f,0xec1104018443ef9f,0xec8520e18831efbf,0xee572ca9f5fdefdf,
    0xec00a06aa303efff,0xec0418100c81f01f,0xec4004082201f03f,0xec0850010601f05f,
    0xeb0104010495f11f,0xec0500440181f07f,0xedd27463f5b7ecbf,0xef48054001e40727,
    0xeea3d65ffdd74753,0xec9c7e9c4dc1e77f,0xec0060600e03eb1f,0xe9900c100401f15f
};
This number that I generate include both table data as shift and address.
Shift = magic >> 58
Address for rook = magic & 0x000000000001fc00ull
Address for bishop = magic & 0x0000000000001fe0ull

Part of my engine uses this:

Code: Select all

const U64 r_magic[64]=
{
    0xd1800040008053ea,0xd48020004000f383,0xd700084020013500,0xd600084022007292,
    0xd500080003009331,0xd600020008049b50,0xd50001000400fa00,0xd10000810000d3e6,
    0xd64c80004000a39b,0xda03004000806f01,0xd802001022004b80,0xd802001020408e00,
    0xd81880430a087ffe,0xd82900080c00ab00,0xd844000d6802afb4,0xd60200006ce6b3f6,
    0xd44000800064bbde,0xd8200040100067c3,0xd820008010006b81,0xd84202001020c3f8,
    0xd9600e000a00c6e0,0xd862008004008680,0xd80144000208e310,0xd4080200038303f4,
    0xd400800100210bc1,0xd8201000400027c7,0xd820010100102bc0,0xd803402a000ee600,
    0xd94a003a00128aa0,0xdb0400808004ea00,0xda008dac0002ef58,0xd40100010000cbb2,
    0xd4008040008014e0,0xd810002000400fcc,0xd810080020200403,0xd805001001001ffd,
    0xda9300a801002ffd,0xd802001400804e80,0xd802000802007b7c,0xd6e7000081003bc2,
    0xd7ffe7fed9fe300b,0xd806010080420064,0xd8a0020400301001,0xd850008100080800,
    0xdafffdfefff02020,0xdbffffbe5fde6008,0xd812408002008100,0xd7ffffdbeb7a4012,
    0xd5fffa7fffdf43f0,0xdbfffbf7ffd323f0,0xdbffffeea7ff27e0,0xdb9ffdbfcbdb2be0,
    0xdb3fff9f6feb2fe0,0xdbffff3bdffd33e0,0xdaefffdfbf733fe0,0xd65fffffbeff4bf0,
    0xd3ffffd77fff13ef,0xd44e8100400163f9,0xd7ffffdfffbf6bf7,0xd7ffff9dffbf73fa,
    0xd7ffffd7ffaf7bfd,0xd7cffffefff783ff,0xd77fffff77ed8bfd,0xd3228785022553fe
};

const U64 b_magic[64]=
{
    0xe858a9ebe999f09f,0xec1090011101ecdf,0xec0848030061ecff,0xed2806004041ed1f,
    0xec0403084001ed3f,0xec05040a4001ed5f,0xee011808040ded7f,0xe885040100a9f0df,
    0xee2840020d05eabf,0xec0a021c1801eadf,0xec2028080101ed9f,0xec8251050201edbf,
    0xed0404102801eddf,0xec0082080405edff,0xec860094515bee1f,0xee8d088c0145ee3f,
    0xec2005684215ea7f,0xed1404878489eaff,0xe428033000cff21b,0xe42401180141f29f,
    0xe7eefeb7eebff31f,0xe4226092d015ebb2,0xee0092040245ee5f,0xec820009b201ee7f,
    0xef7840035911ee9f,0xed100a4c7041ea5f,0xe50370004483f380,0xde04080004012410,
    0xdc02040002018213,0xe40802000991b41f,0xecae008001dfef1f,0xee04e20642c1ea3f,
    0xec65a0300c89ef3f,0xed4c0c8c06c7ef5f,0xe463080802750b3f,0xde12200800010811,
    0xdc3006020011e018,0xe592411200010782,0xec0a1a120803ea97,0xed7df1f23a85eebf,
    0xec1108084001eedf,0xee0402121001eeff,0xe402004a0801e69c,0xe69816012401e60a,
    0xe42010020201f194,0xe7bfb7e7fb5dec3f,0xeca0180102c1e71f,0xee180b21a185ea1f,
    0xec0108080209ef7f,0xec1104018443ef9f,0xec8520e18831efbf,0xee572ca9f5fdefdf,
    0xec00a06aa303efff,0xec0418100c81f01f,0xec4004082201f03f,0xec0850010601f05f,
    0xeb0104010495f11f,0xec0500440181f07f,0xedd27463f5b7ecbf,0xef48054001e40727,
    0xeea3d65ffdd74753,0xec9c7e9c4dc1e77f,0xec0060600e03eb1f,0xe9900c100401f15f
};

BB bat[5248];
BB rat[102400];
bb64 bm;
bb64 rm;

#define R_ADDR_MASK 0x000000000001fc00ull
#define B_ADDR_MASK 0x0000000000001fe0ull
#define R_MAGIC_ADDR (magic&R_ADDR_MASK)
#define B_MAGIC_ADDR (magic&B_ADDR_MASK)
#define SHIFT_CONST 58
#define MAGIC_SHIFT (magic>>SHIFT_CONST)
#define MAGIC_OFFSET ((occ*magic)>>MAGIC_SHIFT)

BB grm(int sq,BB a)
{
    a^=xx[sq];
    return((file_m[7]>>63-LB(*file_m<<sq&(a|rank_m[7]))&*file_m<<MB(file_m[7]>>63-sq&(a|*rank_m)))|
           (rank_m[7]>>63-LB(*rank_m<<sq&(a|file_m[7]))&*rank_m<<MB(rank_m[7]>>63-sq&(a|*file_m))))^xx[sq];
}

BB gbm(int sq,BB a)
{
    a^=xx[sq];
    BB x=diag_m[7]|*xx|xx[63];
    return(((diag_m[23]>>63-LB(diag_m[23]<<sq&(a|file_m[7]|rank_m[7])))&(diag_m[23]<<MB(diag_m[23]>>63-sq&(a|*file_m|*rank_m))))|
           ((x>>63-LB(x<<sq&(a|*file_m|rank_m[7])))&(x<<MB(x>>63-sq&(a|file_m[7]|*rank_m)))))^xx[sq];
}

BB index64(int index,int num_bits,BB mask)
{
    BB result=0ull;
    for(int i=num_bits; i--;)
        {
            int s=EJECT(mask);
            if(index&xx[i])result|=xx[s];
        }
    return result;
}

void write_att(int sq,int is_bishop)
{
    BB magic=is_bishop?b_magic[sq]:r_magic[sq];
    for(int i=xx[64-MAGIC_SHIFT]; i--;)
        {
            BB bb=index64(i,64-MAGIC_SHIFT,is_bishop?bm[sq]:rm[sq]);
            BB offset=bb*magic>>MAGIC_SHIFT;
            if(is_bishop)
                bat[B_MAGIC_ADDR+offset]=gbm(sq,xx[sq]|bb);
            else
                rat[R_MAGIC_ADDR+offset]=grm(sq,xx[sq]|bb);
        }
}

void init_magic()
{
    memset(bat,0,sizeof(bat));
    memset(rat,0,sizeof(rat));
    for(int i=64; i--;)
        {
            BB z=0x007E7E7E7E7E7E00ull;
            z|=xx[i]&rank_m[7]?rank_m[7]:0ull;
            z|=xx[i]&rank_m[0]?rank_m[0]:0ull;
            z|=xx[i]&file_m[7]?file_m[7]:0ull;
            z|=xx[i]&file_m[0]?file_m[0]:0ull;
            rm[i]=rook_m[i]&z&0x7EFFFFFFFFFFFF7Eull;
            bm[i]=bishop_m[i]&z;
            write_att(i,0);
            write_att(i,1);
        }
}

BB r_attacks(int sq,BB occ)
{
    BB magic=r_magic[sq];
    occ&=rm[sq];
    return rat[R_MAGIC_ADDR+MAGIC_OFFSET];
}

BB b_attacks(int sq,BB occ)
{
    BB magic=b_magic[sq];
    occ&=bm[sq];
    return bat[B_MAGIC_ADDR+MAGIC_OFFSET];
}

BB q_attacks(int sq,BB occ)
{
    return r_attacks(sq,occ)|b_attacks(sq,occ);
}

#define ROOK_ATTACKS r_attacks
#define BISHOP_ATTACKS b_attacks
#define QUEEN_ATTACKS q_attacks
Eugene Kotlov
Hedgehog 2.1 64-bit coming soon...
Top
Gerd Isenberg
Posts: 2250
Joined: Wed Mar 08, 2006 8:47 pm
Location: Hattingen, Germany

Re: Shift and Address included into Magic number

Post by Gerd Isenberg »

Is this faster than your fixed shift approach introduced one year ago?

http://www.talkchess.com/forum3/viewtopic.php?t=66538
Top
User avatar
Kotlov
Posts: 266
Joined: Fri Jul 10, 2015 9:23 pm
Location: Russia

Re: Shift and Address included into Magic number

Post by Kotlov »

Gerd Isenberg wrote: ↑Tue Feb 19, 2019 9:46 pm Is this faster than your fixed shift approach introduced one year ago?

http://www.talkchess.com/forum3/viewtopic.php?t=66538
Hi, Gerd.
The only thing for sure is not slower. To be more precise, more tests are needed to select computational functions for a specific compiler. Ideally, an assembler is needed. By this I wanted to get rid of the additional two tables - shifts and addresses. There is no need to load the cache.
Eugene Kotlov
Hedgehog 2.1 64-bit coming soon...
Top
User avatar
Kotlov
Posts: 266
Joined: Fri Jul 10, 2015 9:23 pm
Location: Russia

Re: Shift and Address included into Magic number

Post by Kotlov »

OK, I did the necessary tests and I can say that I registered a 2% speed increase.

test position
[d]1k1q4/6Q1/2q5/7Q/1q6/4Q3/q7/5QK1 w - - 0 1
Eugene Kotlov
Hedgehog 2.1 64-bit coming soon...
Top
User avatar
Kotlov
Posts: 266
Joined: Fri Jul 10, 2015 9:23 pm
Location: Russia

Re: Shift and Address included into Magic number

Post by Kotlov »

Next step:
Try found magic numbers including offset(address realy) with fixed shift.
Eugene Kotlov
Hedgehog 2.1 64-bit coming soon...
Top

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