在位板中查找对角线的计算可行方法
Computationally feasible way of finding diagonals in a bitboard
我正在努力寻找一种计算正方形对角线的 64 位表示的有效方法。
有问题的游戏是一种名为 Othello 或 Reversi 的棋盘游戏。我目前正在研究一种确定作品稳定性的方法。稳定的棋子可以定义为不能翻转的棋子。我正在处理的当前问题可以定义为："a piece cannot be flipped if all squares in all four directions are occupied."
因此，例如，如果棋盘如下所示，则无法捕获标记为 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 位会使行向下移动一位。
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 循环，并且这个操作将被执行数千次，这在计算上不是最优的。
有人知道从单个正方形计算对角线的方法或计算对角线数组中相应索引的方法吗？
非常感谢您的帮助。
I don't know how to match the index of the array with the (i, j) index. For example, if a square is on the index (2, 1), the corresponding index should be [1] in the array. But if a square is on (3, 2) the index is the array should also be [1]. And if a square is on (1,1), ... (7, 7), (8, 8), the index should be [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。同样，我们可以对 "primary diagonal" 的距离做 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...但是我们可以做得更好。您最初移动对角线的想法很好，但需要付出一些努力才能弄清楚如何有效地避免无关的位环绕网格。
需要注意的关键是在网格上移动主对角线向右相当于将它移动向上，然后移动它left 相当于将它移动 down （假设位刚好从网格上掉下来）。当然，当我们实际使用向左或向右移位时，我们会得到位回绕，但是当我们向上或向下移动 时 （使用 8 的倍数和 left/right），额外的位 总是 被推到单词的末尾。次对角线也是如此，但具有逆等价性。
如果我们从 "primary diagonal"（top-left 到 bottom-right）和 "secondary diagonal"（top-right 到 bottom-left）开始，我们可以使用 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 掩盖你的董事会价值，看看它是否是 "stable" 像这样 board & m == m?
有趣的小问题，谢谢:)
我正在努力寻找一种计算正方形对角线的 64 位表示的有效方法。
有问题的游戏是一种名为 Othello 或 Reversi 的棋盘游戏。我目前正在研究一种确定作品稳定性的方法。稳定的棋子可以定义为不能翻转的棋子。我正在处理的当前问题可以定义为："a piece cannot be flipped if all squares in all four directions are occupied."
因此，例如，如果棋盘如下所示，则无法捕获标记为 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 位会使行向下移动一位。
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 循环，并且这个操作将被执行数千次，这在计算上不是最优的。
有人知道从单个正方形计算对角线的方法或计算对角线数组中相应索引的方法吗？
非常感谢您的帮助。
I don't know how to match the index of the array with the (i, j) index. For example, if a square is on the index (2, 1), the corresponding index should be [1] in the array. But if a square is on (3, 2) the index is the array should also be [1]. And if a square is on (1,1), ... (7, 7), (8, 8), the index should be [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。同样，我们可以对 "primary diagonal" 的距离做 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...但是我们可以做得更好。您最初移动对角线的想法很好，但需要付出一些努力才能弄清楚如何有效地避免无关的位环绕网格。
需要注意的关键是在网格上移动主对角线向右相当于将它移动向上，然后移动它left 相当于将它移动 down （假设位刚好从网格上掉下来）。当然，当我们实际使用向左或向右移位时，我们会得到位回绕，但是当我们向上或向下移动 时 （使用 8 的倍数和 left/right），额外的位 总是 被推到单词的末尾。次对角线也是如此，但具有逆等价性。
如果我们从 "primary diagonal"（top-left 到 bottom-right）和 "secondary diagonal"（top-right 到 bottom-left）开始，我们可以使用 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 掩盖你的董事会价值，看看它是否是 "stable" 像这样 board & m == m?
有趣的小问题，谢谢:)