HackMD
2025q1 Homework3 (kxo)
contributed by < weiso131 >
注意項目的使用，亦即用 ## 和 ###
鍵盤事件處理
觀察程式
發現 xo-user.c 藉由修改 kxo_state 這個 sysfs
來修改 attr_obj
暫停/重啟
原本的程式就能做到這個功能
然而，若是在某個使用者視窗暫停之後
其他視窗皆無法藉由 ctrl + P 繼續執行
若是將該視窗關閉，就再也無法讓其他視窗繼續執行
這是因為 read_attr 不同步
導致其他使用者嘗試對 /dev/kxo 進行 read
此時因為 attr_obj 的 display 被設成 1
kfifo 不會有新的物件加入
這會讓 read 陷入無盡的等待
此問題可以藉由在 user space 的迴圈中
不斷藉由讀取 kxo_state 更新 read_attr
來解決
commit 98edb06
儲存對亦資料
history.[h/c] 實作對應的 API
void history_init(void);
初始化 historyvoid history_update(uint64_t move);
用來紀錄棋局內擺放棋子的位置void history_new_table(void);
用來重新開啟一場棋局void history_release(void);
用來釋放 history 所佔的記憶體
這必須放在 del_timer_sync 之後
否則可能會因為觸發計時導致存取已經釋放的指標
commit ce4cd73
離開對亦並顯示棋局紀錄
對於顯示棋局紀錄其實有兩種方法
- 在 release 的時候根據
attr_obj.end的狀態判斷使用者是否按下 ctrl + Q ， 再用 print_string 利用將資料輸出到呼叫 release 的使用者commit 3333893
- 利用 ioctl 讓使用者在跳出迴圈後可以進行資料讀取，並由使用者處理輸出的工作
commit 79422ee
第一種方法的好處就是容易實作，但它在有多個使用者的時候，必須等待前個使用者將資料全部輸出才能換下個使用者輸出，這在場次很多的時候問題會變得更明顯。
此外，若能夠讓使用者實際存取到資料，未來想在使用者端加入機器學習會變得更容易。
在使用 ctrl + q 離開對亦之後，因為 attr_obj.end 被設成 '1'
再次執行 xo-user 將不會進入迴圈，必須重新安裝核心模組
這不太方便
因此我在最後一個使用者進行 release 時，將 attr_obj.end 設成 '0' ，重新執行將不再需要重新安裝核心模組
commit 50e778c
將 draw_board 移至 user space
單純將 draw_board 結果換成回傳 table
commit dc4cef2
利用 bit 儲存對亦資料
提供數學分析
作業說明的快速檢查勝方出現的方法
作業說明中以 is_win 函式快速判斷棋盤的狀態，利用位元運算同時降低空間占用並提升效率。
觀察 is_win 與 move_masks 可發現其原理就是利用 4, 2, 1 去湊出 7 來代表連成一線，這樣每條線的狀態都占用 1 byte 來表示。
這個方法能做到同時表達棋盤位置資訊與快速計算是否有連線。
觀察 check_win 使用
check_win 可以利用 table 的資訊判斷是否有勝方出現，並回傳勝方的棋子圖案。
此方法的缺點是用到了大量迴圈，相較能用 bitwise 快速判斷的方法，明顯非常沒效率。
這個函式在 main.c, mcts.c, negamax.c 都有被反覆使用
而 mcts.c 與 negamax.c 光是在一步棋的預測就有可能多次呼叫 check_win ，若能增加其執行效率應該能有效提昇整個核心模組的效率。
把棋盤位置資訊與連線狀態分開儲存
用 2 個 bit 儲存連線狀態，可用 48 bit 儲存其中一方的連線狀態
32 bit 儲存棋盤的位置資訊(前 16 bits 存 O ， 後 16 bits 存 X)
總佔用記憶體是 128 bits = 16 bytes ， 與原本的 table 相同
回傳棋盤位置資訊給使用者時可以只回傳 32 bits
用 2 個 bit 儲存連線狀態的實作
此方法參考了 DETECT_NULL 的方法，把它從偵測 0000 變成偵測 00
將空棋盤初始化為 0x5555 ， 也就是 0b0101010101010101
對於任意一條線， 0b01 代表差三個， 0b10 代表差兩個， 0b11 代表差一個
0b00 則代表連成一線
利用 bitwise 傳遞 table 資訊給 user space
單純將傳遞資料的部份改成 bitwise 雖然能減少複製到 kfifo 與 user space 的時間(bitwise 儲存方法只需 4 bytes ，原本的方法需要 16 bytes) ，然而，可能會因為將字元陣列轉換成 bitwise 表示方法而花費更多時間。
在這個修改之後，會將 main.c, mcts.c, negamax.c 儲存 table 的方法換成 bitwise 且能快速判斷勝負的版本，這次的修改主要是為了避免一次進行大幅度的修改，增加版本控制難度。
commit 37f2dd6
將棋盤位置資訊與連線狀態分開儲存的方法應用到 main.c
在 kxo_table.h 定義 struct table 儲存棋盤位置資訊與連線狀態
並將 main.c 儲存棋盤的方法從字元陣列換成 struct table
它可以利用 bitwise 操作
提取使用者端所需的棋盤格式與
降低判斷勝負所需的時間
雖然這次的修改免去了上次修改在儲存到 kfifo 時所需的轉換
也成功將 check_win 換成更高效的實作 is_win
然而，在提供資訊給 mcts 與 negamax 時仍須將 struct table 轉成字元陣列，而且這兩個算法內部仍使用 check_win。
commit a937e43
