# 2025q1 Homework3 (kxo)
contributed by < `weiso131` >

{%hackmd NrmQUGbRQWemgwPfhzXj6g %}

:::danger
注意項目的使用，亦即用 `##` 和 `###`
:::

## 鍵盤事件處理
觀察程式
發現 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](https://github.com/weiso131/kxo/commit/98edb068e9b806b4c2cb14b2ea03d22ad76af7a8)

## 儲存對亦資料
`history.[h/c]` 實作對應的 API

- `void history_init(void);`
初始化 history
- `void history_update(uint64_t move);`
用來紀錄棋局內擺放棋子的位置
- `void history_new_table(void);`
用來重新開啟一場棋局
- `void history_release(void);`
用來釋放 history 所佔的記憶體
這必須放在 del_timer_sync 之後
否則可能會因為觸發計時導致存取已經釋放的指標

> commit [ce4cd73](https://github.com/weiso131/kxo/commit/ce4cd739de3e844aa50fd2238f5ea0291a54f94c)
## 離開對亦並顯示棋局紀錄
對於顯示棋局紀錄其實有兩種方法
1. 在 release 的時候根據 `attr_obj.end` 的狀態判斷使用者是否按下 ctrl + Q ， 再用 [print_string](https://sysprog21.github.io/lkmpg/#replacing-print-macros) 利用將資料輸出到呼叫 release 的使用者
> commit [3333893](https://github.com/weiso131/kxo/commit/33338933b692df852cf1d649ad99526a08cbc357)
2. 利用 ioctl 讓使用者在跳出迴圈後可以進行資料讀取，並由使用者處理輸出的工作
> commit [79422ee](https://github.com/weiso131/kxo/commit/79422ee66fb5e64ac9938f8f3e94d90d820e7fc2)

第一種方法的好處就是容易實作，但它在有多個使用者的時候，必須等待前個使用者將資料全部輸出才能換下個使用者輸出，這在場次很多的時候問題會變得更明顯。
此外，若能夠讓使用者實際存取到資料，未來想在使用者端加入機器學習會變得更容易。

在使用 ctrl + q 離開對亦之後，因為 `attr_obj.end` 被設成 `'1'`
再次執行 xo-user 將不會進入迴圈，必須重新安裝核心模組
這不太方便
因此我在最後一個使用者進行 release 時，將 `attr_obj.end` 設成 `'0'` ，重新執行將不再需要重新安裝核心模組

> commit [50e778c](https://github.com/weiso131/kxo/commit/50e778c4b35e7e9e5e3360e61a53299b28982101)

## 將 draw_board 移至 user space
## 單純將 draw_board 結果換成回傳 table
> commit [dc4cef2](https://github.com/weiso131/kxo/commit/dc4cef24b53be5cd18acfadfa514c39c531eee05)

## 利用 bit 儲存對亦資料
:::danger
提供數學分析
:::

### 作業說明的快速檢查勝方出現的方法
作業說明中以 `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](https://github.com/weiso131/kxo/commit/37f2dd6268ade28fc23062c3b174f7e7c35b70df)

#### 將棋盤位置資訊與連線狀態分開儲存的方法應用到 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](https://github.com/weiso131/kxo/commit/a937e433afa01ccb49fb6918393ac19c84d9ca1b)

#### 修改 `mcts.c`

#### 修改 `negamax.c`