1

我正在努力寻找一种计算正方形对角线的 64 位表示的有效方法。

有问题的游戏是一款名为 Othello 或 Reversi 的棋盘游戏。我目前正在研究一种确定作品稳定性的方法。稳定的棋子可以定义为不能翻转的棋子。我正在处理的当前问题可以定义为：“如果所有四个方向的所有方格都被占用，则无法翻转一块。”

因此，例如，如果棋盘如下所示，则无法捕获标有 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 . . 
 */

其中 x 表示该位置存在一块（无论其颜色如何）。由于该棋子被各个方向的棋子包围，因此无法捕获。

垂直线很容易计算。在一个 8x8 的嵌套 for 循环中，可以通过 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 会将线下移 1。

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 . . . . . . . 
 */

因此，移位一位会将线向右移动一位。

要找到他们的组合光标，我只需 OR 结果：

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 循环，并且此操作将执行数千次，这在计算上不是最优的。

有人知道从单个正方形计算对角线的方法或计算对角线数组中相应索引的方法吗？

非常感谢您的帮助。

4

1 回答 1

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 的倍数），额外的位总是被推离单词的末尾。二次对角线也是如此，但具有反等价性。

如果我们从“主对角线”（左上到右下）和“次对角线”（右上到左下角）开始，我们可以使用 using 来上下移动它们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？

有趣的小问题，谢谢:)

于 2019-05-19T01:10:55.100 回答