Вычислительный способ нахождения диагоналей в битборде

Question

Я изо всех сил пытаюсь найти эффективный способ вычисления 64-битного представления диагоналей квадрата.

Рассматриваемая игра - настольная игра под названием «Отелло» или «Реверси». В настоящее время я работаю над методом определения стабильности произведения. Стабильный кусок может быть определен как кусок, который нельзя перевернуть. Текущая проблема, над которой я работаю, может быть определена следующим образом: «кусок нельзя перевернуть, если заняты все квадраты во всех четырех направлениях».

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

/*      1 2 3 4 5 6 7 8 
 *   1  . . x . . . x . 
 *   2  . . x . . x . . 
 *   3  x . x . x . . . 
 *   4  . x x x . . . . 
 *   5  x x A x x x x x 
 *   6  . x x x . . . . 
 *   7  x . x . x . . . 
 *   8  . . x . . x . . 
 */

Где х обозначает наличие фигуры в этом положении (независимо от ее цвета). Поскольку часть окружена частями во всех направлениях, она не может быть захвачена.

Вертикальные линии легко рассчитать. Во вложенном цикле for 8x8 следующая вертикальная линия может быть найдена с помощью ver0 >> j, а следующая горизонтальная строка может быть найдена с помощью hor0 >> i * 8.

const unsigned long long hor0 = 255ULL;
const unsigned long long ver0 = 72340172838076673ULL;
for (i = 0; i < 8; i++) {
    for (j = 0; j < 8; j++) {
    currHor = hor0 << i;
    currVer = ver0 << j;
    }
}

В качестве наглядного примера hor0 выглядит так:

/*      1 2 3 4 5 6 7 8 
 *   1  x x x x x x x x 
 *   2  . . . . . . . . 
 *   3  . . . . . . . . 
 *   4  . . . . . . . . 
 *   5  . . . . . . . . 
 *   6  . . . . . . . . 
 *   7  . . . . . . . . 
 *   8  . . . . . . . . 
 */

поэтому сдвиг на 8 сместит линию на единицу.

ver0 выглядит так:

/*      1 2 3 4 5 6 7 8 
 *   1  x . . . . . . . 
 *   2  x . . . . . . . 
 *   3  x . . . . . . . 
 *   4  x . . . . . . . 
 *   5  x . . . . . . . 
 *   6  x . . . . . . . 
 *   7  x . . . . . . . 
 *   8  x . . . . . . . 
 */

Таким образом, сдвиг на единицу переместит линию на единицу.

Чтобы найти их комбинированный курсор, я просто ИЛИ результаты:

currCursor = (currHor | currVer);

Теперь начинается настоящая проблема. Чтобы определить стабильность, мне нужны все четыре направления. Я не уверен, как посчитать диагональные линии с помощью только позиции (i, j).

Моей первой попыткой было использование битовых сдвигов. Это ужасно провалилось, поскольку сдвиги привели к отражению, когда я не хочу мусорных битов.

Моя вторая попытка состояла в том, чтобы просто поместить все диагональные линии в массив и использовать индексы, чтобы найти соответствующую линию. Массив довольно большой, но вот пример того, как выглядят некоторые элементы (только левые диагонали):

const unsigned long long rightDiagonals[15] = { \
    9241421688590303745ULL, \
/*      1 2 3 4 5 6 7 8 
 *   1  x . . . . . . . 
 *   2  . x . . . . . . 
 *   3  . . x . . . . . 
 *   4  . . . x . . . . 
 *   5  . . . . x . . . 
 *   6  . . . . . x . . 
 *   7  . . . . . . x . 
 *   8  . . . . . . . x
 *   [0] //This is the index in the array.
 */
    36099303471055874ULL, \
/*      1 2 3 4 5 6 7 8 
 *   1  . x . . . . . . 
 *   2  . . x . . . . . 
 *   3  . . . x . . . . 
 *   4  . . . . x . . . 
 *   5  . . . . . x . . 
 *   6  . . . . . . x . 
 *   7  . . . . . . . x 
 *   8  . . . . . . . . 
 *   [1] 
 */
...
    144396663052566528ULL, \
/*      1 2 3 4 5 6 7 8 
 *   1  . . . . . . . . 
 *   2  . . . . . . . . 
 *   3  . . . . . . . . 
 *   4  . . . . . . . . 
 *   5  . . . . . . . . 
 *   6  . . . . . . . . 
 *   7  x . . . . . . . 
 *   8  . x . . . . . . 
 *   [13] 
 */
    72057594037927936ULL}
/*      1 2 3 4 5 6 7 8 
 *   1  . . . . . . . . 
 *   2  . . . . . . . . 
 *   3  . . . . . . . . 
 *   4  . . . . . . . . 
 *   5  . . . . . . . . 
 *   6  . . . . . . . . 
 *   7  . . . . . . . . 
 *   8  x . . . . . . . 
 *   [14] 
 */

Я не знаю, как сопоставить индекс массива с индексом (i, j). Например, если квадрат находится в индексе (2, 1), соответствующий индекс должен быть [1] в массиве. Но если квадрат находится на (3, 2), индекс массива также должен быть [1]. И если квадрат находится на (1,1), ... (7, 7), (8, 8), индекс должен быть [0].

Я не могу определить способ легко найти линию. Одна вещь, о которой я подумал, это получить 64-битное представление текущего квадрата и ИЛИ его с пересечением двух линий. Проблема в том, что для этого потребуется цикл for, и эта операция будет выполняться тысячи раз, что в вычислительном отношении не оптимально.

Кто-нибудь знает способ вычисления диагоналей из одного квадрата или способ вычисления соответствующего индекса в массиве диагоналей?

Ваша помощь очень ценится.

Answer 1

Я не знаю, как сопоставить индекс массива с индексом (i, j). Например, если квадрат находится в индексе (2, 1), соответствующий индекс должен быть [1] в массиве. Но если квадрат находится на (3, 2), индекс массива также должен быть [1]. И если квадрат равен (1,1), ... (7, 7), (8, 8), индекс должен быть [0].

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

    0 1 2 3 4 5 6 7

0   . . x . . . . .
1   . . . x . . . .
2   . . . . x . . .
3   . . . . . x . .
4   . . . . . . x .
5   . . . . . . . x
6   . . . . . . . .
7   . . . . . . . .

Если вы проведете линию от левого края до диагонали и до нижнего края (расстояние до Манхэттена), вы заметите, что все точки на линии имеют одинаковое расстояние 7 - x + y. Точно так же мы можем сделать x - y для расстояния от «первичной диагонали». Следующее иллюстрирует это для всех точек:

    0 1 2 3 4 5 6 7

0   0 1 2 3 4 5 6 7
1  -1 0 1 2 3 4 5 6
2  -2-1 0 1 2 3 4 5
3  -3-2-1 0 1 2 3 4
4  -4-3-2-1 0 1 2 3
5  -5-4-3-2-1 0 1 2
6  -6-5-4-3-2-1 0 1
7  -7-6-5-4-3-2-1 0

В этот момент вы можете пойти и сопоставить свои 16 предварительно вычисленных диагоналей с x - y ... Однако мы можем сделать намного лучше. Ваша первоначальная идея смещения диагоналей хороша, но для выяснения того, как эффективно избежать наложения посторонних битов вокруг сетки, требуются некоторые усилия.

Ключевым моментом, на который следует обратить внимание, является то, что перемещение первичной диагонали вправо по сетке эквивалентно ее перемещению вверх , а перемещение влево эквивалентно переместив его вниз (при условии, что биты просто падают с сетки). Конечно, когда мы на самом деле используем битовый сдвиг влево или вправо, мы получаем обтекание битами, однако, когда мы сдвигаем вверх или вниз (используя кратное 8 с влево / вправо), дополнительные биты всегда оттолкнуться от концов слова. То же самое верно для вторичной диагонали, но с обратной эквивалентностью.

Если мы начнем с «первичной диагонали» (сверху-слева-вниз-справа) и «вторичной диагонали» (сверху-справа-внизу слева), мы можем сдвинуть их вверх и вниз, используя x - y для получения все остальные комбинации диагоналей, ИЛИ их вместе, как вы делаете с ортогональными линиями:

const uint64_t
    HP = 0xff00000000000000, // horizontal primary
    VP = 0x8080808080808080, // vertical primary
    DP = 0x8040201008040201, // diagonal primary
    DS = 0x0102040810204080; // diagonal secondary

uint64_t stable (int x, int y) {
    uint64_t m =
        VP >> x | HP >> (y << 3);
    if (x >= y) {
        m |= DP << ((x - y) << 3);
    } else {
        m |= DP >> ((y - x) << 3);
    }
    int z = 7 - x;
    if (z >= y) {
        m |= DS << ((z - y) << 3);
    } else {
        m |= DS >> ((y - z) << 3);
    }
    return m;
}

void main () {
    for (int y = 0; y < 8; y ++) {
        for (int x = 0; x < 8; x ++) {
            uint64_t m = stable(x, y);
            printf("\n%d,%d:\n", x, y);
            for (int i = 7; i >= 0; i --) {
                int line = m >> (i << 3);
                printf("%c %c %c %c %c %c %c %c\n",
                    line & 0x80 ? 'x' : '.',
                    line & 0x40 ? 'x' : '.',
                    line & 0x20 ? 'x' : '.',
                    line & 0x10 ? 'x' : '.',
                    line & 0x08 ? 'x' : '.',
                    line & 0x04 ? 'x' : '.',
                    line & 0x02 ? 'x' : '.',
                    line & 0x01 ? 'x' : '.'
                );
            }
        }
    }
}

Все << 3 только для эффективности, это эквивалентно * 8.

Я предполагаю, что вы захотите замаскировать значение вашей доски с помощью m, чтобы увидеть, является ли она "стабильной", как это так board & m == m?

Забавная маленькая проблема, спасибо:)