Four in a row, connect 4: some extra explanation
A very efficient algorithm to solve the for in a row game is described by Pascal Pons here. The alpha-beta method and optimizations are explained in detail. However, I had some difficulty to understand the rationale behind the codes to handle the bit board.
So, I have here some explanations at part 6 of the article by Pascal Pons.
Bitboard
Note: columns are numbered from 0, and HEIGHT = 6
The board is coded in three integers, at least 49 bits long (in practice 64 bits).
Bits are numbered thusly:
6 13 20 27 34 41 48
5 12 19 26 33 40 47
4 11 18 25 32 39 46
3 10 17 24 31 38 45
2 9 16 23 30 37 44
1 8 15 22 29 36 43
0 7 14 21 28 35 42Computation of unique key
key = position + mask + bottom
board position mask bottom key
0000000 0000000 0000000 0000000
....... 0000000 0000000 0000000 0001000
...o... 0000000 0001000 0000000 0010000
..xx... 0011000 0011000 0000000 0011000
..ox... 0001000 0011000 0000000 0001100
..oox.. 0000100 0011100 0000000 0000110
..oxxo. 0001100 0011110 1111111 1101101
^ ^ ^ ^Note1: all bit encodings contain one row more than the board.
Note2: bottom is a constant.
Somewhat simpler to see what is going on:
key = mask + bottom + position
mask: one-bits start from the beginning, so (horizontally, column 2)
0001111 is valid, but
0001011 is not validThus, adding 1 ('bottom') to the mask always yields a one on top of the mask, the rest zero:
0001111 + 1 = 0010000 (mask + 1)Adding position (column 2):
0010000 + 0001000 = 0011000 (see key(column 2))Because of the zeros below the one bit in (mask+1), carry does not happen. Likewise, because of the fact that the top bits of position, mask and bottom are all zero, there is no carry between the columns.
Playing a move
Check if a column can be played:
bool canPlay(int col) const
{
return (mask & top_mask(col)) == 0;
}
static uint64_t top_mask(int col) {
return (UINT64_C(1) << (HEIGHT - 1)) << col*(HEIGHT+1);
}A column is full, if the next top-most bit of this column in mask is 1:
0001111 (column 2) this column can be played, but
0111111 cannot be played
UINT64_C(1) << 5 << 2*7: top_mask(2) & mask:
0000000 0000000 00 0 0000 00 0 0000 00 0 0000
0000000 1000000 00 1 0000 00 0 0000 00 0 0000
0000000 0000000 00 0 0000 00 0 1000 00 0 0000
0000000 << 5 = 0000000 << 2*7 = 00 0 0000 & 00 1 1000 = 00 0 0000
0000000 0000000 00 0 0000 00 1 1000 00 0 0000
0000000 0000000 00 0 0000 00 1 1100 00 0 0000
1000000 0000000 00 0 0000 00 1 1110 00 0 0000
1 top_mask(2) mask canPlay(2)So, column 2 can be played. If column 2 of mask was 0111111, then the result would not be zero, and the column could not be played.
Play a column
void play(int col)
{
current_position ^= mask;
mask |= mask + bottom_mask(col);
moves++;
}
static uint64_t bottom_mask(int col) {
return UINT64_C(1) << col*(HEIGHT+1);
}
current_postion ^= mask:
0000000 0000000 0000000
0000000 0000000 0000000
0000000 0001000 0001000
0011000 XOR 0011000 = 0000000
0001000 0011000 0010000
0000100 0011100 0011000
0001100 0011110 0010000
current_position mask current_position
current_position is now the position of the opponent.
UINT64_C(1) << col*(HEIGHT+1):
00 0 0000 00 0 0000
00 0 0000 00 0 0000
00 0 0000 00 0 0000
00 0 0000 << 2*7 = 00 0 0000
00 0 0000 00 0 0000
00 0 0000 00 0 0000
10 0 0000 00 1 0000
1 bottom_mask(2)
mask |= mask + bottom_mask(col):
00 0 0000 00 0 0000 00 0 0000 00 0 0000 00 0 0000
00 0 0000 00 0 0000 00 0 0000 00 0 0000 00 0 0000
00 0 1000 00 0 0000 00 1 1000 00 0 1000 00 1 1000
00 1 1000 + 00 0 0000 = 00 0 1000 OR 00 1 1000 = 00 1 1000
00 1 1000 00 0 0000 00 0 1000 00 1 1000 00 1 1000
00 1 1100 00 0 0000 00 0 1100 00 1 1100 00 1 1100
00 1 1110 00 1 0000 00 0 1110 00 1 1110 00 1 1110
mask bottom_mask(2) mask new maskmask + bottom_mask(2) takes care that there appears a one on top of the original mask in column 2. Or-ing this with the original mask delivers a valid mask, with that extra one in column 2.
Checking for alignment (4 in a row)
The basis for the algorithms to determine if there are four-in-a-row horizontally, vertically or diagonally is the following:
If a bit pattern is shifted one place, and the result is AND-ed with the original, a row of N consecutive one's is replaced by a row of N-1 one's. Moreover, the number of zero's preceding the row of consecutive one's grows by 1, assuming that a right shift is used.
Example:
1110001111100011 A
0111000111110001 A >> 1
0110000111100001 B = A AND (A>>1)So, after three shifts and AND's, if the result is not equal to 0, there is at least one row of 4 or more consecutive one's in the original.
We can optimize this: after the first shift, we can replace the two shift-AND operations by a shift by two places and an AND, because we are sure now that zero's in the middle are replaced by two zero's, and the result will always start with a zero:
0110000111100001 B
0001100001111000 B >> 2
0000000001100000 C = B AND (B >> 2)Note that a shift by 3 places followed by AND is not usable:
1110111000000011 X
0001110111000000 X
0000110000000000 X AND (X>>3)In this example, the result != zero, but there are no 4 consecutive one's in the original.
NOTE: a right shift can result in a sign extension (i.e. the leftmost bit is copied to the right), but in our case that is not a problem: the leftmost bit of the 64-bit word we use to store the game is always zero.
Checking for alignment vertically
Because we are sure that the top row always contains only zeros, we can simply apply the example above.
uint64_t m = pos & (pos > 1);
bool four_in_a_row = ( (m & (m >> 2)) != 0 );Checking for alignment horizontally
In order to handle horizontal rows, we observe that the consecutive rows are not separated by one place as in the vertical case, but are separated by HEIGHT+1 places, so in stead of shifting by 1 and 2, we shift by HEIGHT+1 and 2*(HEIGHT+1).
0000000 0000000 0000000
0000000 0000000 0000000
0000000 0000000 0000000
0011000 0110000 0010000 <
0001000 0010000 0000000
0000100 0001000 0000000
0001100 0011000 0001000 <
^^
pos pos >>(HEIGHT+1) pos&(pos>>(HEIGHT+1))
uint64_t m = pos & (pos >> (HEIGHT+1));
bool four_in_a_row = ( (m & (m >> (2*(HEIGHT+1)))) != 0); After the first shift, we see that there are two horizontal rows with 2 consecutive one's.
Checking for alignment diagonally
To get the neighbours diagonally, we have to look at places HEIGHT of HEIGHT+2 positions further, depending on this diagonal: / or this one: \.
Diagonal /:
0000000 0001100 0000000
0000000 0000000 0000000
0000000 0000000 0000000
0011000 0000000 0000000
0001000 0110000 0000000
0000100 0010000 0000000
0001100 0001000 0001000 <
^
pos pos >> HEIGHT pos&(pos>>HEIGHT)
uint64_t m = pos & (pos >> HEIGHT);
bool four_in_a_row = ( (m & (m >> (2*HEIGHT))) != 0); In this example, we see after the first shift, that there is a / diagonal of two consecutive one's.
Diagonal \:
0000000 0000000 0000000
0000000 0000000 0000000
0000000 0110000 0000000
0011000 0010000 0010000 <
0001000 0001000 0001000 <
0000100 0011000 0000000
0001100 0000000 0000000
^^
pos pos >> (HEIGHT+2) pos&(pos>>(2*(HEIGHT+2)))
uint64_t m = pos & (pos >> (HEIGHT+2));
bool four_in_a_row = ( (m & (m >> (2*(HEIGHT+2)))) != 0); We see after the first shift, there is a \ diagonal of three consecutive one's.
In both cases, the top row of zero's guards against false positives.