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