Bitboard with connect 5 game?

Question

I need your help to know if it's possible to use a bitboard for a connect 5 game. Because I saw a lot of examples for connect 4 games but nothing if the board is very large such as 15x15 or 19x19. I don't understand how can I represent the board with 64bits.

Thanks you for your help

Answer 1

Huh?

Of course it's possible, if by "bitboard" you just mean "a 2D array using one bit per cell".

It's sometimes easier if you e.g. round off so each row (or column) is a whole number of bytes, but you don't have to do that.

Just do something like:

#include <stdint.h>
#include <limits.h>

#define WIDTH 22
#define HEIGHT 17
uint8_t bits[(WIDTH * HEIGHT + CHAR_BIT - 1) / CHAR_BIT];

this declares bits as an array of bytes, with enough bytes to hold a matrix of WIDTH by HEIGHT cells.

With the example's values, it'll be (22 * 17 + 7) / 8 or 47 bytes long (assuming CHAR_BIT is 8).

Answer 2

It is possible, as explained in unwind's answer, but by doing that you negate the main advantage of bitboards, which is performing logical operations on the entire data structure in one CPU instruction. Optimally, the size of the bitboard would be the width of your instruction set of the platform.

A possible workaround would be to represent the board as multiple smaller "standard" bitboards (32-bit or 64-bit, depending on your platform) and apply logical operations on each mini-bitboard separately. For instance, a board of 15x15 can be broken into 4 8x8 boards, for example:

typedef uint64_t miniboard_type; // 8x8 board

typedef struct
{
    miniboard_type miniboard[4]; // Larger 15x15 board comprising 4 8x8 boards
} bitboard_type;

bitboard_type bitboard;

Correspondigly, I believe that you might also need to adjust the math and logic to account for the edges between the mini-bitboards (and that depends on what you want to do with your main bitboard).