How to make movelist using bitboards

Discussion of chess software programming and technical issues.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
Luis Babboni
Posts: 437
Joined: Sat Feb 28, 2015 3:37 pm
Location: Argentina

How to make movelist using bitboards

Post by Luis Babboni » Fri Feb 19, 2021 2:15 pm

Hi!

I´m a little ashamed cause I cant find what Im looking for so I suspect is very obvious or I missing something important.

I think I´m able to find a bitboard with, for example, a 1 in each of possible moves (say 8) for a given knight and a 0 in all other positions.

My question is how, from that, I could make a list move with those 8 possible moves.
I mean, how to separate each move from others.

Sorry if it is a very stupid question, but I could not find the idea of how make it anywhere. it seems is as obvious that it is not needed to explain it (or as I said, I´m missing something very important) :oops:

Thank!

Henk
Posts: 6768
Joined: Mon May 27, 2013 8:31 am

Re: How to make movelist using bitboards

Post by Henk » Fri Feb 19, 2021 2:27 pm

I have a dictionary:

Code: Select all

BitCoordMoveDict[] MovesDict{get;}
per Square64MoveGEn.

So per bitCoord you can lookup the move for that piece type.

Also found this:

Code: Select all

        IMoveBase[] rep = new MoveBase[64];
        BitBoardIndex bbIndex = BitBoardIndex.Instance;


        public IMoveBase Get(ulong coord)
        {
            return rep[bbIndex.Index(coord)];
        }
I don't understand why I don't use Index = (int)Math.Log(coord, 2);
instead of creepy debruijn index
Last edited by Henk on Fri Feb 19, 2021 2:39 pm, edited 5 times in total.


User avatar
Luis Babboni
Posts: 437
Joined: Sat Feb 28, 2015 3:37 pm
Location: Argentina

Re: How to make movelist using bitboards

Post by Luis Babboni » Fri Feb 19, 2021 2:40 pm

Sorry, not understand.

I need ot have a list of all moves and use the bitboard I said to check each of the total moves to know wich is possible and wich no? I do not think that.

It seems I do not understand the background idea.

User avatar
Luis Babboni
Posts: 437
Joined: Sat Feb 28, 2015 3:37 pm
Location: Argentina

Re: How to make movelist using bitboards

Post by Luis Babboni » Fri Feb 19, 2021 2:41 pm

At least for the moment I do not looking for the code.
I need first to understand the idea.

User avatar
Luis Babboni
Posts: 437
Joined: Sat Feb 28, 2015 3:37 pm
Location: Argentina

Re: How to make movelist using bitboards

Post by Luis Babboni » Fri Feb 19, 2021 2:42 pm

Sorry, is not easy to explain me! :D
I did a not bug chess engine yet, Soberango, but I have very little know in programming and nothing in C. I did it in FreeBasic.
i have, i think, a reasonabily understanding of maths, so this is not a problem.

Henk
Posts: 6768
Joined: Mon May 27, 2013 8:31 am

Re: How to make movelist using bitboards

Post by Henk » Fri Feb 19, 2021 2:54 pm

I don't know or can''t remember. Just google it.

I only have this you have to bitshift bitboard moves in a direction 6 times

For straight moves to the right:

Code: Select all

 
 Moves(straightOccupancyBB & rightMovesBB, leftShift, 1, rightMovesBB)

      public static UInt64 Moves(UInt64 occupiedDirMoves, IShiftOperator shift, int multiplier, UInt64 locationDirMoves)
    =>
      locationDirMoves ^ (
                            (
                                  shift.Shift(occupiedDirMoves, multiplier)
                                | shift.Shift(occupiedDirMoves, 2 * multiplier)
                                | shift.Shift(occupiedDirMoves, 3 * multiplier)
                                | shift.Shift(occupiedDirMoves, 4 * multiplier)
                                | shift.Shift(occupiedDirMoves, 5 * multiplier)
                                | shift.Shift(occupiedDirMoves, 6 * multiplier)
                            ) & locationDirMoves
                          )
       );
 
Too complicated.

User avatar
hgm
Posts: 25864
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: How to make movelist using bitboards

Post by hgm » Fri Feb 19, 2021 3:02 pm

Most modern CPUs have an instruction BSF (BitScanForward) which gives the number of trailing zero bits in the operand. Bitboard engines use that to get the square number of a target square indicated in the bitboard bb. This can then be removed from the bitboard by calculating the bitwise AND operation of bb AND bb-1, after which you can 'extract' the square number of the next target square in the same way. Until finally the entire remaining bb is zero, because all targets have been processed.

C/C++ does not support BSF in its language, but many compilers offer functions (written in assembler) to calculate it. If your BASIC doesn't, then you are out of luck.

There is an older method from before CPUs had BSF, which extracts the lowest 1 bit (by calculating bb AND -bb), multiplies it with a magic 'DeBruin' constant,shifts it to the right 58 places, and uses the 6-bit number that is left in a lookup table that then gives the square number.

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

Re: How to make movelist using bitboards

Post by Desperado » Fri Feb 19, 2021 3:28 pm

Luis Babboni wrote:
Fri Feb 19, 2021 2:15 pm
Hi!

I´m a little ashamed cause I cant find what Im looking for so I suspect is very obvious or I missing something important.

I think I´m able to find a bitboard with, for example, a 1 in each of possible moves (say 8) for a given knight and a 0 in all other positions.

My question is how, from that, I could make a list move with those 8 possible moves.
I mean, how to separate each move from others.

Sorry if it is a very stupid question, but I could not find the idea of how make it anywhere. it seems is as obvious that it is not needed to explain it (or as I said, I´m missing something very important) :oops:

Thank!
Hello Luis,

Code: Select all

bitboard tmpsrc,tmpdst;

// 1. the source squares are related to a piece for example
tmpsrc = bb_white_knights;

// 2.loop that bitboard
while (tmpsrc) {

    // 2.1 pick every (piece) bit you find, you get the source square
    src = scan_and_remove_bit(tmpsrc)
    
    // 2.2 use the source square to generate the attacked  squares
    // target can be empty squares or opponent squares to be captured for example
    tmpdst = AttackN(src) & target
    
    // 2.3 loop the destination squares
    while (tmpdst) {
        dst = scan_and_remove_bit(tmpdst)
        
        // here you have the pair of squares... store the move in your list.
        AddMove(src,dst...)
    }
}
As pointed out by others you need a function to get the index (0...63) of a bit (like bitscan).

Hope that helps.
Last edited by Desperado on Fri Feb 19, 2021 3:46 pm, edited 2 times in total.

Henk
Posts: 6768
Joined: Mon May 27, 2013 8:31 am

Re: How to make movelist using bitboards

Post by Henk » Fri Feb 19, 2021 3:33 pm

I don't understand his question. For getting first bit I use this.

Code: Select all

        /// <returns>least significant bit</returns>
        public static UInt64 First(UInt64 bits) 
            => bits & (~bits + 1);

        /// <returns>bits - least significant bit</returns>
        public static UInt64 Rest(UInt64 bits)
        {
            var res = bits & (bits - 1);
            Debug.Assert(res == bits - First(bits));
            return res;
        }

Post Reply