HackMD2025q1 Homework3 (ttt)
contributed by <I-Ying-Tsai>
開發環境
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，無.writehandler。 - 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/對齊問題）。
- 範例：
- user/kernel 都 include 此 header。
2. 將棋盤繪製與互動邏輯移至 user space
- 技術細節
- 原本的 kernel module 提供整盤棋盤字串的繪圖 buffer（kfifo），現在 user space 僅需向 kernel 請求“最佳下一步”，其餘顯示與互動皆在 user 空間完成。
- 只需執行：
- user space 負責根據回傳的 index 更新自己的棋盤、重繪 UI。
- 優點
- 極大減少 kernel/user 資料交換成本（只需一個 int 而非整盤棋盤字串）
dmesg 如下：
未來可能的修改目標：
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 模組（write1至 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：
其他改動
- 使用
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位，在加上s0xoro_jump: 執行一次跳躍操作，可用於平行亂數序列產生，使不同序列互不重複。xoro_init: 使用clock_gettime中的tv_sec與tv_nsec初始化亂數種子，確保每次執行產生不同亂數。
程式中使用的 state_array 結構儲存了 128-bit 的內部狀態，以兩個 64-bit unsigned 整數陣列成員組成。
亂數測試與結果
測試目的
主要驗證 xoro_next 輸出的值是否採用接近於均勻分佈，是否可用於開發通用性模擬。
測試方法
generate_xoro_output.c
xoro_test.py
測試結果
- 資料數: 1000000 次
- 擴展: 用
& 0xFF檢驗每 8-bit 的表現
參考
xoroshiro128+wyhashseed 生成參考
zobrist.[ch]
commit 80d53d1
實作細節
zobrist_init():
為每個棋盤格與每個玩家（'X' 和 'O'）生成隨機的 64 位整數權值，並初始化雜湊表。- 使用
wyhash式樣的無狀態 PRNG 實作產生亂數。
- 使用
-
在
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。
雜湊值初始化（初始轉換）：
解釋：
- 在遊戲開始的盤面上，「第一次」從
char table[]把盤面轉成雜湊值 hash_value被視為目前盤面的唯一識別碼- 這是 雜湊值的初始化階段
雜湊值動態更新 + 還原：
解釋：
- 每次嘗試下一步時，會對 hash_value XOR 加入該格子的雜湊值
- 完成評估後，用 相同 XOR 再次操作還原回原來狀態
為什麼這樣碰裝機率會降低？
我們說：「n 個 hash key 全部落在不同的桶」的機率是：
取對數：
因為 ，我們可以用泰勒展開：
保留第一項近似就好：
所以總和變成：
兩邊取 exp：
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 上為：
- 涉及 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)轉為自然對數。
實作如下：
精度測試
在區間 [0.5, 10] 對每個值與對應 ln() 比較，結果如下所示：
測試定點數版本的精確度
ai_mcts_float.c
test_fixed_point.c
結果：
negamax.[ch]
本模組實作了井字棋遊戲中使用的 Negamax 演算法，並搭配 Zobrist Hashing 優化搜尋過程中的重複局面判斷與結果記憶。
主要功能
negamax_predict: 對外介面，接受目前的棋盤與當前玩家，回傳最佳移動與評分。negamax: 遞迴實作 Negamax 演算法，使用 alpha-beta 剪枝與 PV-search 優化。negamax_init: 初始化 Zobrist 表格與雜湊值。- 評分與排序機制透過 history heuristic 提升剪枝效率。
關鍵資料結構與變數
history_score_sum,history_count: 用於計算每個步驟的歷史平均評分，作為 move ordering 的依據。hash_value: 使用 zobrist_table 依據棋盤內容 XOR 建立，用於辨識當前局面並查表。
negamax_predict 函數
- 透過
zobrist_table建立hash_value，對應目前棋盤狀態。 - 逐層遞增搜尋深度進行 iterative deepening。
- 每層搜尋後清除雜湊表，避免使用過時資訊。
negamax 遞迴搜尋
- 基於原始 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），能有效加速搜尋。
數學邏輯說明
對於後續的每個子節點
我們可以僅使用：
這是一個 null window，寬度為 1。
為什麼這樣可行？
假設我們的主呼叫是：
我們想知道是否存在某個 。這等價於：
如果我們用 ，
- 若搜尋結果落在這個範圍內（fail high），就代表這個節點值得進一步探索。
- 若搜尋結果未超過 ，就直接剪枝。
所以，null-window 會 快速驗證這個分支是否可能比當前 α 更好。
雜湊表應用
使用 zobrist_get 與 zobrist_put 快速存取重複局面的最佳步驟與分數，降低重複計算次數。
