查找（nxn）井字棋板中所有單元格的二進制值的演算法？

我發現Gary C 的這個很好的答案，它使用按位運算子和最少的比較來檢查井字游戲的勝利。唯一的問題是每個單元格的值需要在開始時進行硬編碼。

例如，正如他所說，cell[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 位，以及一個額外的位用于填充。

我知道這是一個非常具體的解決方案中的一個非常具體的場景。然而，他的回答非常出色，人們不禁想知道如何真正實作它。半答案和建議也值得贊賞，因為它將有助于討論。

uj5u.com熱心網友回復：

簡短的回答...

相信最好的課程是Gary C和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 個診斷

下表顯示了 N x N 版本的井字游戲每個玩家所需的總位元數：

在使用 BigInt 之外，Javascript 支持的最大整數是 64 位 BigUint64Array 值型別，因此已經從 5 x 5 板開始，即將進行的按位移位操作將需要在各個二進制數之間進行移位。當然可以使用 BigInt，盡管可能會影響性能。

alexsalo 的 N x N tic-tac-toe 所需的位數

來自 alexsalo 的方案只需要每平方一位，因此表示 N x N 板的 X 或 O 的位數是......

在這種情況下，單個 BigUint64Array 值最多可以處理 8 x 8 板。同樣，在那之后，除非使用 BigInt，否則將需要多個二進制值。

測驗獲勝者

當然，權衡是資料結構更簡單，獲勝者的測驗成本更高，但如前所述，對于可變大小的井字棋盤來說，這更容易擴展。例如，一個 4 x 4 井字棋棋盤將用于顯示演算法，以按行、列和對角線檢查獲勝者。這些演算法本質上是 O(N)，因此很容易在演算法上擴展更大的電路板，特別是在使用 BigInt 的情況下。例如，如果使用 BigUint64Array 值，那么任何位移都將涉及底層整數值之間的溢位，從而使按位演算法更加復雜，但并不過分。

例如，對 64 位 Uint 進行位移很簡單，但對于 128 位 Uint 則不然，因為除了 BigInt 之外沒有 128 位數字的內部表示，在這種情況下可能會影響性能。用兩個 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 個。

( bitboard >>> 3) & (bitboard >>> 2) & (bitboard >>> 1) & bitboard & 0001 0001 0001 0001

例如，檢查 X 位板是否連續 4 個...

                  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 個。

檢查列中的獲勝者

通過簡單地對同一列中的所有位進行移位和與運算，然后檢查結果是否非零來確定玩家在一列中是否有 4。

bitboard & (bitboard >>> 4) & (bitboard >>> 8) & (bitboard >>> 12)

例如，檢查 X 位板在一列中是否有 4...

                   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.                

請注意，確定玩家是否在 Column 中有 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。

標籤：javascript 算法 二进制 位操作 井字游戏

上一篇：在Python中迭代n嵌套for回圈的更有效方法

下一篇：將list/dict傳遞給函式時，是否應該始終添加list.copy()/dict.copy()？