查找（n x n）井字棋盘中所有单元格二进制值的算法？
Algorithm to find binary value of all cells in (n x n) Tic-tac-toe board?
我发现了这个 great answer by Gary C，它使用按位运算符和最少数量的比较来检查井字游戏的胜利。唯一的问题是每个单元格的值需要在开始时进行硬编码。
例如他说单元格[0][0]将被赋予
的值
100 0 000 0 000 0 100 0 000 0 000 100 0 000 0
其中每组 3 位代表
row1 0 row2 0 row3 0 column1 0 column2 0 column3 0 diag 0 antiDiag 0
，后面的 0 作为填充（对他的解决方案的其余部分很重要）。
这是因为cell[0][0]占据了row1、column1以及对角线的第一个位置。
这个任务虽然麻烦，但对于 3x3 板来说肯定是可行的，但是问题是如何对一般的 nxn 板执行此操作。
我假设我们必须关闭的输入是：
a) 单元格的行和列索引。
b)n的值，它告诉我们每组必须有n位，还有一个额外的位用于填充。
我知道这是一个非常具体的解决方案中的一个非常具体的场景。不过他的回答相当精彩，让人不禁好奇到底是如何一路落实的。
半回答和建议也很受欢迎，因为这将有助于讨论。
简答...
相信最好的方法是 Gary C and alexsalo 之间的混合，特别是利用 alexsalo 的 X 和 O 的位板表示，但采用与 Gary C 的方法类似的技术来确定获胜位置。这需要更多的位来确定最后一步是否是赢家，但很容易扩展为 N x N tic-tac-toe...
N x N tic-tac-toe 所需的位数，作者：Gary C
使用 Gary C 的方案，N x N tic-tac-toe 将涉及代表行、列和对角线的位，以及间隔位。 X 和 O 都需要这种按位表示。通过一些数学运算，我们可以确定每个玩家所需的位数。首先，表示行、列和对角线的位数...
- N 行 * N 列 *（1 组行 + 1 组列）+ 2 诊断 * N
...加上代表间隔符的位数...
- N 行 + N 列 + 2 个诊断
以下 table 显示了每个玩家玩 N x N 版本的井字游戏所需的总位数：
N
Bits Required
Spacer
Total
3
24
8
32
4
40
10
50
5
60
12
72
6
84
14
98
7
112
16
128
8
144
18
162
9
180
20
200
10
220
22
242
11
264
24
288
12
312
26
338
13
364
28
392
14
420
30
450
15
480
32
512
16
544
34
578
除了使用 BigInt 之外，Javascript 支持的最大整数是 64 位 BigUint64Array 值类型，因此已经从 5 x 5 板开始，即将进行的移位操作已经需要在各个二进制数之间进行移位.当然可以使用 BigInt，尽管可能会影响性能。
N x N tic-tac-toe 所需的位数，作者：alexsalo
alexsalo 的方案只需要每方块一位，因此对于 N x N 板，表示 X 或 O 的位数是...
N
Bits Required
3
9
4
16
5
25
6
36
7
49
8
64
9
81
10
100
11
121
12
144
13
169
14
196
15
225
16
256
在这种情况下，单个 BigUint64Array 值最多可以处理 8 x 8 板。同样，在那之后，除非使用 BigInt，否则将需要多个二进制值。
测试获胜者
当然，权衡是使用更简单的数据结构，获胜者的测试成本更高一些，但如前所述，对于可变大小，这更容易扩展 tic-tac-toe木板。
例如，一个 4 x 4 tic-tac-toe 的棋盘将用于显示算法，以按行、列和对角线检查获胜者。这些算法本质上是 O(N) 的，因此很容易为更大的板子进行算法扩展，尤其是在使用 BigInt 时。例如，如果使用 BigUint64Array 值，那么任何位移都将涉及基础整数值之间的溢出，从而使按位算法稍微复杂一些，但不会过于复杂。
例如，对 64 位 Uint 进行位移很简单，但对于 128 位 Uint 则不然，因为没有 128 位数字的内部表示，除了 BigInt，在这种情况下可能会影响性能.用两个 64 位 Uint 表示一个 128 位 Uint 是可能的，但是，如果在第一个 64 位 Uint 中右移 10 位，则必须将最右边的 10 位移入第二个 64 位 Uint...
回到通过示例测试获胜者，假设我们的 4 x 4 棋盘游戏状态当前是...
a b c d
- - - -
1: O X O O
2: X X X
3: X X O O
4: X
那么 X 和 O 的表示将是...
- X位板：0100 0111 1100 0100
- O位板：1011 0000 0011 0000
检查行中的赢家...
确定玩家是否在同一行中有 4 个，方法是简单地将一行中的位组合在一起，然后检查结果是否为 non-zero。
( bitboard >>> 3) & (bitboard >>> 2) & (bitboard >>> 1) & bitboard & 0001 0001 0001 0001
例如，连续检查 4 个 X 位板...
abcd abcd abcd abcd
-------------------------------------
bitboard >>> 3: 0000 1000 1111 1000
bitboard >>> 2: 0001 0001 1111 0001
bitboard >>> 1: 0010 0011 1110 0010
bitboard: 0100 0111 1100 0100
mask: 0001 0001 0001 0001
-------------------------------------
ANDed together: 0000 0000 0000 0000 => there are no 4 X's in a single Row.
向下查看每一列 'd' 将显示与位板行相同的序列。即，第一组列 'd' 是 0100，第二组是 0111，等等，这与代表每一行的 4 位的 X 位板组相同...
还要注意，如果没有 Gary C 间隔位，即使有 5 个连续的 1，我们仍然会得到正确的结果，因为这些位实际上被移位并与 'd' 列进行了逻辑运算，然后最终掩码确保了我们只考虑列 'd'，而不是第三组中的误报，其中列 'a' 似乎连续有 4 个。
检查列中的获胜者
通过简单地对同一列中的所有位进行移位和与运算，然后检查结果是否为 non-zero。
来确定玩家是否在一列中有 4
bitboard & (bitboard >>> 4) & (bitboard >>> 8) & (bitboard >>> 12)
例如，检查列中 4 的 X 位板...
abcd abcd abcd abcd
-------------------------------------
bitboard: 0100 0111 0100 0100
bitboard >>> 4: 0000 0100 0111 0100
bitboard >>> 8: 0000 0000 0100 0111
bitboard >>> 12: 0000 0000 0000 0100
-------------------------------------
ANDed together: 0000 0000 0000 0100 => column 'b' has 4 in a col.
请注意，确定玩家是否在一列中有 4 个的逻辑可以优化为 O(log N)...
检查对角线中的获胜者
类似于检查列中的获胜者，但将对角线位合并到列 'a' 和 'd'...
(bitboard >>> 12) & (bitboard << 1 | bitboard >>> 1) >>> 8 & (bitboard << 2 | bitboard >>> 2) >>> 4 & (bitboard << 3 | bitboard >>> 3)
...和列检查一样，结果将是最低 4 位，特别是列 'a' 和 'd'。
底层实现...
建议从 BigInt 表示开始位板，因为这将简化基于 N x N 板敲定特定算法的工作，然后在寻求最佳性能时移植到使用 32 或 64 位 Uint。
我发现了这个 great answer by Gary C，它使用按位运算符和最少数量的比较来检查井字游戏的胜利。唯一的问题是每个单元格的值需要在开始时进行硬编码。
例如他说单元格[0][0]将被赋予
的值100 0 000 0 000 0 100 0 000 0 000 100 0 000 0
其中每组 3 位代表
row1 0 row2 0 row3 0 column1 0 column2 0 column3 0 diag 0 antiDiag 0
，后面的 0 作为填充（对他的解决方案的其余部分很重要）。 这是因为cell[0][0]占据了row1、column1以及对角线的第一个位置。
这个任务虽然麻烦，但对于 3x3 板来说肯定是可行的，但是问题是如何对一般的 nxn 板执行此操作。
我假设我们必须关闭的输入是： a) 单元格的行和列索引。 b)n的值，它告诉我们每组必须有n位，还有一个额外的位用于填充。
我知道这是一个非常具体的解决方案中的一个非常具体的场景。不过他的回答相当精彩，让人不禁好奇到底是如何一路落实的。 半回答和建议也很受欢迎，因为这将有助于讨论。
简答...
相信最好的方法是 Gary C and alexsalo 之间的混合，特别是利用 alexsalo 的 X 和 O 的位板表示，但采用与 Gary C 的方法类似的技术来确定获胜位置。这需要更多的位来确定最后一步是否是赢家，但很容易扩展为 N x N tic-tac-toe...
N x N tic-tac-toe 所需的位数，作者：Gary C
使用 Gary C 的方案，N x N tic-tac-toe 将涉及代表行、列和对角线的位，以及间隔位。 X 和 O 都需要这种按位表示。通过一些数学运算，我们可以确定每个玩家所需的位数。首先，表示行、列和对角线的位数...
- N 行 * N 列 *（1 组行 + 1 组列）+ 2 诊断 * N
...加上代表间隔符的位数...
- N 行 + N 列 + 2 个诊断
以下 table 显示了每个玩家玩 N x N 版本的井字游戏所需的总位数：
| N | Bits Required | Spacer | Total |
|---|---|---|---|
| 3 | 24 | 8 | 32 |
| 4 | 40 | 10 | 50 |
| 5 | 60 | 12 | 72 |
| 6 | 84 | 14 | 98 |
| 7 | 112 | 16 | 128 |
| 8 | 144 | 18 | 162 |
| 9 | 180 | 20 | 200 |
| 10 | 220 | 22 | 242 |
| 11 | 264 | 24 | 288 |
| 12 | 312 | 26 | 338 |
| 13 | 364 | 28 | 392 |
| 14 | 420 | 30 | 450 |
| 15 | 480 | 32 | 512 |
| 16 | 544 | 34 | 578 |
除了使用 BigInt 之外，Javascript 支持的最大整数是 64 位 BigUint64Array 值类型，因此已经从 5 x 5 板开始，即将进行的移位操作已经需要在各个二进制数之间进行移位.当然可以使用 BigInt，尽管可能会影响性能。
N x N tic-tac-toe 所需的位数，作者：alexsalo
alexsalo 的方案只需要每方块一位，因此对于 N x N 板，表示 X 或 O 的位数是...
| N | Bits Required |
|---|---|
| 3 | 9 |
| 4 | 16 |
| 5 | 25 |
| 6 | 36 |
| 7 | 49 |
| 8 | 64 |
| 9 | 81 |
| 10 | 100 |
| 11 | 121 |
| 12 | 144 |
| 13 | 169 |
| 14 | 196 |
| 15 | 225 |
| 16 | 256 |
在这种情况下，单个 BigUint64Array 值最多可以处理 8 x 8 板。同样，在那之后，除非使用 BigInt，否则将需要多个二进制值。
测试获胜者
当然，权衡是使用更简单的数据结构，获胜者的测试成本更高一些，但如前所述，对于可变大小，这更容易扩展 tic-tac-toe木板。 例如，一个 4 x 4 tic-tac-toe 的棋盘将用于显示算法，以按行、列和对角线检查获胜者。这些算法本质上是 O(N) 的，因此很容易为更大的板子进行算法扩展，尤其是在使用 BigInt 时。例如，如果使用 BigUint64Array 值，那么任何位移都将涉及基础整数值之间的溢出，从而使按位算法稍微复杂一些，但不会过于复杂。
例如，对 64 位 Uint 进行位移很简单，但对于 128 位 Uint 则不然，因为没有 128 位数字的内部表示，除了 BigInt，在这种情况下可能会影响性能.用两个 64 位 Uint 表示一个 128 位 Uint 是可能的，但是，如果在第一个 64 位 Uint 中右移 10 位，则必须将最右边的 10 位移入第二个 64 位 Uint...
回到通过示例测试获胜者，假设我们的 4 x 4 棋盘游戏状态当前是...
a b c d
- - - -
1: O X O O
2: X X X
3: X X O O
4: X
那么 X 和 O 的表示将是...
- X位板：0100 0111 1100 0100
- O位板：1011 0000 0011 0000
检查行中的赢家...
确定玩家是否在同一行中有 4 个，方法是简单地将一行中的位组合在一起，然后检查结果是否为 non-zero。
( bitboard >>> 3) & (bitboard >>> 2) & (bitboard >>> 1) & bitboard & 0001 0001 0001 0001
例如，连续检查 4 个 X 位板...
abcd abcd abcd abcd
-------------------------------------
bitboard >>> 3: 0000 1000 1111 1000
bitboard >>> 2: 0001 0001 1111 0001
bitboard >>> 1: 0010 0011 1110 0010
bitboard: 0100 0111 1100 0100
mask: 0001 0001 0001 0001
-------------------------------------
ANDed together: 0000 0000 0000 0000 => there are no 4 X's in a single Row.
向下查看每一列 'd' 将显示与位板行相同的序列。即，第一组列 'd' 是 0100，第二组是 0111，等等，这与代表每一行的 4 位的 X 位板组相同...
还要注意，如果没有 Gary C 间隔位，即使有 5 个连续的 1，我们仍然会得到正确的结果，因为这些位实际上被移位并与 'd' 列进行了逻辑运算，然后最终掩码确保了我们只考虑列 'd'，而不是第三组中的误报，其中列 'a' 似乎连续有 4 个。
检查列中的获胜者
通过简单地对同一列中的所有位进行移位和与运算，然后检查结果是否为 non-zero。
来确定玩家是否在一列中有 4bitboard & (bitboard >>> 4) & (bitboard >>> 8) & (bitboard >>> 12)
例如，检查列中 4 的 X 位板...
abcd abcd abcd abcd
-------------------------------------
bitboard: 0100 0111 0100 0100
bitboard >>> 4: 0000 0100 0111 0100
bitboard >>> 8: 0000 0000 0100 0111
bitboard >>> 12: 0000 0000 0000 0100
-------------------------------------
ANDed together: 0000 0000 0000 0100 => column 'b' has 4 in a col.
请注意，确定玩家是否在一列中有 4 个的逻辑可以优化为 O(log N)...
检查对角线中的获胜者
类似于检查列中的获胜者，但将对角线位合并到列 'a' 和 'd'...
(bitboard >>> 12) & (bitboard << 1 | bitboard >>> 1) >>> 8 & (bitboard << 2 | bitboard >>> 2) >>> 4 & (bitboard << 3 | bitboard >>> 3)
...和列检查一样，结果将是最低 4 位，特别是列 'a' 和 'd'。
底层实现...
建议从 BigInt 表示开始位板，因为这将简化基于 N x N 板敲定特定算法的工作，然后在寻求最佳性能时移植到使用 32 或 64 位 Uint。