2

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.

Community
  • 1
  • 1

1 Answers1

5

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;
Keith Randall
  • 22,985
  • 2
  • 35
  • 54
  • That did the trick, thank you very much. If it isn't too inconvenient, do you think you could share your technique for going about problems like this? Do you start with an example then just try working it out on paper? –  Nov 11 '12 at 03:29
  • 2
    It's a pretty standard bit-parallel thing to do. Check out http://graphics.stanford.edu/~seander/bithacks.html for lots of standard bit-twiddling. – Keith Randall Nov 11 '12 at 04:23