c - 位板到位板(三元位板)转换

Question

在许多棋盘游戏(如西洋跳棋、围棋和黑白棋)中，每个方 block 都可以用三种状态表示:白、黑或空 em>.

此类游戏引擎中的 8x8 棋盘通常表示为两个位棋盘:一个 64 位整数用于白子的位置，另一个 64 位整数用于黑子。

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

另一种方法是将棋盘存储为三进制数——所谓的titboards .但是我在任何地方都找不到在两个二进制整数表示和三元整数表示之间进行转换的快速算法。

因此，我的问题是

有没有一种高效的方法可以将两个互斥的二进制数 (w & b == 0) 转换(编码)为三进制数，以便每一对唯一的这样的整数会被映射到一个结果唯一的整数？ (最好使用 C/C++。)

Python 示例

Here是我的 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

如果您的硬件具有快速 popcount操作，那么您可以将 n 空间的棋盘表示为 2 n 位值 ⟨mask，颜色⟩ , 其中第二个值保证在 [0, 2^{popcount(mask)}] 范围内 如果广场被占用；如果第j被占据的方格有白子，则第二个值在对应于j的位位置为1。为了访问颜色中的位，使用此函数返回颜色中给定掩码的位位置和掩码对应于掩码中的一位(即对应于一个被占用的方 block 的一位):

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

(换句话说，它计算指定位置后面的掩码中的一位数。)

然后您可以轻松地将 ⟨掩码、颜色⟩ 对转换为范围 [0, 3ⁿ-1] 通过预先计算的包含基本索引的查找表。当我最初想到这个系统时，我想到了 n+1 个串联表，每个表对应一个 popcount。这在概念上很好，因为带有 popcount i 的代码的可能着色数量显然是 2ⁱ 而带有 popcount i 是 C(n, i) (使用 C() 作为二项式系数函数，因为这里没有 MathJax)。可爱的身份:

可能不如其他二项式恒等式广为人知。

虽然可以利用这种安排在 O(n) 时间内相当费力地计算索引(在 mask 字段中逐位计算)，但最简单和最快的解决方案是使用 2ⁿ 元素的固定查找表base，其大小远小于 3^{< em>n} 数据表。通过简单地为每个值累加适当的 2 的幂，为 mask 的每个值计算基值:

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

然后任何对的索引可以计算为:

index = base[mask] + colour;

[见下面的例子]

双分量表示并不是特别难处理，尽管它显然不如两位三路选择那么容易。例如，要查找正方形 i 中的内容:

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

再举一个例子，为了向当前未占用的方格 i 添加一 block 彩色 col(WHITE = 1，BLACK = 0)，您可以这样做:

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

有效地将颜色的第一部分左移一位以插入新位。如果广场已经被占领，你会避免转变:

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

其他操作同样简单明了。

这项工作在您的案例中是否合理取决于很多因素，我无法做出判断。但是空间开销接近最优。除了增加的代码大小之外，唯一的开销是一个 2ⁿ 元素的查找表，它可以与所有数据表一起使用，并且在任何情况下相对较小到任何数据表的大小(例如，对于 n=8，数据表有 6561 个元素，因此 256 个元素的查找表将增加 4% 的数据表的开销，其数据元素是也是短裤。如果您要持久化数据表，则无需持久化查找表，因为它可以很容易地重新生成。)

---

索引编码示例:

为简单起见，使用 n=4，base 查找表为:

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

使用 U=Unoccupied、B=Black、W=White(并假设，如上所述，White 为 1)，一些示例编码和索引:

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