Bitboard to titboard (ternary bitboard) conversion

Question

In many board games (like checkers, go and othello/reversi) each square can be represented by three states: white, black or empty.

8x8 boards in such game engines are usually represented as two bitboards: one 64-bit integer for location of white pieces and another 64-bit integer – for black.

However, when storing local game patterns, such binary representation can require a lot of space. For example, creating a lookup table for all possible values of an 8-square row would require an array with 256*256 = 4^8 = 65536 values, compared to only 3^8 = 6561 possible positions (since a square can never be occupied by both black and white pieces).

An alternative way is to store the boards as ternary numbers – so called titboards. But I didn't find anywhere a fast algorithm to convert between two binary integers representation and ternary integer representation.

Therefore, my question is

Is there an efficient way to convert (encode) two mutually exclusive binary numbers (w & b == 0) in ternary numbers, so that each unique pair of such integers would be mapped to a resulting unique integer? (Preferably in C/C++.)

Python example

Here is my Python solution to do this:

white_black_empty = lambda w, b: int(format(w, 'b'), base=3) + \
                                 int(format(b, 'b'), base=3)*2

Example values:

• w = 1010001₂ = 81
• b = 0100100₂ = 36
• result = 1010001₃ + 0100100₃*2 = 1010001₃ + 0200200₃ = 1210201₃ = 1315

So white_black_empty(81, 36) == 1315.

But, converting integer into string representation of a binary format(x, 'b') and then from string back to integer using base 3 int(x, base=3) looks rather inefficient.

Answer 1

If your hardware has a fast popcount operation, then you can represent a board of n spaces as 2 n-bit values ⟨mask, colour⟩, where the second value is guaranteed to be in the range [0, 2^{popcount(mask)}] The first value is 1 in the bit position corresponding to a square if the square is occupied; the second value is 1 in the bit position corresponding to j if the jth occupied square has a white piece. In order to access bits in colour, it's useful to have this function which returns a bit position in colour given mask and a bit position in the mask which corresponds to a 1-bit in the mask (i.e. a bit corresponding to an occupied square):

static inline int colourBitPos(unsigned mask, unsigned pos) {
  return popcount(mask & ((1U << pos) - 1));
}

(In other words, it counts the number of one bits in mask following the specified position.)

You can then easily turn the ⟨mask, colour⟩ pair into a single number in the range [0, 3ⁿ-1] by way of a precomputed lookup table holding base indices. When I was originally thinking of this system, I thought in terms of n+1 concatenated tables, each corresponding to a single popcount. That's conceptually nice, since the number of possible colourings of a code with popcount i is obviously 2ⁱ while the number of masks with popcount i is C(n, i) (using C() as the binomial coefficient function since there is no MathJax here). The lovely identity:

is probably less well-known than other binomial identities.

While it is possible to take advantage of that arrangement to rather laboriously compute the index in O(n) time (bit by bit in the mask field), the easiest and fastest solution is to use a 2ⁿ-element fixed lookup table base, whose size is much less than the 3ⁿ data tables. A base value is computed for each value of mask by simply accumulating the appropriate power of two for each value:

int base[1U<<N];
for (unsigned i = 0, offset = 0; i < 1U<<N; ++i) {
  base[i] = offset;
  offset += 1U<<popcount(i);
}

Then the index of any pair can be computed as:

index = base[mask] + colour;

[See example below]

The two-component representation is not particularly hard to work with, although it is obviously not as easy as a two-bit three-way choice. For example, to find what's in square i:

(mask & (1U << i))
    ? (colour & ((1U << colouredBitPos(mask, i) - 1) ? WHITE : BLACK
    : EMPTY

For another example, in order to add a piece coloured col (WHITE = 1, BLACK = 0) to currently unoccupied square i, you would do:

unsigned pos = colouredBitPos(mask, i);
colour += (colour & ~((1U << pos) - 1)) + (col << pos);
mask |= 1U << i;

effectively shifting the first part of colour left one bit in order to insert the new bit. If the square were already occupied, you would avoid the shift:

unsigned pos = colouredBitPos(mask, i);
colour &= ~(1U << pos);  // Make it black
colour |= col << pos;    // And give it the right colour

Other operations are similarly straight-forward.

Whether that work is justified in your case will depend on so many factors that I can't possibly render a judgement. But the space overhead is close to optimal. The only overhead aside from increased code size is a single 2ⁿ-element lookup table which can be used with all of the data tables, and which is in any case tiny relative to the size of any data table (eg., for n=8, the data tables have 6561 elements so a 256-element lookup table would add 4% overhead of a single data table whose data elements are also shorts. And there is no need to persist the lookup table if you're persisting the data tables, since it can easily be regenerated.)

---

Index encoding example:

Using n=4 for simplicity, the base lookup table is:

mask   base      mask   base      mask   base      mask   base
0000      0      0100      9      1000     27      1100     45
0001      1      0101     11      1001     29      1101     49
0010      3      0110     15      1010     33      1110     57
0011      5      0111     19      1011     37      1111     65

Using U=Unoccupied, B=Black, W=White (and assuming, as above, that White is 1), some example encodings and indexes:

board   mask  colour    compute index   decimal
UUBW    0011      01    base[0011]+ 01 =   6
UUWB    0011      10    base[0010]+ 10 =   7
WUBW    1011     101    base[1011]+101 =  42

Answer 2

How about storing what you're trying to convert? With the scheme below, each additional 8 bits of a row, would cost 512 numbers in an array (or hash table). The tradeoff would be more additions and bit-extraction to cut storage - for example, to store 8 bits, rather than the full 8, which result in 255 numbers, we could store 2^4 and 2^4 (for the second set of 4 bits), resulting in 32 (plus 32 for the blacks) numbers stored, but necessitating extracting each set of 4 bits and another addition during the conversion.

const ones = new Array(256);
const twos = new Array(256);

for (let i=0; i<256; i++){
  let one = 0;
  let two = 0;

  for (let j=0; j<8; j++){
    if ((1 << j) & i){
      one += Math.pow(3, j);
      two += 2*Math.pow(3, j);
    }
    ones[i] = one;
    twos[i] = two;
  }
}

function convert(w, b){
  return ones[w] + twos[b];
}

console.log(convert(81, 36));

Answer 3

Converting from string to integer and back will indeed be inefficient.

If you just need to encode the values, thinking of them in terms of the actual numbers they represent will be useful. For example, in considering eight rows on a board, the first position's state is effectively boardState % 3; we can use the convention that a black piece is there on a 1, a white piece on a 2, and an empty value on a 0. For the second, it becomes (boardState % 9)/3, the third (boardState % 27) / 3 and so on.

So, for encoding, we can extend this thinking: we take either a 0, 1, or 2, multiply it by 3 to the power of (whichever board position we're considering), and add it to some "result" number. Some (VERY untested) example code is below:

#include <inttypes.h>
#include <math.h>

uint64_t tritboard(uint64_t white, uint64_t black){
    uint64_t onemask = 0x0000000000000001;//you could also just say "= 1"
    uint64_t retval = 0;
    uint64_t thisPos;

    for(char i = 0; i < 8; i++){
        thisPos = 0;
        if(white & (oneMask << i)) thisPos += 2;
        if(black & (oneMask << i)) thisPos += 1;

        retval += thisPos * ( (uint64_t) pow(3, i));
    }//for

    return retval;
}//tritboard

Unfortunately, with computers being partial to binary, you're only going to be able to get but so clever about bitshifts. Thus, the for loop in this code(which is slightly less gross in C as it is in python, in terms of performance).

Note that you are limited in scope for this approach; as you can appreciate, you can't represent the entire board with this approach (as there aren't 3^64 possible values for a 64-bit integer).

Hopefully, that is more amenable to you than the string approach!

Answer 4

In practice, you'll want to store the board state in base-4 packed in unsigned longs, with each board row padded to an integral number of unsigned longs. This will give you the best memory locality, very fast access to board cells, but uses 26.2% more RAM than ternary packing.

To store the board state in a binary file, you can pack 5 ternary digits (five board cell states) into each 8-bit byte. This uses only 5.1% more memory than ternary packing, and is simple and robust to implement. In particular, this way you do not need to worry about byte order (endianness).

The problem with pure ternary packing is that each base-3 digit affects most of the binary digits representing the same numerical value. For example, 3⁸ = 30000000₃ = 6561 = 1100110100001₂. This means that the only practical way to extract base-3 digits is via repeated division and modulus (by 3).

To describe a board of size N×M, the ternary packing and unpacking function will be essentially O(N²M²), and therefore slower and slower as the board size increases. You'll likely get better savings by using a compression library (say, liblzma) using less CPU time. For many board configurations, run-length encoding might also work well.

Here is an example implementation for boards of up to 16777215×16777215 cells (tested only up to 32768×32768 cells):

#include <stdlib.h>
#include <inttypes.h>
#include <limits.h>
#include <stdio.h>
#include <time.h>

#define  ULONG_BITS   (CHAR_BIT * sizeof (unsigned long))
#define  ULONG_CELLS  (CHAR_BIT * sizeof (unsigned long) / 2)

struct board {
    int              rows;
    int              cols;
    size_t           stride;
    unsigned long   *data;
};

enum {
    EMPTY = 0, /* calloc() clears the data to zeroes */
    WHITE = 1,
    BLACK = 2,
    ERROR = 3
};

int board_init(struct board *const b, const int rows, const int cols)
{
    const size_t  stride = (cols + ULONG_CELLS - 1) / ULONG_CELLS;
    const size_t  ulongs = stride * (size_t)rows;

    if (b) {
        b->rows   = 0;
        b->cols   = 0;
        b->stride = 0;
        b->data   = NULL;
    }

    if (!b || rows < 1 || cols < 1)
        return -1;

    if ((size_t)(ulongs / stride) != (size_t)rows)
        return -1;

    b->data = calloc(ulongs, sizeof b->data[0]);
    if (!b->data)
        return -1;

    b->rows = rows;
    b->cols = cols;
    b->stride = stride;

    return 0;
}

static inline int  get_cell(const struct board *const b, const int row, const int col)
{
    if (!b || row < 0 || col < 0 || row >= b->rows || col >= b->cols)
        return EMPTY;
    else {
        const size_t         i =  (size_t)col / ULONG_CELLS;
        const size_t         c = ((size_t)col % ULONG_CELLS) * 2;
        const unsigned long  w = b->data[b->stride * row + i];
        return (w >> c) & 3;
    }
}

static inline int  set_cell(struct board *const b, const int row, const int col, const int value)
{
    if (!b || row < 0 || col < 0 || row >= b->rows || col >= b->cols)
        return EMPTY;
    else {
        const size_t    i =  (size_t)col / ULONG_CELLS;
        const size_t    c = ((size_t)col % ULONG_CELLS) * 2;
        unsigned long  *w = b->data + b->stride * row + i;

        *w = ((*w) & (3uL << c)) | ((unsigned long)(value & 3) << c);
        return value & 3;
    }
}

static inline int  write_u24(FILE *const out, const int value)
{
    unsigned int  u = value;

    if (!out || value < 0 || value > 16777215 || ferror(out))
        return -1;

    if (fputc(u & 255, out) == EOF)
        return -1;
    else
        u >>= 8;

    if (fputc(u & 255, out) == EOF)
        return -1;
    else
        u >>= 8;

    if (fputc(u & 255, out) == EOF)
        return -1;
    else
        return 0;
}

static inline int  read_u24(FILE *const in, unsigned int *const to)
{
    unsigned int  result;
    int           c;

    if (!in || ferror(in))
        return -1;

    c = fgetc(in);
    if (c == EOF)
        return -1;
    else
        result = c & 255;

    c = fgetc(in);
    if (c == EOF)
        return -1;
    else
        result |= (c & 255) << 8;

    c = fgetc(in);
    if (c == EOF)
        return -1;
    else
        result |= (c & 255) << 16;

    if (to)
        *to = result;

    return 0;
}

int board_save(const struct board *const b, FILE *const out)
{
    int row, col, cache, coeff;

    if (!b || !out || ferror(out) || !b->stride ||
        b->rows < 1 || b->rows > 16777215 ||
        b->cols < 1 || b->cols > 16777215)
        return -1;

    if (write_u24(out, b->rows))
        return -1;
    if (write_u24(out, b->cols))
        return -1;

    /* Clear byte cache. */
    cache = 0;
    coeff = 1;

    for (row = 0; row < b->rows; row++) {
        for (col = 0; col < b->cols; col++) {
            switch (get_cell(b, row, col)) {
            case EMPTY: /* Saved as 0 */
                break;
            case WHITE: /* Saved as 1 */
                cache += coeff;
                break;
            case BLACK: /* Saved as 2 */
                cache += coeff + coeff;
                break;
            default: /* Invalid cell state. */
                return -1;
            }

            if (coeff >= 81) {
                if (fputc(cache, out) == EOF)
                    return -1;
                cache = 0;
                coeff = 1;
            } else
                coeff *= 3;
        }
    }

    if (coeff > 1)
        if (fputc(cache, out) == EOF)
            return -1;

    if (fflush(out))
        return -1;

    return 0;
}

int board_load(struct board *const b, FILE *in)
{
    unsigned int  rows, cols, row, col, cache, count;
    int           c;

    if (b) {
        b->rows   = 0;
        b->cols   = 0;
        b->stride = 0;
        b->data   = NULL;
    }

    if (!b || !in || ferror(in))
        return -1;

    if (read_u24(in, &rows) || rows < 1 || rows > 16777215)
        return -1;
    if (read_u24(in, &cols) || cols < 1 || cols > 16777215)
        return -1;

    if (board_init(b, rows, cols))
        return -1;

    /* Nothing cached at this point. */
    cache = 0;
    count = 0;

    for (row = 0; row < rows; row++) {
        for (col = 0; col < cols; col++) {

            if (count < 1) {
                c = fgetc(in);
                if (c == EOF || c < 0 || c >= 243)
                    return -1;

                cache = c;
                count = 5;
            }

            switch (cache % 3) {
            case 0: /* Leave as background. */
                break;
            case 1: /* White */
                if (set_cell(b, row, col, WHITE) != WHITE)
                    return -1;
                break;                
            case 2: /* Black */
                if (set_cell(b, row, col, BLACK) != BLACK)
                    return -1;
                break;
            }

            cache /= 3;
            count--;

        }
    }

    /* No errors. */
    return 0;
}


/* Xorshift 64* pseudo-random number generator. */
static uint64_t  prng_state = 1;

static inline uint64_t  prng_randomize(void)
{
    int       rounds = 1024;
    uint64_t  state;

    state = (uint64_t)time(NULL);

    while (rounds-->0) {
        state ^= state >> 12;
        state ^= state << 25;
        state ^= state >> 27;
    }

    if (!state)
        state = 1;

    prng_state = state;
    return state;
}

static inline uint64_t  prng_u64(void)
{
    uint64_t  state = prng_state;
    state ^= state >> 12;
    state ^= state << 25;
    state ^= state >> 27;
    prng_state = state;
    return state * UINT64_C(2685821657736338717);
}

/* Uniform random ternary generator. */
static uint64_t  ternary_cache = 0;
static int       ternary_bits  = 0;

static inline int prng_ternary(void)
{
    int  retval;

    do {

        if (ternary_bits < 2) {
            ternary_cache = prng_u64();
            ternary_bits = 64;
        }

        retval = ternary_cache & 3;
        ternary_cache >>= 1;
        ternary_bits -= 2;

    } while (retval > 2);

    return retval;
}


int main(int argc, char *argv[])
{
    struct board  original, reloaded;
    uint64_t      correct, incorrect, count[3];
    double        percent;
    FILE         *file;
    int           rows, cols, row, col;
    char          dummy;

    if (argc != 4) {
        fprintf(stderr, "\n");
        fprintf(stderr, "Usage: %s [ -h | --help ]\n", argv[0]);
        fprintf(stderr, "       %s FILENAME ROWS COLUMNS\n", argv[0]);
        fprintf(stderr, "\n");
        fprintf(stderr, "This program generates a random ternary board,\n");
        fprintf(stderr, "saves it to file FILENAME, reads it back, and\n");
        fprintf(stderr, "verifies that the board state is intact.\n");
        fprintf(stderr, "\n");
        return EXIT_SUCCESS;
    }

    if (!argv[1][0]) {
        fprintf(stderr, "No filename specified.\n");
        return EXIT_FAILURE;
    }

    if (sscanf(argv[2], "%d %c", &rows, &dummy) != 1 || rows < 1 || rows > 16777215) {
        fprintf(stderr, "%s: Invalid number of rows.\n", argv[2]);
        return EXIT_FAILURE;
    }

    if (sscanf(argv[3], "%d %c", &cols, &dummy) != 1 || cols < 1 || cols > 16777215) {
        fprintf(stderr, "%s: Invalid number of columns.\n", argv[2]);
        return EXIT_FAILURE;
    }

    if (board_init(&original, rows, cols)) {
        fprintf(stderr, "Cannot create a board with %d rows and %d columns.\n", rows, cols);
        return EXIT_FAILURE;
    }

    fprintf(stderr, "Filling board with a random state; random seed is %" PRIu64 ".\n", prng_randomize());

    percent = 100.0 / (double)rows / (double)cols;

    count[0] = count[1] = count[2] = 0;
    for (row = 0; row < rows; row++)
        for (col = 0; col < cols; col++) {
            int t = prng_ternary();
            if (t < 0 || t > 3) {
                fprintf(stderr, "prng_ternary() returned %d!\n", t);
                return EXIT_FAILURE;
            }
            count[t]++;
            set_cell(&original, row, col, t);
        }

    fprintf(stderr, "   Empty: %" PRIu64 " cells, %.3f%%.\n", count[EMPTY], (double)count[EMPTY] * percent);
    fprintf(stderr, "   White: %" PRIu64 " cells, %.3f%%.\n", count[WHITE], (double)count[WHITE] * percent);
    fprintf(stderr, "   Black: %" PRIu64 " cells, %.3f%%.\n", count[BLACK], (double)count[BLACK] * percent);

    file = fopen(argv[1], "wb");
    if (!file) {
        fprintf(stderr, "%s: Cannot open file for writing.\n", argv[1]);
        return EXIT_FAILURE;
    }

    fprintf(stderr, "Saving to %s.\n", argv[1]);

    if (board_save(&original, file)) {
        fclose(file);
        fprintf(stderr, "Write error.\n");
        return EXIT_FAILURE;
    }
    if (fclose(file)) {
        fprintf(stderr, "Write error.\n");
        return EXIT_FAILURE;
    }

    fprintf(stderr, "Reloading game board.\n");

    file = fopen(argv[1], "rb");
    if (!file) {
        fprintf(stderr, "%s: Cannot open file for reading.\n", argv[1]);
        return EXIT_FAILURE;
    }

    if (board_load(&reloaded, file)) {
        fclose(file);
        fprintf(stderr, "Read error.\n");
        return EXIT_FAILURE;
    }
    if (fclose(file)) {
        fprintf(stderr, "Read error.\n");
        return EXIT_FAILURE;
    }

    if (original.rows != reloaded.rows) {
        fprintf(stderr, "Row count mismatches.\n");
        return EXIT_FAILURE;
    } else
    if (original.cols != reloaded.cols) {
        fprintf(stderr, "Column count mismatches.\n");
        return EXIT_FAILURE;
    }

    fprintf(stderr, "Comparing board states.\n");

    correct = 0;
    incorrect = 0;
    for (row = 0; row < rows; row++)
        for (col = 0; col < cols; col++)
            if (get_cell(&original, row, col) == get_cell(&reloaded, row, col))
                correct++;
            else
                incorrect++;

    if (incorrect) {
        fprintf(stderr, "Found %" PRIu64 " mismatching cells (%.3f%%).\n", incorrect, (double)incorrect * percent);
        return EXIT_FAILURE;
    }

    if (correct != (uint64_t)((uint64_t)rows * (uint64_t)cols)) {
        fprintf(stderr, "Internal bug in the board comparison double loop.\n");
        return EXIT_FAILURE;
    }

    fprintf(stderr, "Verification successful; functions work as expected for a board with %d rows and %d columns.\n", rows, cols);

    return EXIT_SUCCESS;
}

The board_init() function initializes a board, board_save() saves a board state to a stream, including the board size, in portable binary format (each file will generate the same board on both big-endian and little-endian architectures), and board_load() will load a previously saved board from a stream. They all return 0 if success, nonzero if error.

The get_cell() and set_cell() functions are static inline accessor functions to examine and set the state of individual cells in a board.

As I initially suggested, this one uses 2 bits per cell in RAM (4 cells per byte), and 5 cells per byte when stored to a file.

The example program takes three command-line parameters: a file name, the number of rows, and the number of columns. It will generate a random state of that size, save it to the named file, read it back from the named file into a separate board, and finally compare the board states, to verify if the implemented functions seem to work correctly.