Fast Connected Components for 6x12 bitboard

This optimized code was made for Smash the Code contest. We assume that you are using one 6x12 bitboard per color, represented as the least significant bits of an 128 bit integer (__uint128_t), which is supported by GCC. You can expect about say 800k-1M separations of one color into connected components per 100ms, versus say 200k-250k for a regular bit-BFS per index. It depends on the hardware, but in general expect a 4x speedup over normal bit-BFS. The output is an array of components, which are themselves 6x12 bitboards.

The main idea is to create a lookup table for the transition between 2 rows. This allows you to iterate over the rows 2 by 2 and connect the components already computed in the table.

For a row of 6 columns, the maximum number of components is 3, for example 101010, 010101 or 101101. You can see this because each component must be separated by a space (0), so 4 components (1) have 3 separators (0), which makes 7, which is greater than the columns, 6, so there are at most 3 components.

This means we can keep 3 running active components and seal components as soon as they finish. There is a caveat to this, in that one running component can terminate while another running component keeps it active. This happens for example with this configuration:

Leave a Comment