2025 年 Linux 核心設計課程作業 —— kxo (D)

--- title: 2025 年 Linux 核心設計課程作業 —— kxo (D) image: https://hackmd.io/_uploads/r1ob8RIaa.png description: 藉由改寫井字遊戲來熟悉數值系統和核心程式設計 tags: linux2025 --- # N04: kxo > 主講人: [jserv](https://wiki.csie.ncku.edu.tw/User/jserv) / 課程討論區: [2025 年系統軟體課程](https://www.facebook.com/groups/system.software2025/) :mega: 返回「[Linux 核心設計](https://wiki.csie.ncku.edu.tw/linux/schedule)」課程進度表 ## 對奕的核心模組 [kxo](https://github.com/sysprog21/kxo) 衍生自 [simrupt](https://github.com/sysprog21/simrupt)，遊戲主本運作於 Linux 核心內運作，讓二個不同的井字遊戲 (也稱為 XO Game，本核心模組因此得名) 人工智慧演算法，藉由 workqueue，執行在「不同的 CPU」並模擬二者的對弈，並允許使用者層級的程式藉由開啟 `/dev/kxo` 來設定二個人工智慧程式的對弈並存取彼此的棋步。其一演算法是 MCTS，另一者是 [Negamax 演算法](https://en.wikipedia.org/wiki/Negamax)。模擬對弈過程，前述二個人工智慧演算法程式碼在執行時間，會適度停頓 (數百個 millisecond)，並可從使用者層級指定對弈的起始、暫停、恢復，和瀏覽狀態。 tic-tac-toe 棋盤規劃如下： ``` | | | ------- | | | ------- | | | ------- | |O| ------- ``` 一旦 `kxo` 核心模組掛載，即可藉由以下命令觀察對戰的過程： ``` $ sudo cat /dev/kxo ``` 參考輸出: ``` | | |O ------- | | | ------- O| | |X ------- | | | ------- | | |O ------- | | | ------- O| | |X ------- | | | ------- ... ``` 畫出棋盤的時間變長並非因為畫棋盤所需時間變長，是因為每次都等待 AI 演算法完整推算出一步才畫出來，用 `sudo dmesg` 命令觀察到以下: ``` [ 415.416008] kxo: [CPU#2] ai_one_tasklet_func in_softirq: 2766783 usec [ 417.613452] kxo: [CPU#2] ai_two_tasklet_func in_softirq: 2145960 usec [ 417.614730] kxo: [CPU#2] enter timer_handler [ 417.614741] kxo: [CPU#2] doing AI game [ 417.614746] kxo: [CPU#2] scheduling tasklet [ 417.614750] kxo: [CPU#2] timer_handler in_irq: 9 usec [ 417.614833] kxo: [CPU#2] simrupt_tasklet_func in_softirq: 0 usec [ 417.614841] kxo: [CPU#1] simrupt_work_func [ 418.346857] kxo: [CPU#2] ai_one_tasklet_func in_softirq: 714876 usec [ 418.794527] kxo: [CPU#2] ai_two_tasklet_func in_softirq: 437181 usec [ 418.794535] kxo: [CPU#2] enter timer_handler [ 418.794537] kxo: [CPU#2] doing AI game [ 418.794537] kxo: [CPU#2] scheduling tasklet [ 418.794538] kxo: [CPU#2] timer_handler in_irq: 1 usec [ 418.794559] kxo: [CPU#2] simrupt_tasklet_func in_softirq: 7 usec [ 418.794575] kxo: [CPU#1] simrupt_work_func [ 419.011141] kxo: [CPU#2] ai_one_tasklet_func in_softirq: 211507 usec [ 419.013170] kxo: [CPU#2] ai_two_tasklet_func in_softirq: 1979 usec [ 419.013174] kxo: [CPU#2] enter timer_handler [ 419.013175] kxo: O win!!! [ 419.013176] kxo: [CPU#2] timer_handler in_irq: 0 usec [ 419.013185] kxo: [CPU#2] simrupt_tasklet_func in_softirq: 0 usec [ 419.013225] kxo: [CPU#7] simrupt_work_func ``` 凡是執行 AI 演算法的時候，該 CPU 就會耗費很長的時間在 softirq 當中，將 AI 演算法都包裝成 work item 放入 workqueue 當中執行，但這裡會遇到一個問題，該如何判斷輪到誰執行？單純用 mutex lock 是不足夠的，因為有可能某方連續兩次都搶到該 lock ，使得它可以連續下兩步，於是採用一個變數 `turn` 來表示目前輪到誰下棋，若非自己則直接結束該 work item ，等待下一次 tasklet 再把 work item 放入，但這裡又有另一個問題，每個 work item 是被不同 CPU 執行，他們看到的 `turn` 有可能不相同，該如何保證跨越 CPU 之間的資料一致性呢？於是要特別運用 memory ordering 的 acquire / release 操作來保證這件事。 ### 使用者層級互動撰寫使用者層級程式 `xo-user.c` 作為與 `kxo` 的檔案裝置互動的媒介，首先是顯示對弈過程 ```diff + FILE *device_ptr = fopen(kxo_DEVICE_FILE, "r"); + char display_buf[DRAWBUFFER_SIZE]; + while (fgets(display_buf, DRAWBUFFER_SIZE, device_ptr)) { + printf("%s", display_buf); + } + + fclose(device_ptr); ``` 透過 `fopen(), fgets()` 即可讀取核心對弈過程。接下來要透過使用者層級的輸入來判斷是否重新開始一個棋局或者暫停顯示等等操作，需要從使用者層級傳送資料到核心空間，本處選用 sysfs 機制，透過寫入代表核心模組當中變數的檔案和核心模組進行溝通，以暫停顯示對弈棋盤為例，首先新增 kernel attribute 如下 ```c struct kxo_attr { char display; char restart; char end; rwlock_t lock; }; ``` 同時也要定義對應的 `show(), store()` 函式，最後透過 `DEVICE_ATTR_RW()` 巨集來取得 attribute 。 ```c static ssize_t kxo_state_show(struct device *dev, struct device_attribute *attr, char *buf) { read_lock(&attr_obj.lock); int ret = sprintf(buf, "%c %c %c\n", attr_obj.display, attr_obj.restart, attr_obj.end); read_unlock(&attr_obj.lock); return ret; } static ssize_t kxo_state_store(struct device *dev, struct device_attribute *attr, const char *buf, size_t count) { write_lock(&attr_obj.lock); sscanf(buf, "%c %c %c", &(attr_obj.display), &(attr_obj.restart), &(attr_obj.end)); write_unlock(&attr_obj.lock); return count; } static DEVICE_ATTR_RW(kxo_state); ``` 然後要在核心模組初始化的時候建立對應 sysfs 檔案，透過 `device_create_file()` ```c ret = device_create_file(kxo_dev, &dev_attr_kxo_state); if (ret < 0) { printk(KERN_ERR "failed to create sysfs file kxo_state\n"); goto error_cdev; } ``` 在使用者層級的程式也要有對應處理機制，讓終端機的 stdin 轉為 raw mode ，並監聽輸入的字元並進行對應的處理。 ```diff + if (read(STDIN_FILENO, &input, 1) == 1) { + switch(input) { + case 16: + char buf[20]; + read(attr_fd, buf, 5); + buf[0] = buf[0] - '0' ? '0' : '1'; + write(attr_fd, buf, 5); + break; + case 17: + break; + } + } ``` 到目前為止，可讓核心重複對弈的棋局，並在使用者層級透過 Ctrl + P 控制是否顯示對弈棋盤。上述做法在第一次利用 Ctrl + P 暫停顯示棋盤後，整個使用者層級行程會卡在 `read()` 處等待資料送入，但不會有資料送進該檔案因為核心模組停止傳送資料到使用者層級，於是可利用 I/O multiplexing 機制也就是 `select()` 來達到同時監聽 `STDIN_FILENO` 和裝置檔案是否有輸入，藉此使得 Ctrl + P 可以重複使用，並且 Ctrl + Q 可以使整個核心空間的對弈終止。 ### 自動更新對弈畫面透過在每次輸出前先利用 ASCII code 的跳脫字元 (escape character) 來將終端機畫面刷新，就可以避免一直出現重複畫面的問題 ```diff } else if (read_attr && FD_ISSET(device_fd, &readset)) { FD_CLR(device_fd, &readset); + printf("\033[H\033[J"); /* ASCII escape code to clear the screen */ read(device_fd, display_buf, DRAWBUFFER_SIZE); ``` 展示影片: [Kernel space tic-tac-toe game](https://youtu.be/Y_xdLrDVGzk) --- ## kxo 程式碼分析井字遊戲棋盤並不是只有 `3*3` ，即他的 `BOARD_SIZE` 是可以被設定為三或以上的數字，並且在 `game.h` 中還另外設定了結構體 ```c typedef struct { int i_shift, j_shift; int i_lower_bound, j_lower_bound, i_upper_bound, j_upper_bound; } line_t; ``` 用以在之後判斷對局是否結束，這邊看到在使用這個結構體時，會先建立一個 `lines` 陣列: ```c const line_t lines[4] = { {1, 0, 0, 0, BOARD_SIZE - GOAL + 1, BOARD_SIZE}, // ROW {0, 1, 0, 0, BOARD_SIZE, BOARD_SIZE - GOAL + 1}, // COL {1, 1, 0, 0, BOARD_SIZE - GOAL + 1, BOARD_SIZE - GOAL + 1}, // PRIMARY {1, -1, 0, GOAL - 1, BOARD_SIZE - GOAL + 1, BOARD_SIZE}, // SECONDARY }; ``` 這裡分別代表四個方向 (橫向、直向、左上右下、右上左下) 的線段，`GOAL` 為判斷勝利的長度，在一般 `3*3` 的對局中即為 `3` ，之後經過呼叫 `check_win` ，進行這四種獲勝條件方向的檢查。 ```c char check_win(char *t) { for (int i_line = 0; i_line < 4; ++i_line) { line_t line = lines[i_line]; for (int i = line.i_lower_bound; i < line.i_upper_bound; ++i) { for (int j = line.j_lower_bound; j < line.j_upper_bound; ++j) { char win = check_line_segment_win(t, i, j, line); if (win != ' ') return win; } } } for (int i = 0; i < N_GRIDS; i++) if (t[i] == ' ') return ' '; return 'D'; } ``` 在 `check_line_segment_win` 內 ```c for (int k = 1; k < GOAL; k++) { if (last != t[GET_INDEX(i + k * line.i_shift, j + k * line.j_shift)]) { return ' '; } ``` 可觀察到這個實作方式的優缺點，優點是這個勝利判定方式在棋盤為大於 `3*3` 的方形棋盤時也同樣可以適用，缺點在於這個方式做過多的 `for` 迴圈，即在所有有可能達成勝利條件的起始點都進行一次的 `check_line_segment_win` ，因此在每一次落子之後，至少都需要耗費 $O(N^2)$ 的計算量，其中 $N$ 為棋盤寬度；另外就是在資料存儲與傳輸的方面來看，這個實作方式需要一個大小為 `N_GRIDS` 的字串去儲存每一個格子內目前的狀況 `( ' ' / 'O' / 'X' )` ```c char table[N_GRIDS]; ``` 在之後使用者和核心空間之間的傳輸將會大幅提高 buffer 的負載量。 ### 藉由位元運算降低棋盤判定的成本 [population count](https://en.wikichip.org/wiki/population_count) 簡稱 popcount 或叫 sideways sum，是計算數值的二進位表示中，有多少位元是 `1`，在一些場合下很有用，例如計算 0-1 稀疏矩陣 (sparse matrix)或 bit array 中非 `0` 元素個數、計算兩個字串的 [Hamming distance](https://en.wikipedia.org/wiki/Hamming_weight)。Intel 在 2008 年 11 月 Nehalem 架構的處理器 Core i7 引入 SSE4.2 指令集，其中就有 `CRC32` 和 `popcount` 指令，`popcount` 可處理 16-bit, 32-bit, 64-bit 整數。對應到 C 程式的實作: ```c unsigned popcount_naive(unsigned v) { unsigned n = 0; while (v) v &= (v - 1), n = -(~n); return n; } ``` 函式 `popcount_naive()` 利用不斷清除 LSB 直到輸入的數值 `v` 為 0。來說，假設輸入數值為 `20`: ```c 0001 0100 # 20 ; LSB in bit position 2 0001 0011 # 20 - 1 0001 0000 # 20 & (20 - 1) ``` > 類似的操作還有 `x & -x`，將 `x` 的 LSB 取出 (**isolate LSB**) `n = -(~n)` 等同 `n++`，因為在二補數系統中， $-n =\ \sim n + 1$ $-(\sim n) = n + 1$ 因此 `popcount_naive()` 的執行時間取決於輸入數值中 1 (set bit) 的個數。可改寫為以下常數時間複雜度的實作: ```c unsigned popcount_branchless(unsigned v) { unsigned n; n = (v >> 1) & 0x77777777; v -= n; n = (n >> 1) & 0x77777777; v -= n; n = (n >> 1) & 0x77777777; v -= n; v = (v + (v >> 4)) & 0x0F0F0F0F; v *= 0x01010101; return v >> 24; } ``` 對於一個 32 bit 的無號整數，popcount 可以寫成以下數學式: $popcount(x) = x - \left \lfloor{{\dfrac{x}{2}}}\right \rfloor - \left \lfloor{{\dfrac{x}{4}}}\right \rfloor - ... - \left \lfloor{{\dfrac{x}{2^{{31}}}}}\right \rfloor$ 假設 $x = b_{31}...b_3b_2b_1b_0$，先看看 $x[3:0]$ 4 個位元，用以上公式可以計算得: $(2^3b_3 + 2^2b_2 + 2^1b_1 + 2^0b_0) - (2^2b_3 + 2^1b_2 + 2^0b_1) - (2^1b_3 + 2^0b_2) - 2^0b_3$ > $\left \lfloor{{\dfrac{x}{2}}}\right \rfloor$ 相當於 C 表達式中 `x >> 1` 稍微改寫可得到: $(2^3 - 2^2 - 2^1 - 2^0)b_3 + (2^2 - 2^1 - 2^0)b_2 + (2^1 - 2^0)b_1 + 2^0b_0$ 因此 popcount 的一般式可改寫為: $popcount(x) = \sum\limits_{n=0}^{31} {}(2^n - \sum\limits_{i=0}^{n-1} 2^{i})b_n = \sum\limits_{n=0}^{31}b_n$ 因為 $2^n - \sum\limits_{i=0}^{n-1} 2^{i} = 1$，只要對應的 $b_n$ 為 1，這個 bit 就會在 popcount 的總和中加一，剛好對應 `popcount_naive()`，因此映證上述數學式確實可計算出 population count。且一個 32 位元無號整數最多有 32 個 1 (set bit)，剛好可用一個 byte 表示，所以可分成幾個區塊平行計算，最後再全部加總到一個 byte 中，進行避免檢查 32 次。 `popcount_branchless` 實作一開始以**每 4 個位元 (nibble) 為一個單位**計算 1 的個數，利用最初的公式計算 $x - \left \lfloor{{\dfrac{x}{2}}}\right \rfloor - \left \lfloor{{\dfrac{x}{4}}}\right \rfloor - \left \lfloor{{\dfrac{x}{8}}}\right \rfloor$ 關鍵的程式碼，逐行解釋: ```c= n = (v >> 1) & 0x77777777; v -= n; n = (n >> 1) & 0x77777777; v -= n; n = (n >> 1) & 0x77777777; v -= n; ``` 1. `n = (v >> 1) & 0x77777777` : 將輸入數值 `v` 除以 2，得到 $\left \lfloor{{\dfrac{v}{2}}}\right \rfloor$ ```c b_31 b_30 b_29 b_28 ... b7 b6 b5 b4 b3 b2 b1 b0 // v 0 b_31 b_30 b_29 ... 0 b7 b6 b4 0 b3 b2 b1 // (v >> 1) & 0x77777777 ``` 2. `v -= n` : 計算結果相當於 $v - \left \lfloor{{\dfrac{v}{2}}}\right \rfloor$ 3. `n = (n >> 1) & 0x77777777` : 再對 `n` 除以 2，得到 $\left \lfloor{{\dfrac{v}{4}}}\right \rfloor$ 4. `v -= n` : 計算出 $v - \left \lfloor{{\dfrac{v}{2}}}\right \rfloor - \left \lfloor{{\dfrac{v}{4}}}\right \rfloor$ 5. 和 6. 重複同樣動作最後這段結束後計算出 $v - \left \lfloor{{\dfrac{v}{2}}}\right \rfloor - \left \lfloor{{\dfrac{v}{4}}}\right \rfloor - \left \lfloor{{\dfrac{v}{8}}}\right \rfloor$，得到每 4 個位元為一個單位中 set bit 的個數 **`v = (v + (v >> 4)) & 0x0F0F0F0F`** : 將每 4 個位元中 set bit 的個數加到 byte 中: 1. 假設 $B_n$ 代表第 n 個 nibble (4 位元) 中的數值 ```c B7 B6 B5 B4 B3 B2 B1 B0 // v 0 B7 B6 B5 B4 B3 B2 B1 // (v >> 4) ``` 2. 加總可得到: ```c // (v + (v >> 4)) B7 (B7+B6) (B6+B5) (B5+B4) (B4+B3) (B3+B2) (B2+B1) (B1+B0) ``` 3. 最後使用 `0x0F0F0F0F` 做 mask 可得 ```c // (v + (v >> 4)) & 0x0F0F0F0F 0 (B7+B6) 0 (B5+B4) 0 (B3+B2) 0 (B1+B0) ``` **`v *= 0x01010101`** : 在最後一道敘述中，將 `v` 乘上 `0x01010101`。寫成直式如下 ``` 0 A6 0 A4 0 A2 0 A0 x 0 1 0 1 0 1 0 1 --------------------------------------------------- 0 A6 0 A4 0 A2 0 A0 0 A6 0 A4 0 A2 0 A0 0 0 A6 0 A4 0 A2 0 A0 0 0 A6 0 A4 0 A2 0 A0 0 --------------------------------------------------- ↑_______________________A6+A4+A2+A0 ``` 我們可發現期望輸出就在原本 $A_6$ 的位置 ($2^7$)，因此將 `v` 右移 24 bits 即為所求，剩下的位數會 overflow ，右移後不影響結果。 * 假設 $A = B_7 + B_6$, $B = B_5 + B_4$, $C = B_3 + B_2$, $D = B_1 + B_0$, 根據分配律可得: ``` v * 0x01010101 = (A + B + C + D) (B + C + D) (C + D) (D) |<-- 1 byte -->|<-- 1 byte -->|<-- 1 byte -->|<-- 1 byte -->| ``` **`return v >> 24`** : 最後得到的結果會放在 Most significant byte 中，因此向右位移 24 位元，即為所求的 popcount 值。 GCC 提供對應的內建函式: > `__builtin_popcount(x)`: 計算 x 的二進位表示中，總共有幾個 `1` 使用示範： ```c int x = 5328; // 00000000000000000001010011010000 printf("%d\n", __builtin_popcount(x)); // 5 ``` > 以下部分摘錄自 [Hacker's Delight](https://web.archive.org/web/20180517023231/http://www.hackersdelight.org/divcMore.pdf): **Remainder by Summing digits** 如何不使用任何除法就算出某數除以另一個數的餘數呢？若除數符合 $2^k \pm 1$，則可運用以下手法來達成這個目的。若 $a \equiv b (mod \ \ m)$ 且 $c \equiv d (mod \ \ m)$ ，則 $a + c \equiv b + d (mod \ \ m)$ 且 $ac \equiv bd (mod \ \ m )$ 假設 $$ a = q_a m + r_1, b = q_b m + r_1, c = q_c m + r_2, d = q_d m + r_2 $$ 再進行運算。以下用 mod 3 當作例子進行操作和解釋 : 由數學上同餘 (modulo) 的特性可以知道，當 $a\equiv b(mod\ \ m)$ 且 $c\equiv d(mod\ \ m)$ ，則 $\ \ a+c\equiv b+d(mod\ \ m)$ 且 $ac\equiv bd(mod\ \ m)$ ，因此若我們有 $1\equiv 1(mod\ \ 3)$ 且 $2\equiv -1(mod\ \ 3)$ ，則可以推出 $2^k\equiv\begin{cases} 1(mod\ \ 3) &if\ \ k\ \ is\ \ even\\ -1(mod\ \ 3) &if\ \ k\ \ is\ \ odd\\ \end{cases}$ 。假設一 32 bits 無號整數 $n = b_{31}b_{30}\cdots b_{2}b_{1}b_{0}$ ，則 n 的值就會等於 $\sum_{i=0}^{31}b_i2^i$ ，由上述推論可得 $n = \sum_{i=0}^{31}b_i(-1)^i\ \ (mod\ \ 3)$ 。到這裡我們可以發現對於以二進位表示的數來講， mod 3 其實就是將偶數位元相加再減去奇數位元，因此可以利用 population count 類型的函式來進行操作，其中一種做法為 `n = popcount(n & 0x55555555) - popcount(n & 0xAAAAAAAA)` ，因為 5 為 0101 ， A 為 1010 ，所以如此運算便能將奇偶穿插著相減，達到預期的效果。而上述做法其實還有別的寫法，那就是利用以下定理將其簡化 : $popcount(x\& \overline m)-popcount(x\&m) = popcount(x \oplus m)-popcount(m)$ 因此我們就能將其改寫為 `n = popcount(n ^ 0xAAAAAAAA) - 16` ，但這裡必須注意到 `popcount(n ^ 0xAAAAAAAA)` 這個值的範圍為 0 < n < 32 ， -16 這個動作可能會導致算出來的值為負數，因此需透過加上 3 的倍數避免這樣的情況發生，而該數只要大於 16 即可，以下利用 39 做說明。 ```c int mod3(unsigned n) { n = popcount(n ^ 0xAAAAAAAA) + 23; n = popcount(n ^ 0x2A) - 3; return n + ((n >> 31) & 3); } ``` 程式碼第一行是由上述推導而來的，也就是 `n = popcount(n ^ 0xAAAAAAAA) - 16 + 39` ，但此時 n 的範圍就會變成 23 < n < 55 ，而我們希望最終的結果會落在 0 < n < 2 (因為 mod 3 )，因此可以再次利用上述定理縮小其範圍。在經過第一行的運算後，其範圍已經變為 23 < n < 55 ，只有最低位的 6 個 bits 可能會有 1 存在，因此根據定理，第二行即為 `popcount(n ^ 0x2A) - 3` (因為 0x2A 為 101010 )，此時 n 的範圍為 -3 < n < 2 ，我們只需再處理負數的部分即可。處理的方法為得到負數就將其 + 3 ，首先，透過右移 31 位來判斷正負，若為 1 則代表是負數，需要 + 3 ，於是和 3 做 `&` 運算，此時會發現要用全 1 去做 `&` 才會是 + 3 的結果，也就是右移需要是算術位移而非邏輯位移，但上方的 input 卻是 `unsigned n` ，因此該程式碼有個小 bug 存在，可以透過將 input 宣告成 `int` 來解決，或者是修改 return 的部分，修改過後的程式碼如下 : ```c int mod3(unsigned n) { n = __builtin_popcount(n ^ 0xAAAAAAAA) + 23; n = __builtin_popcount(n ^ 0x2A) - 3; return n + (((n >> 31) | (n >> 30)) & 3); } ``` 在最後一行的地方，我將 `(n >> 31)` 與 `(n >> 30)` 做 or 運算，由於 3 的二進位表示法為 011 ，因此只須考慮最後 2 個 bits 即可，並且利用 or 來達到算術位移的效果，也就是將負數的高位元填滿 1 。而事實上若改寫為這樣也不需要再 `&3` 了，因為若是負數則位移完會得到 `011` ，若是正數則為 `0` ，因此最終的程式碼為： ```c int mod3(unsigned n) { n = __builtin_popcount(n ^ 0xAAAAAAAA) + 23; n = __builtin_popcount(n ^ 0x2A) - 3; return n + ((n >> 31) | (n >> 30)); } ``` 另一種變形是查表法。 ```c int mod3(unsigned n) { static char table[33] = {2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1 }; n = popcount(n ^ 0xAAAAAAAA); return table[n]; } ``` 首先要建立一個表格，該表格的內容為 mod 3 後可能的值，也就是 {012} ，而大小則取決於 `n` 的範圍，這裡是 0 ~ 32 ，因此表格大小為 33 。至於表格內值的排序則是由 `n` 所決定的，在這裡因為 `n = popcount(n ^ 0xAAAAAAAA)` ，可以想成 `n = popcount(n & 0x55555555) - popcount(n & 0xAAAAAAAA) + 16` ，因此對於 table[0] 來講，要找到當程式碼內的 `n = 0` 時，實際上 mod 3 為多少，而這裡只要找出前 3 項，然後依序填完整個 table 即可 : `n = 0` : -16 mod 3 為 2 ，所以 table[0] = 2 ； `n = 1` : -15 mod 3 為 0 ，所以 table[1] = 0 ； `n = 2` : -14 mod 3 為 1 ，所以 table[2] = 1 ；如此填完便可以得到正確的值。運用上述想法，統計隨機的井字遊戲的表現，參考執行輸出如下: ``` Win probability for first move with random agents: 0.115 0.102 0.116 0.102 0.131 0.101 0.116 0.102 0.116 Player 1 won 584650 times Player 2 won 288379 times 126971 ties 0.047604 seconds 21.006638 million games/sec ``` 程式碼: ```c /* Enhance tic-tac-toe game performance through a strategic approach. * Rather than exclusively focusing on achieving three consecutive marks on a * 3x3 board, reimagine the game as aiming for three in a row across any of the * eight possible lines. In this variation, a single move can influence multiple * lines simultaneously. */ static const uint32_t move_masks[9] = { 0x40040040, 0x20004000, 0x10000404, 0x04020000, 0x02002022, 0x01000200, 0x00410001, 0x00201000, 0x00100110, }; ``` 用十六進位 32 位元無號整數來表示，原因為 8 個位元正好可對應到九宮格的 8 種連線方法，亦即，由最高位元開始依序往下會對應到的是九宮格中由上到下、由左到右的橫一、橫二、橫三、直一、直二、直三、右斜和左斜，而一組 nibble 中的前 3 個位元則代表了該位置是否已經被放置。以左上角第一個位置做說明，對於橫一、直一和右斜來講，就會是 100 ，其餘皆為 000 ，因此整體就會是 `0x40040040` 。 ```c /* Determine if the tic-tac-toe board is in a winning state. */ static inline uint32_t is_win(uint32_t player_board) { return (player_board + 0x11111111) & 0x88888888; } ``` 此段程式碼是用來決定是否已經存在一方獲勝的狀態，也就是上述八種可能有其中一種被填滿，舉例來說，如果是橫二被填滿，那當下的狀態應為 `0x07022222` ，換句話說，被填滿的那條線必定會出現 `7(0b0111)` 這個數字，因此可以將當下的狀態加上 `0x11111111` 並和 `0x8888888` 做 bitwise-AND 運算，若有值則代表有存在著連線，否則會 `return 0` 。 ```c /* specialized */ static inline uint32_t fastmod(uint32_t x, uint32_t n) { switch (n) { case 2: return x & 1; case 3: return mod3(x); case 4: return x & 3; case 5: return x % 5; case 6: return x % 6; case 7: return mod7(x); case 8: return x & 7; case 9: return x % 9; default: return 0; } } /* Simulate a random game and display the sequence of moves made. */ uint32_t play_random_game(uint32_t player, uint32_t *moves) { uint32_t boards[2] = {0, 0}; uint32_t available_moves[9] = {0, 1, 2, 3, 4, 5, 6, 7, 8}; for (uint32_t n_moves = 9; n_moves > 0; n_moves--) { /* Get board of player */ uint32_t board = boards[player - 1]; /* Choose random move */ uint32_t i = fastmod(xorshift32(), n_moves); uint32_t move = available_moves[i]; /* Delete move from available moves */ available_moves[i] = available_moves[n_moves - 1]; /* Apply move to board */ board |= move_masks[move]; /* Remember move */ *moves++ = move; /* Check if current player won the game and return the winner */ if (is_win(board)) return player; /* Update board of player */ boards[player - 1] = board; /* Next player, 1 -> 2, 2 -> 1 */ player = 3 - player; } /* Mark end of game */ *moves++ = -1; return 0; } int main() { /* Run multiple iterations to verify the consistency of probabilities. */ for (int k = 0; k < 10; k++) { double start_time = clock() / (double) CLOCKS_PER_SEC; /* Count wins by player (tie, player 1, player 2) */ uint32_t wins[3] = {0, 0, 0}; /* Count wins by first move */ uint32_t wins_by_move[9] = {0}; /* Simulate a million random games */ int n_games = 1000 * 1000; for (int i = 0; i < n_games; i++) { uint32_t player = 1; /* Record which moves were played, last move is -1. */ uint32_t moves[10] = {0}; uint32_t winner = play_random_game(player, moves); /* Count wins */ wins[winner]++; if (winner == player) wins_by_move[moves[0]]++; } double delta_time = clock() / (double) CLOCKS_PER_SEC - start_time; /* Print statistics */ printf("Win probability for first move with random agents:\n"); for (int y = 0; y < 3; y++) { for (int x = 0; x < 3; x++) printf("%.3f ", wins_by_move[x + y * 3] * 1.0 / wins[1]); printf("\n"); } printf("Player 1 won %u times\n", wins[1]); printf("Player 2 won %u times\n", wins[2]); printf("%u ties\n", wins[0]); printf("%f seconds\n", delta_time); printf("%f million games/sec\n", n_games * 1e-6 / delta_time); printf("\n"); } return 0; } ```