_____

# 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 42``````

## Computation 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 valid``````

Thus, adding 1 ('bottom') to the mask always yields a one on top of the mask, the rest zero:

``      0001111 + 1 = 0010000    (mask + 1)``

``      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 (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

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

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)
{
moves++;
}

return UINT64_C(1) << col*(HEIGHT+1);
}

0000000        0000000         0000000
0000000        0000000         0000000
0000000        0001000         0001000
0011000  XOR   0011000    =    0000000
0001000        0011000         0010000
0000100        0011100         0011000
0001100        0011110         0010000
``````

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

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) 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.