Connect Four Bitboard

Question

In this post, there was a very interesting suggestion for testing for connect four wins using a bitboard.

The board has a structure like this:

6 14 22 30 38 46 54
5 13 21 29 37 45 53
4 12 20 28 36 44 52
3 11 19 27 35 43 51
2 10 18 26 34 42 50
1  9 17 25 33 41 49
0  8 16 24 32 40 48

They also recommended the following algorithm, for testing for a win using only 8 shifts:

bool haswon(int64_t board)
{
    int64_t y = board & (board >> 7);
    if (y & (y >> 2 * 7)) // check \ diagonal
        return true;
    y = board & (board >> 8);
    if (y & (y >> 2 * 8)) // check horizontal -
        return true;
    y = board & (board >> 9);
    if (y & (y >> 2 * 9)) // check / diagonal
        return true;
    y = board & (board >> 1);
    if (y & (y >> 2))     // check vertical |
        return true;
    return false;
}

I want to implement this algorithm in a similar program I am writing. However, to apply my heuristic function, I need to be able to tell how many pieces are in a given row. I've really been trying to wrap my head around this algorithm, but I can't figure out how to check if there are only 1, 2, or 3 pieces in a row.

Right now, I just am iterating across each row, and counting bits, but I'm sure there must be a better way using shifts.

Answer 1

For row 0, you could get the number of pieces by doing this:

int64_t row0 = board & 0x01010101010101LL;
row0 += row0 >> 32;
row0 += row0 >> 16;
row0 += row0 >> 8;
return row0 & 0xff;

Similarly for the other rows (shift by row number first). In fact, you could probably do two rows at once as the count will always fit in 3 bits.

int64_t x = board & 0x11111111111111LL;
x += x >> 32;
x += x >> 16;
x += x >> 8;
int row0 = x & 0xf;
int row4 = (x >> 4) & 0xf;