位板到titboard(三元位板)转换

Question

在许多棋盘游戏中(如跳棋,go和othello/reversi),每个方块可以用三种状态表示:白色,黑色或空白.

这种游戏引擎中的8x8板通常表示为两个位板:一个64位整数用于白色位置,另一个64位整数用于黑色.

然而,当存储本地游戏模式时,这种二进制表示可能需要大量空间.例如,为8平方行的所有可能值创建查找表将需要具有256*256 = 4 ^ 8 = 65536值的数组,而仅有3 ^ 8 = 6561个可能位置(因为正方形永远不可能是被黑色和白色片段占据).

另一种方法是将电路板存储为三元数 - 所谓的标题.但我没有找到任何在两个二进制整数表示和三元整数表示之间转换的快速算法.

因此,我的问题是

有没有一种有效的方法来转换(编码)三个数字中的两个互斥二进制数(w & b == 0),这样每个唯一的这样的整数对将被映射到一个唯一的整数？(最好用C/C++.)

Python示例

这是我的Python解决方案:

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

示例值:

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

所以white_black_empty(81, 36) == 1315.

但是,将整数转换为二进制的字符串表示形式,format(x, 'b')然后使用基数3 int(x, base=3)将字符串转换回整数看起来效率很低.

Answer 1

存储您要转换的内容怎么样？使用下面的方案，一行中每增加 8 位，就会在数组（或哈希表）中花费 512 个数字。权衡将是更多的添加和位提取以减少存储 - 例如，要存储 8 位，而不是完整的 8 位（这会产生 255 个数字），我们可以存储 2^4 和 2^4（对于第二组） 4 位），导致存储 32 个（加上黑人的 32 个）数字，但需要在转换过程中提取每组 4 位并进行另一次加法。

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