OSDev.org

Posted: **Fri Sep 24, 2010 8:14 am**

I've decided to continue my chess programming efforts from scratch. No deadline or anything. Taking it slow as part of a learning process.

So I was thinking about the problem of shifting a pattern around on a bitboard. Fx, if you shift a patter left, if you shift it too far, which you sometimes need to do, the part of the patter which is shifted over the "edge" will usually appear at the opposite side of the board, which is not what is needed.

The solution I've come up with, not saying it haven't been done before, though I haven't seen it anywhere, is actually rather simple, but rather than trying to explain it, I'll simply post the code. It should be pretty self explanatory.

Code: Select all

class Board {
    unsigned char* rank;
  public:
    unsigned long long board;
    Board() {
        rank = (unsigned char*)&board;
        board = (some_pattern)LL;
    }
    void shiftRight(int n) {
        for(int i = 0; i < 8; i++)
            *(rank+i) = *(rank+i) << n;
    }
    void shiftLeft(int n) {
        for(int i = 0; i < 8; i++)
            *(rank+i) = *(rank+i) >> n;
    }
    void shiftUp(int n) {
        board = board << (n * 8);
    }
    void shiftDown(int n) {
        board = board >> (n * 8);
    }
};

Question number one is if this is a safe approach. At first I used regular signed variable, which had some weird side effects that I don't quite understand. didn't think that the sign bit was an issue when shifting, but in any case if seems to work well now.

Question number two is of course if there's any obvious improvements I've missed. fx. I was thinking if it would be possible to drop the rank pointer all together like:

Code: Select all

void shiftRight(int n) {
    for(int i = 0; i < 8; i++)
        *((unsigned char*)&board+i) = *((unsigned char*)&board+i) << n;
}

I am aware that the obvious solution involves a union, but I seem to recall having had some trouble with that approach in the past.

It was my original plan to do it in C, oddly as it may sound, but unless you tell me otherwise, I'll assume that there's no pretty way to do it.

Also, should it not be possible to leave the pointer out of the equation, I'd really like it to be const, but am not sure how exactly to achieve that effect.

Anyway, looking forward to your input on the issue.

Best regards.

edit:
obviously I'll need to ensure that the types are safe, but for now it only need work on my own machine.

Posted: **Fri Sep 24, 2010 8:34 am**

The problem you see with signed chars is probably that you get a sign extension (from implicit conversion to int) before the shift.

There are a few things to be aware of with this technique though, first of all you have to make sure you use types of appropriate size (the standard does not guarantee that fx long long is 64 bits and char is 8 bits). Also the bit layout of a 64-bit integer need not be the same on other implementation (you could have big endian, mixed endian and all kind of crazy schemes).

To avoid this you could for sideways shifts first mask out the bits that will be lost and then shift the entire 64-bit in one go (ie board = (board & ~((0x0101010101010101LL << n) - 0x0101010101010101LL)) >> n).

Posted: **Fri Sep 24, 2010 8:38 am**

Hi,

Your code looks sound. Signedness *does* actually affect shifts - specifically it affects right shifts.

For a signed variable, the compiler will generate an arithemetic shift right, which will shift a copy of the old MSB into the new MSB (effectively copying any signedness).

An unsigned variable will have a logical shift right created for it, which always inserts zero to the MSB. This is what you want.

Why are you shifting the board right in the "shiftLeft" operation and left in the "shiftRight" operation?

Thinking of more efficient ways; surely your problem is just that when (for example) shifting the board one bit left, the LSB of every row will be wrong. However, as you've just shifted the board left you know that bit *should* be zero for all rows.

So, you could just do a 64-bit left shift and mask:

Code: Select all

bitboard = (bitboard << 1) & ~0x0101010101010101UL;

For shifts of multiple amounts, I would personally perform a switch with hand-crafted masks instead of a loop:

Code: Select all

switch(n) {
case 0: break;
case 1: bitboard = (bitboard << 1) & ~0x0101010101010101UL; break;
case 2: bitboard = (bitboard << 2) & ~0x03030303030303UL; break;
case 3: bitboard = (bitboard << 3) & ~0x07070707070707UL; break;
...
}

And so on. This would probably be the fastest you could get this operation in C.

James

Posted: **Fri Sep 24, 2010 4:52 pm**

I took me some time to grasp exactly what was the point with the masks, but I think that I finally got it.

When I shift a row one bit left/right, I know that the outermost bit in the opposite direction must be zero and with two bits, the two outermost bits in the opposite direction and so on and so forth.

It's easy to see how this method is much more efficient, so thanks you very much for that.

As for all the stuff with data types acting differently on different system, I am very much aware of this, but for now it's not important, though I am interested to know if there's any build in types that get around this problem. Alternatively I guess I can just use Bitset (if I stick to C++), though I'm not sure what the consequences will be in terms of efficiency.

In any case, thanks for the comeback, you've been a great help.

edit:
The reason for the confusion regarding the function name not matching the shift direction is actually rather simple. As the LSB is A1 and MSB is H8, the board is actually mirrored compared to how the bits are usually represented. So when you shift the board left, you shift the bits right, and visa versa. It's actually kinda stupid, but it's my understanding that this is the way it's usually done and also I've gotten used to it.

Posted: **Fri Sep 24, 2010 5:46 pm**

OK, here is the revised version:

Code: Select all

class Board {
    unsigned long long board;
  public:
    Board() {
        board = (some_pattern)ull;
    }
    void shiftRight(unsigned int n) {
        switch (n) {
            case 0: break;
            case 1: board = (board << 1) & 0xfefefefefefefefeull; break;
            case 2: board = (board << 2) & 0xfcfcfcfcfcfcfcfcull; break;
            case 3: board = (board << 3) & 0xf8f8f8f8f8f8f8f8ull; break;
            case 4: board = (board << 4) & 0xf0f0f0f0f0f0f0f0ull; break;
            case 5: board = (board << 5) & 0xe0e0e0e0e0e0e0e0ull; break;
            case 6: board = (board << 6) & 0xc0c0c0c0c0c0c0c0ull; break;
            case 7: board = (board << 7) & 0x8080808080808080ull; break;
            default: board = 0ull; break;
        }
    }
    void shiftLeft(unsigned int n) {
        switch (n) {
            case 0: break;
            case 1: board = (board >> 1) & 0x7f7f7f7f7f7f7f7full; break;
            case 2: board = (board >> 2) & 0x3f3f3f3f3f3f3f3full; break;
            case 3: board = (board >> 3) & 0x1f1f1f1f1f1f1f1full; break;
            case 4: board = (board >> 4) & 0x0f0f0f0f0f0f0f0full; break;
            case 5: board = (board >> 5) & 0x0707070707070707ull; break;
            case 6: board = (board >> 6) & 0x0303030303030303ull; break;
            case 7: board = (board >> 7) & 0x0101010101010101ull; break;
            default: board = 0ull; break;
        }
    }
    void shiftUp(int n) {
        board = board << (n * 8);
    }
    void shiftDown(int n) {
        board = board >> (n * 8);
    }
};

Assuming I've gotten the masks right, this should work very well, however, the code does take up a lot of more space now so I was thinking if it wouldn't be about the same storing the masks in and array:

Code: Select all

void shiftLeft(unsigned int n) {
    board = (board >> n) & lmask[n];
}
void shiftReft(unsigned int n) {
    board = (board << n) & rmask[n];
}

Only significant problem I see is if n > 7 or 0, the ladder of which should still work fine with the mask 0xffffffffffffffff, though it will of course mean a bit of wasted processing power, but since it should never happen it shouldn't mean anything.

But how does the two approaches compare? To me it would seem that there's no real difference.

I am aware that the first approach is more explanatory as you don't need to go looking for the masks to see what's actually happening, but I think it's an insignificant difference when it comes to that too.

Best regards.

Posted: **Sat Sep 25, 2010 7:53 am**

I agree, however this is as much a matter of interest.

Here is the newest approach:

Code: Select all

class Board {
    unsigned long long board;
    static const unsigned long long lmask[8], rmask[8];
  public:
    Board() {
        board = (some_pattern)ull;
    }
    void shiftRight(unsigned int n) {
        board = (board << n) & rmask[n];
    }
    void shiftLeft(unsigned int n) {
        board = (board >> n) & lmask[n];
    }
    void shiftUp(unsigned int n) {
        board = board << (n * 8);
    }
    void shiftDown(unsigned int n) {
        board = board >> (n * 8);
    }
};

const unsigned long long Board::rmask[8] = {0xffffffffffffffffull, 
                                            0xfefefefefefefefeull, 
                                            0xfcfcfcfcfcfcfcfcull, 
                                            0xf8f8f8f8f8f8f8f8ull, 
                                            0xf0f0f0f0f0f0f0f0ull, 
                                            0xe0e0e0e0e0e0e0e0ull, 
                                            0xc0c0c0c0c0c0c0c0ull, 
                                            0x8080808080808080ull};
                                            
const unsigned long long Board::lmask[8] = {0xffffffffffffffffull, 
                                            0x7f7f7f7f7f7f7f7full, 
                                            0x3f3f3f3f3f3f3f3full, 
                                            0x1f1f1f1f1f1f1f1full, 
                                            0x0f0f0f0f0f0f0f0full, 
                                            0x0707070707070707ull, 
                                            0x0303030303030303ull, 
                                            0x0101010101010101ull};

I know which approach I prefer, but while it won't necesarily alter my approach, I'm still very interested in the details.

Posted: **Sat Sep 25, 2010 9:32 am**

Hi,

Premature optimisation is the root of all evil, but when working with such important bitboard operations it is important to get them as quick as possible.

Your new version, while it does look neater, is less efficient. The old version only required one short jump which relied on no memory data. Your new one introduces a memory dependency. The AND cannot be computed until the memory load at rmask[n] has completed.

In the original version, the speculation engine could actually end up computing one or many of the possible results before the jump is computed (as there are no dependencies at all!)

It's six of one and two threes of the other to some extent.

James

Posted: **Sat Sep 25, 2010 12:41 pm**

Well, that answered my question

Only question left is regarding what type to use. If I should just use a regular in type and do some pre processor testing for possible complications, or possible should I use std::bitset instead? bitset seem pretty obvious but I think I'll quickly run in to some problems when anding a bitset and an int mask. Could a mask be typecasted as a bitset?

I realise I may sound a bit stupid now, but this is an area I haven't really had the need to worry about before.

Posted: **Sat Sep 25, 2010 6:28 pm**

berkus wrote:Use C99 stdint's uint64_t.

Thanks.

OSDev.org

Is it safe? (C/C++)

Is it safe? (C/C++)

Re: Is it safe? (C/C++)

Re: Is it safe? (C/C++)

Re: Is it safe? (C/C++)

Re: Is it safe? (C/C++)

Re: Is it safe? (C/C++)

Re: Is it safe? (C/C++)

Re: Is it safe? (C/C++)

Re: Is it safe? (C/C++)