Преобразование битборда в титборд (троичный битборд)

Question

Во многих настольных играх (таких как шашки, го и отелло / реверси) каждый квадрат может быть представлен тремя состояниями: белый , черный или пустой .Платы

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

Answer 2

На практике вы захотите сохранить состояние платы в base-4, упакованном в unsigned long с, с каждой строкой платы, дополненной целым числом unsigned long с.Это обеспечит вам лучшее расположение памяти, очень быстрый доступ к ячейкам платы, но использует ОЗУ на 26,2% больше, чем троичная упаковка.

Чтобы сохранить состояние платы в двоичном файле, вы можете упаковать 5 троичных цифр (пятьсостояния ячейки платы) в каждый 8-битный байт.Это использует только 5,1% больше памяти, чем троичная упаковка, и является простым и надежным в реализации.В частности, таким образом вам не нужно беспокоиться о порядке следования байтов (порядковый номер байтов).

Проблема с чистой троичной упаковкой заключается в том, что каждая цифра в Base-3 влияет на большинство двоичных цифр, представляющих одно и то же числовое значение.Например, 3 ⁸ = 30000000 ₃ = 6561 = 1100110100001 ₂ .Это означает, что единственный практический способ извлечь цифры из базы-3 - это повторное деление и модуль (на 3).

Для описания доски размером N × M троичная функция упаковки и распаковки будет по существу O ( N ² M ² ), ипоэтому все медленнее и медленнее с увеличением размера платы.Вероятно, вы получите лучшую экономию за счет использования библиотеки сжатия (скажем, liblzma ), использующей меньше процессорного времени.Для многих конфигураций плат кодирование по длине прогона также может работать хорошо.

Вот пример реализации для плат до 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() сохраняет состояние платы в поток, включая размер платы, в переносимом двоичном формате (каждый файл будет генерировать одну и ту же плату как с прямым и обратным порядком байтов)архитектур), и board_load() загрузит ранее сохраненную доску из потока.Все они возвращают 0 в случае успеха, ненулевое значение в случае ошибки.

Функции get_cell() и set_cell() являются статическими встроенными функциями доступа для проверки и установки состояния отдельных ячеек на плате.

Как я первоначально предположил, этот использует 2 бита на ячейку в ОЗУ (4 ячейки на байт) и 5 ​​ячеек на байт при сохранении в файл.

В примере программы используются три параметра командной строки:имя файла, количество строк и количество столбцов.Он сгенерирует случайное состояние такого размера, сохранит его в именованный файл, прочитает его обратно из именованного файла на отдельную плату и, наконец, сравнит состояния платы, чтобы проверить, работают ли реализованные функции правильно.

Answer 3

Если ваше оборудование выполняет быструю операцию popcount , то вы можете представить доску из n пробелов в виде 2 n -битных значений ⟨ маска, color ⟩, где второе значение гарантированно находится в диапазоне [0, 2 ^{popcount ( mask )} ] Первое значение 1в битовой позиции, соответствующей квадрату, если квадрат занят;второе значение равно 1 в битовой позиции, соответствующей j , если j -й занятый квадрат имеет белый фрагмент.Чтобы получить доступ к битам в цвет , полезно иметь эту функцию, которая возвращает битовую позицию в цвет заданную маску и битовую позицию в маске, которая соответствует1-бит в маске (т. е. бит, соответствующий занятому квадрату):

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

(Другими словами, он подсчитывает число одного бита в mask послеуказанная позиция.)

Затем можно легко превратить пару ⟨ mask , color into в одно число в диапазоне [0, 3 ⁿ -1] в виде предварительно вычисленной таблицы поиска, содержащей базовые индексы.Когда я первоначально думал об этой системе, я думал в терминах n + 1 составных таблиц, каждая из которых соответствует отдельному поп-счету.Это концептуально неплохо, поскольку число возможных раскрасок кода с помощью popcount i , очевидно, равно 2 ⁱ , а количество масок с popcount i is C ( n , i ) (используя C () в качестве функции биномиального коэффициента, поскольку здесь нет MathJax),Прекрасная личность:

, вероятно, менее известна, чем другие биномиальные личности.

Хотя можно воспользоваться преимуществамиЭта схема довольно трудоемкого вычисления индекса за O ( n ) времени (бит за битом в поле mask ), самое простое и быстрое решение - использовать 2 ⁿ -элемент с фиксированной таблицей поиска base , размер которого намного меньше, чем у таблиц данных 3 ⁿ .Базовое значение вычисляется для каждого значения 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

Для другого примера, чтобы добавить кусок, окрашенный col (WHITE = 1, BLACK =0) к незанятому в данный момент квадрату i вы должны сделать:

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

, эффективно смещая первую часть color влево на один бит, чтобы вставить новый бит,Если бы квадрат уже был занят, вы бы избежали сдвига:

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 = незанятый, B = черный, W = белый (и при условии, как указано выше, чтоБелый - 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

Преобразование из строки в целое и обратно действительно будет неэффективным.

Если вам просто нужно закодировать значения, полезно подумать о них с точки зрения действительных чисел, которые они представляют.Например, при рассмотрении восьми строк на доске, состояние первой позиции фактически равно boardState % 3;мы можем использовать соглашение о том, что черная фигура находится на 1, белая фигура на 2 и пустое значение на 0.Для второго оно становится (boardState % 9)/3, для третьего (boardState % 27) / 3 и т. Д.

Итак, для кодирования мы можем расширить это мышление: мы берем либо 0, 1, либо 2, умножаем его на3 к степени (какую бы позицию платы мы не рассматривали), и прибавьте ее к некоторому «результату» числа.Ниже приведен пример (ОЧЕНЬ непроверенный) примера кода:

#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 возможных значений).

Надеюсь, это более поддается вам, чемструнный подход!