very small bitboard move/attack generator

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
xr_a_y
Posts: 733
Joined: Sat Nov 25, 2017 1:28 pm
Location: France

very small bitboard move/attack generator

Post by xr_a_y » Sat Oct 27, 2018 4:55 pm

I'd like to test a bitboard approach in Minic for both move generation, attack detection and to get some useful tools to add some evaluation features easily. But what I found in other engines are very "lines of code consuming" implementations. Does someone can point me a small and easy to implement bitboard approach ?

smatovic
Posts: 833
Joined: Wed Mar 10, 2010 9:18 pm
Location: Hamburg, Germany
Full name: Srdja Matovic
Contact:

Re: very small bitboard move/attack generator

Post by smatovic » Sat Oct 27, 2018 7:30 pm

xr_a_y wrote:
Sat Oct 27, 2018 4:55 pm
I'd like to test a bitboard approach in Minic for both move generation, attack detection and to get some useful tools to add some evaluation features easily. But what I found in other engines are very "lines of code consuming" implementations. Does someone can point me a small and easy to implement bitboard approach ?
https://www.chessprogramming.org/Dumb7F ... ed_Attacks

--
Srdja

User avatar
xr_a_y
Posts: 733
Joined: Sat Nov 25, 2017 1:28 pm
Location: France

Re: very small bitboard move/attack generator

Post by xr_a_y » Mon Oct 29, 2018 4:28 pm

Thanks.

A very good resource : https://github.com/ZirconiumX/bbattack

User avatar
Desperado
Posts: 638
Joined: Mon Dec 15, 2008 10:45 am

Re: very small bitboard move/attack generator

Post by Desperado » Mon Oct 29, 2018 7:57 pm

// simple direct computations for sliders (unify bishop and rook for queen attacks)

Code: Select all

uint64_t Eng::gen_b_attack(int s, uint64_t o)
{
    uint64_t tmp, att = 0;
    remove_bit(&o,s);
    tmp = Setbit64(s);
    while(False(tmp & (o | BB_HF | BB_R8))) att |= tmp <<= 9;
    tmp = Setbit64(s);
    while(False(tmp & (o | BB_AF | BB_R8))) att |= tmp <<= 7;
    tmp = Setbit64(s);
    while(False(tmp & (o | BB_AF | BB_R1))) att |= tmp >>= 9;
    tmp = Setbit64(s);
    while(False(tmp & (o | BB_HF | BB_R1))) att |= tmp >>= 7;
    return att;
}

uint64_t Eng::gen_r_attack(int s, uint64_t o)
{
    uint64_t tmp, att = 0;
    remove_bit(&o,s);
    tmp = Setbit64(s);
    while(False(tmp & (o | BB_HF))) att |= tmp <<= 1;
    tmp = Setbit64(s);
    while(False(tmp & (o | BB_AF))) att |= tmp >>= 1;
    tmp = Setbit64(s);
    while(False(tmp & (o | BB_R8))) att |= tmp <<= 8;
    tmp = Setbit64(s);
    while(False(tmp & (o | BB_R1))) att |= tmp >>= 8;
    return att;
}
// pre-computations to fill lookup tables for p,n,k

Code: Select all

uint64_t Eng::gen_wp_attack(int s)
{
    uint64_t target = 0;
    target |= (Setbit64(s) & ~BB_HF) << 9;
    target |= (Setbit64(s) & ~BB_AF) << 7;
    return target;
}

uint64_t Eng::gen_bp_attack(int s)
{
    uint64_t target = 0;
    target |= (Setbit64(s) & ~BB_HF) >> 7;
    target |= (Setbit64(s) & ~BB_AF) >> 9;
    return target;
}

uint64_t Eng::gen_n_attack(int s)
{
    uint64_t target = 0;
    target |= (Setbit64(s) & ~(BB_R7 | BB_R8 | BB_HF)) << 17;
    target |= (Setbit64(s) & ~(BB_R7 | BB_R8 | BB_AF)) << 15;
    target |= (Setbit64(s) & ~(BB_R8 | BB_GF | BB_HF)) << 10;
    target |= (Setbit64(s) & ~(BB_R8 | BB_BF | BB_AF)) <<  6;
    target |= (Setbit64(s) & ~(BB_R1 | BB_R2 | BB_AF)) >> 17;
    target |= (Setbit64(s) & ~(BB_R1 | BB_R2 | BB_HF)) >> 15;
    target |= (Setbit64(s) & ~(BB_R1 | BB_BF | BB_AF)) >> 10;
    target |= (Setbit64(s) & ~(BB_R1 | BB_GF | BB_HF)) >>  6;
    return target;
}

uint64_t Eng::gen_k_attack(int s)
{
    uint64_t target = 0;
    target |= (Setbit64(s) & ~(BB_R8)) << 8;
    target |= (Setbit64(s) & ~(BB_R1)) >> 8;
    target |= (Setbit64(s) & ~(BB_HF)) << 1;
    target |= (Setbit64(s) & ~(BB_AF)) >> 1;
    target |= (Setbit64(s) & ~(BB_R8 | BB_HF)) << 9;
    target |= (Setbit64(s) & ~(BB_R1 | BB_AF)) >> 9;
    target |= (Setbit64(s) & ~(BB_AF | BB_R8)) << 7;
    target |= (Setbit64(s) & ~(BB_HF | BB_R1)) >> 7;
    return target;
}
Hope it is simple and short enough :)

User avatar
xr_a_y
Posts: 733
Joined: Sat Nov 25, 2017 1:28 pm
Location: France

Re: very small bitboard move/attack generator

Post by xr_a_y » Tue Oct 30, 2018 8:34 am

Thanks, that's short enought.
This is already usefull if I use then to iterate other set bits using more or less the current algorithm for move generation or attack.
But I suspect it won't be a huge speed boost ;i'd like to do more with this.
I guess I shall keep a bitboard of white and black pieces to combined occuped square this those attack bitboard in order to get in one shot the possible move (including captures).
How do you handle this for sliding piece with minimal code ?

abulmo2
Posts: 189
Joined: Fri Dec 16, 2016 10:04 am
Contact:

Re: very small bitboard move/attack generator

Post by abulmo2 » Tue Oct 30, 2018 10:45 am

You may have a look at Dumb, my simple chess program in D language (a C/C++ like language):
https://github.com/abulmo/Dumb
It is bitboard based, using the hyperbola quintessence algorithm to generate moves.
Overall, Dumb has less lines of code than minic and probably use less sophisticated algorithms, but it looks much faster and a little stronger.
Richard Delorme

User avatar
xr_a_y
Posts: 733
Joined: Sat Nov 25, 2017 1:28 pm
Location: France

Re: very small bitboard move/attack generator

Post by xr_a_y » Tue Oct 30, 2018 11:21 am

Great input thanks.

Indeed Dumb as window/pvs/nullmove/TT/check extension/IID but no LMR, but its evaluation is smarter than Minic PST only.
Great source to read, i'll give feedback.

User avatar
xr_a_y
Posts: 733
Joined: Sat Nov 25, 2017 1:28 pm
Location: France

Re: very small bitboard move/attack generator

Post by xr_a_y » Tue Oct 30, 2018 11:37 am

Wow on my hardware (and even without -flto because I lack llvm gold ...) Dumb is crunching 3Mnps when Minic is at 300knps :shock:

abulmo2
Posts: 189
Joined: Fri Dec 16, 2016 10:04 am
Contact:

Re: very small bitboard move/attack generator

Post by abulmo2 » Thu Nov 01, 2018 7:01 am

xr_a_y wrote:
Tue Oct 30, 2018 11:21 am
Indeed Dumb as window/pvs/nullmove/TT/check extension/IID but no LMR, but its evaluation is smarter than Minic PST only.
Dumb's evaluation is tapered and well tuned but it remains quite simplistic: material + pst + tempo.
Richard Delorme

maksimKorzh
Posts: 81
Joined: Sat Sep 08, 2018 3:37 pm
Location: Ukraine
Full name: Maksim Korzh
Contact:

Re: very small bitboard move/attack generator

Post by maksimKorzh » Thu Nov 01, 2018 8:00 am

Vivien, it's I'm so happy people are gaining interest in minimalist chess, I've found your minic engine idea to be very interesting. Unfortunately it's not always easy to define the true goals while writing a minimalist chess, I mean what kind of minimalism is about to prefer - minimalist RAM usage/minimalist source code/minimalist design and features. How did you come with an idea to write minic? What are your goals? I really wonder.

Post Reply