# linux2025-homework3

:::danger
注意書寫規範！
:::

$ make
make -C /lib/modules/6.11.0-19-generic/build M=/home/neat/YCL/linux2025/kxo/kxo modules
make[1]: Entering directory '/usr/src/linux-headers-6.11.0-19-generic'
warning: the compiler differs from the one used to build the kernel
  The kernel was built by: x86_64-linux-gnu-gcc-13 (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0
  You are using:           gcc-13 (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0
  CC [M]  /home/neat/YCL/linux2025/kxo/kxo/main.o
/home/neat/YCL/linux2025/kxo/kxo/main.c: In function ‘kxo_init’:
/home/neat/YCL/linux2025/kxo/kxo/main.c:494:20: error: implicit declaration of function ‘vmalloc’; did you mean ‘kmalloc’? [-Werror=implicit-function-declaration]
  494 |     fast_buf.buf = vmalloc(PAGE_SIZE);
      |                    ^~~~~~~
      |                    kmalloc
/home/neat/YCL/linux2025/kxo/kxo/main.c:494:18: warning: assignment to ‘char *’ from ‘int’ makes pointer from integer without a cast [-Wint-conversion]
  494 |     fast_buf.buf = vmalloc(PAGE_SIZE);
      |                  ^
/home/neat/YCL/linux2025/kxo/kxo/main.c:505:9: error: implicit declaration of function ‘vfree’; did you mean ‘kvfree’? [-Werror=implicit-function-declaration]
  505 |         vfree(fast_buf.buf);
      |         ^~~~~
      |         kvfree
cc1: some warnings being treated as errors
make[3]: *** [scripts/Makefile.build:244: /home/neat/YCL/linux2025/kxo/kxo/main.o] Error 1
make[2]: *** [/usr/src/linux-headers-6.11.0-19-generic/Makefile:1931: /home/neat/YCL/linux2025/kxo/kxo] Error 2
make[1]: *** [Makefile:224: __sub-make] Error 2
make[1]: Leaving directory '/usr/src/linux-headers-6.11.0-19-generic'
make: *** [Makefile:13: kmod] Error 2

在補上以下標頭檔之後即可正常make

--- a/main.c
+++ b/main.c
@@ -9,6 +9,7 @@
 #include <linux/sysfs.h>
 #include <linux/version.h>
 #include <linux/workqueue.h>
+#include <linux/vmalloc.h>

`$ make` 之後產生 kxo.ko
接著執行 `$ sudo insmod kxo.ko`
為了執行此 command 要先進 BIOS 將 security boot disabled

最後才能執行 `$ sudo ./kxo-user`

:::danger
說好的進度呢？
:::

### MCTS
[影片說明](https://www.youtube.com/watch?v=J3I3WaJei_E)
1. Select
> 選擇一個沒有 children 的 node
2. Expand or Rollout
> expand: 對某個沒有 children 的 node 產生新的 children
> rollout: 從目前的狀態開始，模擬一場遊戲，直到遊戲結束
> 若該 node 是全新的，則進行 rollout，若該 node 是舊的(已經被更新過) 則進行 expand
3. Backpropagate
> 把 node 更新並不斷往上更新，直到 root 為止

每個 node 會記錄 ${w_i}$ 和 ${n_i}$，前者是勝利次數，後者是模擬次數。接者，我們根據 UCB 選擇每次要 select 哪一個 child，其中 UCB 為 Upper Confidence Bound: $\frac{w_i}{n_i} + C \sqrt{\frac{\ln N_i}{n_i}}$
> ${w_i}$ : # wins
> ${n_i}$ : # simulations
> ${N_i}$ : Parent's # simulations
> $C$ : 可自己調整的參數，常用的值是 $\sqrt{2}$

- 前項 $\frac{w_i}{n_i}$ 代表勝率，若一個 node 的勝率越高 那 UCB 也會越高，之後也更有可能走訪這個 node。所以前項是 exploitation => 選擇已知最好策略
- 後項 $\sqrt{\frac{\ln N_i}{n_i}}$ 代表如果我在模擬時走訪該 node 越多次， UCB 會下降。所以後項是 exploration => 探索其他未知路線