位板到位板（三元位板）转换

Question

在许多棋盘游戏中（如西洋跳棋、围棋和othello/reversi），每个方块可以用三种状态表示：白、黑或空.

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

然而，当存储本地游戏模式时，这种二进制表示可能需要很多 space。例如，为 8 平方行的所有可能值创建查找 table 将需要一个包含 256*256 = 4^8 = 65536 个值的数组，而只有 3^8 = 6561 个可能的位置（因为正方形永远不能被黑色和白色的棋子同时占据。

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

因此，我的问题是

是否有高效方法将两个互斥的二进制数 (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

从字符串到整数再返回确实效率低下。

如果您只需要对值进行编码，那么根据它们代表的实际数字来考虑它们将会很有用。例如，考虑棋盘上的八行，第一个位置的状态实际上是 boardState % 3；我们可以使用这样的约定，即 1 上有黑色棋子，2 上有白色棋子，0 上有空值。对于第二个，它变成 (boardState % 9)/3，第三个 (boardState % 27) / 3 等等。

因此，对于编码，我们可以扩展这种思路：我们取 0、1 或 2，将其乘以 3 的次方（无论我们正在考虑的棋盘位置），然后将其添加到一些"result" 号。下面是一些（非常未经测试的）示例代码：

#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

不幸的是，由于计算机偏向于二进制，因此您只能对位移位非常了解。因此，此代码中的 for 循环（就性能而言，在 C 中比在 python 中稍微不那么粗暴）。

请注意，您使用此方法的范围有限；如您所知，您不能用这种方法代表整个板（因为 64 位整数没有 3^64 个可能的值）。

希望这比字符串方法更适合您！

Answer 2

实际上，您需要将棋盘状态存储在 unsigned longs 中的 base-4 中，并将每个棋盘行填充为 unsigned longs 的整数。这将为您提供最佳的内存位置，非常快速地访问电路板单元，但使用的 RAM 比三元封装多 26.2%。

要将电路板状态存储在二进制文件中，您可以将 5 个三进制数字（五个电路板单元状态）打包到每个 8 位字节中。这仅比三元打包多使用 5.1% 的内存，并且实现起来简单且健壮。特别是，这样你就不需要担心字节顺序（endianness）。

纯三进制打包的问题是每个以 3 为基数的数字都会影响表示相同数值的大多数二进制数字。例如，3⁸ = 30000000₃ = 6561 = 1100110100001₂。这意味着提取 base-3 数字的唯一实用方法是通过重复除法和模数（乘以 3）。

描述一块N×M的板子，三元打包解包函数本质上就是O (N²M² ), 因此随着电路板尺寸的增加越来越慢。通过使用压缩库（例如，liblzma）使用更少的 CPU 时间，您可能会获得更好的节省。对于许多电路板配置，运行长度编码也可能工作良好。

这是最多 16777215×16777215 个单元的电路板的示例实现（仅测试最多 32768×32768 个单元）：

#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;
}

board_init()函数初始化一个棋盘，board_save()将棋盘状态保存到一个流中，包括棋盘大小，以可移植的二进制格式（每个文件将在两个big- endian 和 little-endian 架构），并且 board_load() 将从流中加载以前保存的板。如果成功，它们都是 return 0，如果错误则非零。

get_cell() 和 set_cell() 函数是静态内联访问器函数，用于检查和设置板上各个单元格的状态。

正如我最初建议的那样，这个在 RAM 中每个单元格使用 2 位（每个字节 4 个单元格），存储到文件时每个字节使用 5 个单元格。

示例程序采用三个命令行参数：文件名、行数和列数。它将生成该大小的随机状态，将其保存到命名文件中，将其从命名文件读回到单独的板中，最后比较板状态，以验证实现的功能是否正常工作。

Answer 3

如果你的硬件有一个快速的popcount操作，那么你可以将一块nspaces表示为2n 位值⟨mask,colour⟩，其中第二个值保证在[0, 2^{popcount(mask)}] 如果方格被占用，则该方格对应的位位置第一个值为1；如果第j格有白子，则j对应的位位置第二个值为1。为了访问 colour 中的位，使用此函数很有用 returns 给定 colour 中的位位置]mask 和掩码中对应于掩码中 1 位的位位置（即对应于被占用方块的位）：

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

(也就是统计mask中指定位置后面的1位的个数。)

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

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

虽然可以利用这种安排在 O(n) 时间内相当费力地计算索引（在 mask 字段），最简单和最快的解决方案是使用 2ⁿ-元素固定查找 table base，其大小远小于3ⁿ数据tables。 mask 的每个值的基值是通过简单地为每个值累加适当的 2 的幂来计算的：

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[=95=中添加一块彩色col（WHITE = 1, BLACK = 0） ]，你会这样做：

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

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

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

其他操作同样简单。

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

索引编码示例：

为了简单起见，使用 n=4，base 查找 table 是：

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

Answer 4

如何存储您要转换的内容？使用下面的方案，一行中每增加 8 位，将花费数组（或散列 table）中的 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));

位板到位板（三元位板）转换

Bitboard to titboard (ternary bitboard) conversion

c

algorithm

math

ternary

bitboard