2025q1 Homework3 (ttt)

contributed by <I-Ying-Tsai>

作業書寫規範:

• 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
• 文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
• 共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
• 不要在筆記內加入 [TOC] : 筆記左上方已有 Table of Contents (TOC) 功能，不需要畫蛇添足
• 不要變更預設的 CSS 也不要加入任何佈景主題: 這是「開發紀錄」，用於評分和接受同儕的檢閱
• 當在筆記中貼入程式碼時，避免非必要的行號，也就是該手動將 c= 或 cpp= 變更為 c 或 cpp。行號只在後續討論明確需要行號時，才要出現，否則維持精簡的展現。可留意「你所不知道的 C 語言: linked list 和非連續記憶體」裡頭程式碼展現的方式
• HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」
• 留意科技詞彙的使用，請參見「資訊科技詞彙翻譯」及「詞彙對照表」
• 不要濫用 :::info, :::success, :::warning 等標示，儘量用清晰的文字書寫。:::danger 則僅限授課教師作為批注使用
• 避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景
• 在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","。注意書名號的使用，即 〈 和 〉，非「小於」和「大於」符號
• 避免使用不必要的 emoji 字元

開發環境

i-ying-tsai@i-ying-tsai-G5-KF5:~/linux2025/lab0-c$ uname -a
Linux i-ying-tsai-G5-KF5 6.11.0-17-generic #17~24.04.2-Ubuntu SMP PREEMPT_DYNAMIC Mon Jan 20 22:48:29 UTC 2 x86_64 x86_64 x86_64 GNU/Linux

i-ying-tsai@i-ying-tsai-G5-KF5:~/linux2025/lab0-c$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0
Copyright (C) 2023 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

i-ying-tsai@i-ying-tsai-G5-KF5:~/linux2025/lab0-c$ ldd --version
ldd (Ubuntu GLIBC 2.39-0ubuntu8.4) 2.39
Copyright (C) 2024 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
Written by Roland McGrath and Ulrich Drepper.

i-ying-tsai@i-ying-tsai-G5-KF5:~/linux2025/lab0-c$ lscpu
Architecture:             x86_64
  CPU op-mode(s):         32-bit, 64-bit
  Address sizes:          39 bits physical, 48 bits virtual
  Byte Order:             Little Endian
CPU(s):                   16
  On-line CPU(s) list:    0-15
Vendor ID:                GenuineIntel
  Model name:             13th Gen Intel(R) Core(TM) i7-13620H
    CPU family:           6
    Model:                186
    Thread(s) per core:   2
    Core(s) per socket:   10
    Socket(s):            1
    Stepping:             2
    CPU(s) scaling MHz:   33%
    CPU max MHz:          4900.0000
    CPU min MHz:          400.0000
    BogoMIPS:             5836.80

kernel/user 分層 AI 通訊重構報告

commit e066b23 c48480c
實作報告：將棋盤繪製搬移至 user space 並實現 kernel/user 通訊

不要濫用 --- 標示

實作動機與目標

原設計下，棋盤畫面繪製與顯示由 kernel module 處理，user space 僅為被動觀察者。這會導致：

• kernel 必須頻繁輸出整個棋盤字串，通訊資料量大

目標：

• 讓 kernel 僅負責 AI 推理與棋局合法性判斷，user space 主導棋盤繪製與人機/自動對弈邏輯
• 大幅降低 kernel/user 的 I/O 負載，只需交換「棋盤狀態」和「最佳落子」

改寫內容

注意用語

1. 重新設計 kernel/user 溝通介面

- 問題發現

• 原本 kernel module 只實作 .read，無 .write handler。
• user space 無法主動把棋盤狀態寫入 kernel，AI 推理也無法以同步 query 方式取得。

- 解決方案

• 新增 kxo_write：
  • 允許 user space 傳送棋盤狀態（struct xo_board）給 kernel。
  • kernel 端 upon write 立即呼叫 AI（MCTS/Negamax），計算最佳落子，將結果暫存。
• 新增 kxo_read：
  • 讓 user space 能直接讀回 AI 計算出的最佳下一步（struct xo_result），只需一個 index。
• thread safety：
  • 實作 static DEFINE_MUTEX(kxo_lock);，所有 read/write 流程都在 mutex 保護下，避免多執行緒 race condition。

- 共用結構設計

• 新增 xo_common.h：
  • 定義 kernel/user 共用 struct，確保資料 layout 完全一致（避免 padding/對齊問題）。
  • 範例：
    ​​​​#define XO_BOARD_SIZE 16
    ​​​​struct xo_board {
    ​​​​    char table[XO_BOARD_SIZE];
    ​​​​    char player;
    ​​​​} __attribute__((packed));
    
    ​​​​struct xo_result {
    ​​​​    int move;
    ​​​​} __attribute__((packed));
    

• user/kernel 都 include 此 header。

2. 將棋盤繪製與互動邏輯移至 user space

- 技術細節

• 原本的 kernel module 提供整盤棋盤字串的繪圖 buffer（kfifo），現在 user space 僅需向 kernel 請求“最佳下一步”，其餘顯示與互動皆在 user 空間完成。
• 只需執行：
  ​​write(fd, &board, sizeof(board));   // 傳送棋盤狀態與 player
  ​​read(fd, &result, sizeof(result));  // 取得 AI 建議落子
  

• user space 負責根據回傳的 index 更新自己的棋盤、重繪 UI。

- 優點

• 極大減少 kernel/user 資料交換成本（只需一個 int 而非整盤棋盤字串）

dmesg 如下：

[ 7991.861890] kxo: unloaded
[ 7996.597238] kxo: registered new kxo device: 506,0
[ 8005.946284] openm current cnt: 1
[ 8005.946519] openm current cnt: 2
[ 8005.946528] kxo_write: len=17 expect=17
[ 8005.946530] Player O using MCTS algorithm
[ 8006.835695] Player O chose move: 13
[ 8006.835856] kxo_write: len=17 expect=17
[ 8006.835861] Player O using MCTS algorithm
[ 8007.715525] Player O chose move: 4
[ 8007.715661] kxo_write: len=17 expect=17
[ 8007.715664] Player X using Negamax algorithm
[ 8007.724045] Player X chose move: 6
[ 8007.724058] kxo_write: len=17 expect=17
[ 8007.724061] Player X using Negamax algorithm
[ 8007.735346] Player X chose move: 11
[ 8007.735402] kxo_write: len=17 expect=17
[ 8007.735404] Player O using MCTS algorithm
[ 8008.362811] Player O chose move: 1
[ 8008.362930] kxo_write: len=17 expect=17
[ 8008.362934] Player O using MCTS algorithm
[ 8008.844757] Player O chose move: 8
[ 8008.844811] kxo_write: len=17 expect=17
[ 8008.844813] Player X using Negamax algorithm
[ 8008.846533] Player X chose move: 9
[ 8008.846536] kxo_write: len=17 expect=17
[ 8008.846538] Player X using Negamax algorithm
[ 8008.849360] Player X chose move: 7
[ 8008.849392] kxo_write: len=17 expect=17
[ 8008.849394] Player O using MCTS algorithm
[ 8009.154950] Player O chose move: 2
[ 8009.155064] kxo_write: len=17 expect=17
[ 8009.155068] Player O using MCTS algorithm
[ 8009.306985] Player O chose move: 0
[ 8009.307161] kxo_write: len=17 expect=17
[ 8009.307164] Player X using Negamax algorithm
[ 8009.307471] Player X chose move: 3
[ 8009.307475] kxo_write: len=17 expect=17
[ 8009.307476] Player O using MCTS algorithm
[ 8010.186737] Player O chose move: 3
[ 8010.186934] kxo_write: len=17 expect=17
[ 8010.186938] Player O using MCTS algorithm
[ 8011.192011] Player O chose move: 15
[ 8011.192151] kxo_write: len=17 expect=17
[ 8011.192155] Player X using Negamax algorithm
[ 8011.198224] Player X chose move: 6
[ 8011.198275] kxo_write: len=17 expect=17
[ 8011.198277] Player X using Negamax algorithm
[ 8011.202879] Player X chose move: 10
[ 8011.202883] kxo_write: len=17 expect=17
[ 8011.202884] Player O using MCTS algorithm
[ 8011.831991] Player O chose move: 0
[ 8011.832148] kxo_write: len=17 expect=17
[ 8011.832152] Player O using MCTS algorithm
[ 8012.465743] Player O chose move: 8
[ 8012.465885] kxo_write: len=17 expect=17
[ 8012.465889] Player X using Negamax algorithm
[ 8012.467935] Player X chose move: 10
[ 8012.467977] kxo_write: len=17 expect=17
[ 8012.467979] Player X using Negamax algorithm
[ 8012.470928] Player X chose move: 2
[ 8012.470931] kxo_write: len=17 expect=17
[ 8012.470933] Player O using MCTS algorithm
[ 8012.767517] Player O chose move: 14
[ 8012.767710] kxo_write: len=17 expect=17
[ 8012.767713] Player O using MCTS algorithm
[ 8013.064723] Player O chose move: 12
[ 8013.064842] kxo_write: len=17 expect=17
[ 8013.064846] Player X using Negamax algorithm
[ 8013.065596] Player X chose move: 5
[ 8013.065636] kxo_write: len=17 expect=17
[ 8013.065638] Player X using Negamax algorithm
[ 8013.066082] Player X chose move: 6
[ 8013.066084] kxo_write: len=17 expect=17
[ 8013.066085] Player O using MCTS algorithm
[ 8013.311538] Player O chose move: 1
[ 8013.311719] kxo_write: len=17 expect=17
[ 8013.311723] Player O using MCTS algorithm
[ 8014.301126] Player O chose move: 11
[ 8014.301254] kxo_write: len=17 expect=17
[ 8014.301257] Player X using Negamax algorithm
[ 8014.301602] Player X chose move: 2
[ 8014.301642] kxo_write: len=17 expect=17
[ 8014.301643] Player X using Negamax algorithm
[ 8014.310498] Player X chose move: 5
[ 8014.310508] kxo_write: len=17 expect=17
[ 8014.310511] Player O using MCTS algorithm
[ 8015.169542] Player O chose move: 9
[ 8015.169610] kxo_write: len=17 expect=17
[ 8015.169613] Player O using MCTS algorithm
[ 8015.792389] Player O chose move: 0
[ 8015.792401] kxo_write: len=17 expect=17
[ 8015.792403] Player X using Negamax algorithm
[ 8015.799811] Player X chose move: 6
[ 8015.799859] kxo_write: len=17 expect=17
[ 8015.799860] Player X using Negamax algorithm
[ 8015.801247] Player X chose move: 6
[ 8015.801251] kxo_write: len=17 expect=17
[ 8015.801252] Player O using MCTS algorithm
[ 8016.284864] Player O chose move: 1
[ 8016.284968] kxo_write: len=17 expect=17
[ 8016.284971] Player O using MCTS algorithm
[ 8016.631433] Player O chose move: 7
[ 8016.631563] kxo_write: len=17 expect=17
[ 8016.631568] Player X using Negamax algorithm
[ 8016.632275] Player X chose move: 5
[ 8016.632368] kxo_write: len=17 expect=17
[ 8016.632369] Player X using Negamax algorithm
[ 8016.632728] Player X chose move: 4
[ 8016.632735] kxo_write: len=17 expect=17
[ 8016.632736] Player O using MCTS algorithm
[ 8016.934090] Player O chose move: 14
[ 8016.934206] kxo_write: len=17 expect=17
[ 8016.934210] Player O using MCTS algorithm
[ 8017.925530] Player O chose move: 14
[ 8017.925665] kxo_write: len=17 expect=17
[ 8017.925669] Player X using Negamax algorithm
[ 8017.925913] Player X chose move: 4
[ 8017.925923] kxo_write: len=17 expect=17
[ 8017.925924] Player X using Negamax algorithm
[ 8017.936565] Player X chose move: 2
[ 8017.936573] kxo_write: len=17 expect=17
[ 8017.936574] Player O using MCTS algorithm
[ 8018.804900] Player O chose move: 7
[ 8018.805108] kxo_write: len=17 expect=17
[ 8018.805112] Player O using MCTS algorithm
[ 8019.306195] Player O chose move: 4
[ 8019.306310] kxo_write: len=17 expect=17
[ 8019.306313] Player X using Negamax algorithm
[ 8019.317239] Player X chose move: 4
[ 8019.317286] kxo_write: len=17 expect=17
[ 8019.317288] Player X using Negamax algorithm
[ 8019.318365] Player X chose move: 1
[ 8019.318369] kxo_write: len=17 expect=17
[ 8019.318370] Player O using MCTS algorithm
[ 8019.825121] Player O chose move: 6
[ 8019.825286] kxo_write: len=17 expect=17
[ 8019.825291] Player O using MCTS algorithm
[ 8019.990906] Player O chose move: 9
[ 8019.991044] kxo_write: len=17 expect=17
[ 8019.991048] Player X using Negamax algorithm
[ 8019.993077] Player X chose move: 8
[ 8019.993122] kxo_write: len=17 expect=17
[ 8019.993124] Player O using MCTS algorithm
[ 8020.861429] Player O chose move: 3
[ 8020.861458] kxo_write: len=17 expect=17
[ 8020.861477] Player O using MCTS algorithm
[ 8021.011617] Player O chose move: 5
[ 8021.011850] release, current cnt: 1
[ 8021.012123] release, current cnt: 0

未來可能的修改目標：

1 : 因為目前把棋盤資訊寫入 kernel 的通訊量仍然可以降低（現在寫進去的是一個陣列以及當前玩家），之後會嘗試利用 hash 來減少寫入成本。

2 : 可能可以利用 queue 來讓 kernel 裡的 ai 再不是自己的回合時往後多算幾步並存進去 queue ，下一步可以直接查表。

---

xo-user.c

新的commit c48480c
實現了繪製棋盤、處理鍵盤事件以及向 kernel space 拿 ai 運算的下一步

注意書寫規範：中英文間用一個半形空白字元區隔

實作報告：Coroutine-based 使用者層級排程器設計

參考 sysprog21/concurrent-programs 專案中 tinync 的 coroutine 實作方式。

使用巨集與 goto 配合結構體儲存程式跳轉點與執行狀態，模擬 coroutine 行為，而非依賴 POSIX thread。

其關鍵實作方式為：

• 使用 struct cr 儲存 coroutine 狀態與跳轉點。
• 定義 cr_begin, cr_end, cr_wait, cr_exit 等巨集實現狀態控制。
• 使用 select() 搭配非阻塞 I/O 配合 coroutine 排程。

xo-user.c 改寫說明

原本的 xo-user.c 採用 select() 機制等待 stdin 或 /dev/kxo 的輸入，並使用同步方式處理鍵盤與棋盤更新事件。為了支援 coroutine 式排程，我將其改寫為多 coroutine 架構，分工如下：

1. keyboard_loop coroutine

• 處理鍵盤輸入（使用 raw 模式 + nonblocking read）。
• 支援：
  • Ctrl+P 切換畫面刷新（read_attr）
  • Ctrl+Q 終止程式並通知 kernel 模組（write 1 至 sysfs）。
• 寫入目標為 /sys/class/kxo/kxo/kxo_state。

2. display_loop coroutine

• 負責根據 should_redraw 顯示雙棋盤畫面。
• 僅在 read_attr == true 時輸出，配合鍵盤切換。

3. AI coroutine 設計

• 共 4 個 coroutine：
  • ai1_loop_0, ai2_loop_0 操作棋盤 0（Game 1）
  • ai1_loop_1, ai2_loop_1 操作棋盤 1（Game 2）
• 交替進行 O vs. X 自動對戰
  • ai1_loop_*: 執行 mcts() 決策
  • ai2_loop_*: 執行 negamax_predict() 決策
• 每次選定落子後檢查勝負，若有勝者，設定 finished[i] = true

4. main 排程器邏輯

• 使用無窮迴圈排程所有 coroutine：
  ​​if (!finished[0]) {
  ​​          if (turns[0] == 1 && cr_status(ai1_loop_0) != CR_FINISHED)
  ​​              cr_run(ai1_loop_0);
  ​​          else if (turns[0] == 2 && cr_status(ai2_loop_0) != CR_FINISHED)
  ​​              cr_run(ai2_loop_0);
  ​​      }
  ​​  
  ​​      if (!finished[1]) {
  ​​          if (turns[1] == 1 && cr_status(ai1_loop_1) != CR_FINISHED)
  ​​              cr_run(ai1_loop_1);
  ​​          else if (turns[1] == 2 && cr_status(ai2_loop_1) != CR_FINISHED)
  ​​              cr_run(ai2_loop_1);
  ​​      }
  ​​      cr_run(display_loop);
  ​​      cr_run(keyboard_loop);
  
  

其他改動

• 使用 non-blocking 設定 stdin 讓 coroutine 不會卡住。
• 使用 raw_mode_enable() 啟用原始鍵盤輸入模式以接收 Ctrl+P/Q。

---

xoroshiro.[ch]

commit 6555a92

實作說明

本模組移植了一個基於 xoroshiro128+ 的輕量級隨機數產生器，主要目的是提供高效能的亂數來源給 MCTS 演算法使用。該實作包含以下幾個核心函式：

• xoro_next: 根據 xoroshiro128+ 的設計，從目前狀態產出下一個 64-bit 的隨機數。
  數學部份：rotl(s0 + s1, 24) + s0 //s0+s1後左旋24位，在加上s0
• xoro_jump: 執行一次跳躍操作，可用於平行亂數序列產生，使不同序列互不重複。
• xoro_init: 使用 clock_gettime 中的 tv_sec 與 tv_nsec 初始化亂數種子，確保每次執行產生不同亂數。

程式中使用的 state_array 結構儲存了 128-bit 的內部狀態，以兩個 64-bit unsigned 整數陣列成員組成。

亂數測試與結果

測試目的

主要驗證 xoro_next 輸出的值是否採用接近於均勻分佈，是否可用於開發通用性模擬。

測試方法

generate_xoro_output.c

struct state_array rng;
    xoro_init(&rng);

    for (int i = 0; i < NUM_SAMPLES; i++) {
        uint64_t r = xoro_next(&rng);
        fprintf(f, "%llu\n", (unsigned long long)r);
    }

xoro_test.py

for byte_idx in range(8):
    byte_values = ((data >> (8 * byte_idx)) & 0xFF).astype(np.uint8)
    freqs = np.bincount(byte_values, minlength=256)
    chi2, p = chisquare(freqs)
    print(f"[Byte {byte_idx}] Chi2 = {chi2:.2f}, p = {p:.4f}")
    if p > 0.05:
        print(f"Byte {byte_idx} appears uniform.")
    else:
        print(f"Byte {byte_idx} shows non-uniformity.")
    plt.figure()
    plt.bar(np.arange(256), freqs)
    plt.title(f"Byte {byte_idx} distribution")
    plt.xlabel("Byte Value")
    plt.ylabel("Frequency")

bit_counts = np.zeros(64, dtype=np.uint32)

for i in range(64):
    bit_counts[i] = np.count_nonzero((data >> i) & 1)

total = len(data)
bit_proportions = bit_counts / total
bit_entropy = -bit_proportions * np.log2(bit_proportions + 1e-10) - (1 - bit_proportions) * np.log2(1 - bit_proportions + 1e-10)

print("\nBit-level analysis:")
for i in range(64):
    print(f"Bit {i:02d}: 1s ratio = {bit_proportions[i]:.4f}, entropy = {bit_entropy[i]:.4f}")

測試結果

• 資料數: 1000000 次
• 擴展: 用 & 0xFF 檢驗每 8-bit 的表現

[Byte 0] Chi2 = 253.26, p = 0.5189
Byte 0 appears uniform.
[Byte 1] Chi2 = 253.04, p = 0.5230
Byte 1 appears uniform.
[Byte 2] Chi2 = 259.88, p = 0.4035
Byte 2 appears uniform.
[Byte 3] Chi2 = 255.65, p = 0.4768
Byte 3 appears uniform.
[Byte 4] Chi2 = 243.62, p = 0.6851
Byte 4 appears uniform.
[Byte 5] Chi2 = 207.37, p = 0.9870
Byte 5 appears uniform.
[Byte 6] Chi2 = 216.36, p = 0.9622
Byte 6 appears uniform.
[Byte 7] Chi2 = 238.12, p = 0.7688
Byte 7 appears uniform.

Bit-level analysis:
Bit 00: 1s ratio = 0.4999, entropy = 1.0000
Bit 01: 1s ratio = 0.5002, entropy = 1.0000
Bit 02: 1s ratio = 0.4999, entropy = 1.0000
Bit 03: 1s ratio = 0.4998, entropy = 1.0000
...

參考

• xoroshiro128+
• wyhash seed 生成參考

---

zobrist.[ch]

commit 80d53d1

實作細節

• zobrist_init():
  為每個棋盤格與每個玩家（'X' 和 'O'）生成隨機的 64 位整數權值，並初始化雜湊表。
  • 使用 wyhash 式樣的無狀態 PRNG 實作產生亂數。

static inline uint64_t wyhash64_stateless(uint64_t *seed)
{
    *seed += 0x60bee2bee120fc15ULL;
    __uint128_t tmp = (__uint128_t) (*seed) * 0xa3b195354a39b70dULL;
    uint64_t m1 = (uint64_t) (tmp >> 64) ^ (uint64_t) tmp;
    tmp = (__uint128_t) m1 * 0x1b03738712fad5c9ULL;
    uint64_t m2 = (uint64_t) (tmp >> 64) ^ (uint64_t) tmp;
    return m2;
}

• 在 user-space 中用 clock_gettime() 作為種子；在 kernel-space 中使用 ktime_get()。

• zobrist_get(uint64_t key):
  從雜湊表中查找指定 key 的節點（zobrist_entry_t），若存在則回傳該節點；否則回傳 NULL。

• zobrist_put(uint64_t key, int score, int move):
  新增一筆包含 key、score 與 move 的紀錄至雜湊表中。

• zobrist_clear():
  清空整個雜湊表，包括所有節點，釋放記憶體，並重設 head。

雜湊值初始化（初始轉換）：

move_t negamax_predict(char *table, char player)
{
    for (int i = 0; i < N_GRIDS; ++i) {
        if (table[i] == 'X')
            hash_value ^= zobrist_table[i][1];
        else if (table[i] == 'O')
            hash_value ^= zobrist_table[i][0];
    }

解釋：

• 在遊戲開始的盤面上，「第一次」從 char table[] 把盤面轉成雜湊值
• hash_value 被視為目前盤面的唯一識別碼
• 這是 雜湊值的初始化階段

雜湊值動態更新 + 還原：

for (int i = 0; i < n_moves; i++) {
    ...
    table[move] = player;
    hash_value ^= zobrist_table[move][player == 'X'];

    table[move] = ' ';
    hash_value ^= zobrist_table[move][player == 'X'];

解釋：

• 每次嘗試下一步時，會對 hash_value XOR 加入該格子的雜湊值
• 完成評估後，用 相同 XOR 再次操作還原回原來狀態

為什麼這樣碰裝機率會降低？

我們說：「n 個 hash key 全部落在不同的桶」的機率是：

$$P_{\text{no-collision}}=\prod _{i=0}^{n-1}(1-\frac{i}{H})$$

取對數：

$$\ln P_{\text{no-collision}}=\sum _{i=0}^{n-1}\ln (1-\frac{i}{H})$$

因為

$$\frac{i}{H}\mathrm{很}\mathrm{小}$$

$$(H=2^{64})$$，我們可以用泰勒展開：

$$\ln (1-x)=-x-\frac{x^2}{2}-\frac{x^3}{3}-\cdots$$

保留第一項近似就好：

$$\ln (1-\frac{i}{H})\approx -\frac{i}{H}$$

所以總和變成：

$$\ln P_{\text{no-collision}}\approx -\sum _{i=0}^{n-1}\frac{i}{H}=-\frac{1}{H}\cdot \sum _{i=0}^{n-1}i=-\frac{n(n-1)}{2H}$$

兩邊取 exp：

$$P_{\text{no-collision}}\approx e^{-\frac{n(n-1)}{2H}}\Rightarrow P_{\text{collision}}\approx 1-e^{-\frac{n(n-1)}{2H}}$$

---

game.[ch]

commit 96b92ec

此模組負責管理井字棋（Tic-Tac-Toe）的棋盤邏輯與勝負判斷，支援彈性定義棋盤大小 (UTIL_BOARD_SIZE) 及勝利條件 (UTIL_GOAL)。

巨集定義與結構

• #define UTIL_BOARD_SIZE 4：棋盤邊長。
• #define UTIL_GOAL 3：連續幾子算勝。
• #define UTIL_N_GRIDS：棋盤總格數（UTIL_BOARD_SIZE²）。
• typedef game_table_t：以 1 維陣列方式儲存棋盤格子。
• typedef util_line_t：定義一條可供掃描的線段方向與邊界條件。

主要函式與邏輯

char check_win(const char *table)

• 掃描所有可能的方向（橫、直、兩條對角線）來尋找是否有 UTIL_GOAL 個連續相同的棋子。
• 排除「被延伸」的連線（避免超過 GOAL 的連續棋判定錯誤）。
• 若無勝方，則繼續檢查是否棋盤填滿（回傳 'D'，代表和局）；否則回傳 ' '（比賽尚未結束）。

util_fixed_point_t calculate_win_value(char win, char player)

• 將勝利結果轉換為定點數值：
  • 若 win == player：回傳 1.0（1 << UTIL_FIXED_SCALE_BITS）。
  • 若輸：回傳 0.0。
  • 若平手：回傳 0.5（1 << (UTIL_FIXED_SCALE_BITS - 1)）。
• 此函式提供 AI 演算法作為模擬評分依據。

int *available_moves(const char *table)

• 掃描棋盤上所有可落子的位置，將空格子的位置記錄到動態配置的陣列中（並以 -1 結尾）。
• 呼叫端應負責 free() 返回的指標。

---

mcts.[ch]

commit 0889166

此模組移植了基於定點數 (fixed_point_t) 的蒙地卡羅樹搜尋（MCTS），提供 mcts() 作為 AI 的決策入口。MCTS 結合 UCT (Upper Confidence Bound for Trees) 演算法來平衡探索與利用，並能在不支援浮點數運算的環境下運作。

核心邏輯

1. mcts() 函式

• 執行多次模擬（預設 1000 次），從 root 開始選擇最佳節點（使用 uct_score()）。
• 若該節點未展開，呼叫 expand() 建立子節點。
• 接著進行 simulate() 模擬遊戲至結束，依據結果 backpropagate() 分數回傳至父節點。
• 最終回傳拜訪次數最多的節點對應的動作。

2. uct_score() 函式

• 使用公式 Q/n + C * sqrt(ln(N)/n) 計算每個子節點的探索價值（其中 C 是探索係數），但實作在 fixed-point 上為：

score / n + EXPLORATION_FACTOR * sqrt(log(N) / n)

• 涉及 fixed-point 的乘除、平方根與對數。

fixed_log in ai_mcts.c

參考了2025 年 Linux 核心設計課程作業 —— kxo (A)

此函式計算 Q23.8 固定點格式的自然對數 ln(y)。考慮到 log 的泰勒展開當計算點遠離展開點（即y=1）時，泰勒展開的收斂速度變慢、精度下降。，改以中點對數逼近計算 log 值，方法如下：

主要邏輯

• 將輸入值區間對映為一對整數邊界 L 與 R，以 __builtin_clz() 找出最接近的 2 的冪。
• 不斷更新 L, R 為乘積的平方根中心值，並同時逼近 log(L) 與 log(R) 之間的值。
• 回傳對應 log2 的線性內插結果，最後乘上 ln(2) 轉為自然對數。

實作如下：

static fixed_point_t fixed_log(fixed_point_t y) {
    if (y <= 0) return 0;

    fixed_point_t L = 1 << (31 - __builtin_clz(y));
    fixed_point_t R = L << 1;
    fixed_point_t Llog = ((31 - __builtin_clz(y)) - Q) << Q;
    fixed_point_t Rlog = Llog + (1 << Q);
    fixed_point_t log;

    for (int i = 0; i < 20; i++) {
        if (y == L) return fixed_mul(Llog, FIXED_LN2);
        else if (y == R) return fixed_mul(Rlog, FIXED_LN2);

        log = (Llog + Rlog) >> 1;
        int64_t tmp = (int64_t)L * R >> Q;
        fixed_point_t mid = fixed_sqrt((fixed_point_t)tmp);

        if (y >= mid) {
            L = mid;
            Llog = log;
        } else {
            R = mid;
            Rlog = log;
        }
    }

    return fixed_mul(log, FIXED_LN2);
}

精度測試

在區間 [0.5, 10] 對每個值與對應 ln() 比較，結果如下所示：

i-ying-tsai@i-ying-tsai-G5-KF5:~/test$ ./test_fixed_log
x(Q23.8)     fixed_log(x)      ln(expected)
---------------------------------------------
    0.5000        -0.691406        -0.693147
    1.0000         0.000000         0.000000
    1.5000         0.406250         0.405465
    2.0000         0.691406         0.693147
    2.5000         0.914062         0.916291
    3.0000         1.097656         1.098612
    3.5000         1.250000         1.252763
    4.0000         1.382812         1.386294
    4.5000         1.500000         1.504077
    5.0000         1.605469         1.609438
    5.5000         1.699219         1.704748
    6.0000         1.785156         1.791759
    6.5000         1.863281         1.871802
    7.0000         1.941406         1.945910
    7.5000         2.007812         2.014903
    8.0000         2.074219         2.079442
    8.5000         2.132812         2.140066
    9.0000         2.187500         2.197225
    9.5000         2.242188         2.251292
   10.0000         2.292969         2.302585

---

測試定點數版本的精確度

ai_mcts_float.c

static float uct_score(int n_total, int n_visits, float score)
{
    if (n_visits == 0)
        return INFINITY;
    return score / n_visits +
           EXPLORATION_CONSTANT * sqrtf(logf((float)n_total) / n_visits);
}

test_fixed_point.c

int play_one_game(player_type_t first)
{
    char table[UTIL_N_GRIDS];
    memset(table, ' ', UTIL_N_GRIDS);
    char winner = ' ';
    char current = (first == PLAYER_FIXED) ? 'X' : 'O';

    while (1) {
        int move;
        if ((current == 'X' && first == PLAYER_FIXED) ||
            (current == 'O' && first == PLAYER_FLOAT))
            move = mcts(table, current);        // fixed-point version
        else
            move = mcts_float(table, current);  // floating-point version

        if (move == -1)
            break;

        table[move] = current;
        winner = check_win(table);
        if (winner != ' ')
            break;

        current ^= 'X' ^ 'O';
    }

    if (winner == ' ')
        return 0; // draw
    if ((winner == 'X' && first == PLAYER_FIXED) ||
        (winner == 'O' && first == PLAYER_FLOAT))
        return 1; // fixed win
    else
        return 2; // float win
}

結果：

i-ying-tsai@i-ying-tsai-G5-KF5:~/kxo$ ./mcts_test 
Game 1: Draw
Game 2: Draw
Game 3: Draw
Game 4: Draw
Game 5: Draw
Game 6: Draw
Game 7: Draw
Game 8: Draw
Game 9: Draw
Game 10: Draw
Game 11: Draw
Game 12: Draw
Game 13: Draw
Game 14: Draw
Game 15: Draw
Game 16: Draw
Game 17: Draw
Game 18: Draw
Game 19: Draw
Game 20: Draw
Game 21: Draw
Game 22: Draw
Game 23: Draw
Game 24: Draw
Game 25: Draw
Game 26: Draw
Game 27: Draw
Game 28: Draw
Game 29: Draw
Game 30: Draw
Game 31: Draw
Game 32: Draw
Game 33: Draw
Game 34: Draw
Game 35: Draw
Game 36: Draw
Game 37: Draw
Game 38: Draw
Game 39: Draw
Game 40: Draw
Game 41: Draw
Game 42: Draw
Game 43: Draw
Game 44: Draw
Game 45: Draw
Game 46: Draw
Game 47: Draw
Game 48: Draw
Game 49: Draw
Game 50: Draw
Game 51: Draw
Game 52: Draw
Game 53: Draw
Game 54: Draw
Game 55: Draw
Game 56: Draw
Game 57: Draw
Game 58: Draw
Game 59: Draw
Game 60: Draw
Game 61: Draw
Game 62: Draw
Game 63: Draw
Game 64: Draw
Game 65: Draw
Game 66: Draw
Game 67: Draw
Game 68: Draw
Game 69: Draw
Game 70: Draw
Game 71: Draw
Game 72: Draw
Game 73: Draw
Game 74: Draw
Game 75: Draw
Game 76: Draw
Game 77: Draw
Game 78: Draw
Game 79: Draw
Game 80: Draw
Game 81: Draw
Game 82: Draw
Game 83: Draw
Game 84: Draw
Game 85: Draw
Game 86: Draw
Game 87: Draw
Game 88: Draw
Game 89: Draw
Game 90: Draw
Game 91: Draw
Game 92: Draw
Game 93: Draw
Game 94: Draw
Game 95: Draw
Game 96: Draw
Game 97: Draw
Game 98: Draw
Game 99: Draw
Game 100: Draw

===== Results =====
Fixed Wins: 0
Float Wins: 0
Draws:      100
Total:      100

---

negamax.[ch]

602a53c

本模組實作了井字棋遊戲中使用的 Negamax 演算法，並搭配 Zobrist Hashing 優化搜尋過程中的重複局面判斷與結果記憶。

主要功能

• negamax_predict: 對外介面，接受目前的棋盤與當前玩家，回傳最佳移動與評分。
• negamax: 遞迴實作 Negamax 演算法，使用 alpha-beta 剪枝與 PV-search 優化。
• negamax_init: 初始化 Zobrist 表格與雜湊值。
• 評分與排序機制透過 history heuristic 提升剪枝效率。

關鍵資料結構與變數

static int history_score_sum[N_GRIDS];
static int history_count[N_GRIDS];
static uint64_t hash_value;

• history_score_sum, history_count: 用於計算每個步驟的歷史平均評分，作為 move ordering 的依據。
• hash_value: 使用 zobrist_table 依據棋盤內容 XOR 建立，用於辨識當前局面並查表。

negamax_predict 函數

move_t negamax_predict(char *table, char player) {
    hash_value = 0;
    for (int i = 0; i < N_GRIDS; ++i) {
        if (table[i] == 'X')
            hash_value ^= zobrist_table[i][1];
        else if (table[i] == 'O')
            hash_value ^= zobrist_table[i][0];
    }

    memset(history_score_sum, 0, sizeof(history_score_sum));
    memset(history_count, 0, sizeof(history_count));

    move_t result = {-1, -1};
    for (int depth = 2; depth <= MAX_SEARCH_DEPTH; depth += 2) {
        result = negamax(table, depth, player, -100000, 100000);
        zobrist_clear();
    }
    return result;
}

• 透過 zobrist_table 建立 hash_value，對應目前棋盤狀態。
• 逐層遞增搜尋深度進行 iterative deepening。
• 每層搜尋後清除雜湊表，避免使用過時資訊。

negamax 遞迴搜尋

static move_t negamax(char *table, int depth, char player, int alpha, int beta)

• 基於原始 Minimax 概念，以 score = -negamax(...) 的方式對立評分。
• 若命中 hash table 則直接回傳儲存的最佳結果（transposition table）。
• 嘗試所有合法步驟，並更新 hash_value 進行狀態轉移。
• 先對最佳歷史步驟進行 full-window alpha-beta 剪枝，其餘嘗試 null-window (PVS)。

PV-Search（主變分搜尋）

在嘗試每個步驟時：

• 第一個步驟使用 full-window (-β, -α)。
• 其他步驟使用 null-window (-α-1, -α) 來快速判斷是否可能更好，再回頭做完整搜索。

這種方式稱為 Principal Variation Search（PVS），能有效加速搜尋。

數學邏輯說明

對於後續的每個子節點

$$i\ge 2$$
我們可以僅使用：

$$\text{Window}=[\alpha ,\alpha +1)$$

這是一個 null window，寬度為 1。

為什麼這樣可行？

假設我們的主呼叫是：

$$\text{score}=\underset{i}{max}(-V_i)$$

我們想知道是否存在某個

$$V_i>\alpha$$。這等價於：

$$\mathrm{\exists }i\text{such that}-V_i>\alpha \Rightarrow V_i<-\alpha$$

如果我們用

$$[\alpha -1,-\alpha ]\mathrm{搜}\mathrm{尋}\mathrm{這}\mathrm{個}{V}_i$$，

• 若搜尋結果落在這個範圍內（fail high），就代表這個節點值得進一步探索。
• 若搜尋結果未超過
  $$-\alpha$$，就直接剪枝。

所以，null-window 會 快速驗證這個分支是否可能比當前 α 更好。

雜湊表應用

使用 zobrist_get 與 zobrist_put 快速存取重複局面的最佳步驟與分數，降低重複計算次數。

---