_____

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)

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 mask

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.