# 電腦對局理論 Computer Games 期末大賽懶人包
###### tags: `Computer Games`

這門課最有有趣的評分項目沒有之一：**期末大戰**。這是一篇幫我自己複習學到什麼同時告訴學弟妹這麼多東西可以實作要做哪個比較好的一篇文。

這是 111 Autumn 的內容，每學期都會有些許改變請注意。

[TOC]

## 比什麼？

**Hollow NoGo**。首先我們有個 $9\times 9$ 的盤面，

<img style="display: block;margin-left: auto;margin-right: auto;width: 30%;" src="https://i.imgur.com/M5MFLhO.png">

黑先，黑棋和白棋輪流下，一回合下在一個 `+` 號上，但有些位置不能下

- 有人下過的位置
- 下了會使自己沒氣的位置
- 下了會使對方沒氣的位置

**氣**的規則就和圍棋一樣，然後沒地方下的人就輸了。詳細請見[這裡](https://webdocs.cs.ualberta.ca/~mmueller/nogo/rules.html)。

一些知道會更好的 remarks

- 場上 $3\cdot4$ 個位置本來就不能下，所以叫 Hollow
- Hollow 的位置每學期都會變
- 總共 $69$ 個可下位置
- 約 $61$ 至 $63$ 手就會結束
- 約 $38$ 到 $42$ 手就會分出勝負，也就是一人 $20$ 手

再來就是各種大家可以玩玩看的技巧。

## MCTS

實用指數：★★★★★


> 圖片來源: I-Chen Wu slide monte-carlo.pdf page 36

BJ4，一切都是從這個出發，但有一些要注意的：

- selection 時，自己的 node 選的是自己的勝率+exploration 最高的，但對手回合應該是 **-自己的勝率**+exploration，就 min-max 的概念
- 跑完 MCTS 要選最好的一步，這裡通常是選 visit 最多次的，而非勝率 $Q$ 最高的，

## RAVE

實用指數：★★★☆☆

All moves as first (AMAF) 的概念在這遊戲非常適用，有些位置基本上就是要點基本上一定先搶著下，例如邊邊E9、角落A9。

但老實說只要 MCTS 跑足夠多次，這個幫助的程度就漸漸降低，因此勝率的提升有但不明顯。不過通常在上一個 project 就實作了吧，不放白不放。

## Bitboard

實用指數：★★★★★

非常重要，大幅加速流程，看看助教預設的程式中的 `check_liberty` 那就是你 `N` 設不高的罪魁禍首，是助教故意放來懲罰不仔細看扣的同學的。個人改 bitboard 之後同樣時間 `N` 約可大 5 倍。

基本上就是用 128 bit `unsigned int` 分別存黑棋和白棋。但最麻煩的是檢查一個位置能不能下，可以是

- 每次呼叫 `place` 的時候檢查能不能下
- 每次 `place` 完都維護雙方可下的位置
- 對一個 board 都先一個函數取得可下位置，然後 `place` 時只考慮這些位置

當中 bit count、bit scan 之類上課沒提多少的挖溝都會用到。

## UCB1-Tuned

實用指數：★★☆☆☆

slide 提到一個實作上更好的公式，勝率變化沒什麼感覺，但不改白不改。

## Parallelization

實用指數：★★★★★

用 CPU 的力量取勝，基本上有兩種平行化方式：

- root parallelization
- 每個 thread 跑自己的 MCTS tree，最後再蒐集起來看 visit 最多的。好實作，提升也很明顯
- tree lock-free parallelization
- 每個 thread 都長同一棵樹，但任何的 mutex 都會大幅降低速度，因此有各種稍微冒計算誤差的風險，但至少不會讓程式炸掉的 lock-free 方法

Tree lock-free parallelization 大概幾個實作重點：

- memory pre-allocation
- 一開始，每個 thread 都先生好自己存 node 的空間。在 Expension 階段，用掉一個自己的 node 空間，然後再一個 instruction 把這個 node 插到樹上。這樣即使被其他 thread 蓋掉了也不會造成 memory leak。
- virtual loss
- 在 Selection 階段邊往下鑽就把路過的 node visit $+1$，然後 Backpropagation 只修改 win count。差別是先 + visit 就像假設輸了，那其他 thread 會傾向跑其他 node，減少 conflict 的機會。
- Backpropagation
- 這裡有大量數字要 `++` (critical section)，最搞笑的就是這裡沒有任何改動，你就是祈禱 thread 不要撞得亂七八糟。

但 **Tree parallelization 是個危險的坑！**

- $c$ 是調整 exploitation 和 exploration 比例的參數，太大會 exploitation 不夠，搜不夠深，太小 thread 又會撞到懷疑人生。調出最好的 $c$ 又很花時間
- 你家 CPU 太好也會撞的很嚴重，隔壁同學出動 70 thread 輸人，最後還自己調降 thread 數量
- 這種時候結合 root 和 tree，例如 7 棵樹，每棵放 10 個 thread 或許是個解決辦法
- root parallelization 的效果其實出奇的好，**建議先做好 root 的，有空再來改成 tree**

## Enhanced Time Management

實用指數：★★★★☆

公式如下

<img style="display: block;margin-left: auto;margin-right: auto;width: 80%;" src="https://i.imgur.com/PmLuTeI.png">

> 來源 2018-11-27 slide 'Time Management for MCTS Applied to the Game of Go.pptx' by His-Chun Kao, Tzu-Yee Yang 

簡單來說在第 $\text{MaxPly}$ 步會想最久，越遠想的時間就越少。

相當重要，如前所述，第 $10$ 步到第 $20$ 步要好好想，再之前下稍微爛一點這部分也可能逆轉，再之後基本上勝負會突然很明顯，加上實作也不難。

## EARLY-C Time Management

實用指數：★★★☆☆

假設最好下法和第二好下法的 visit 差異足夠明顯，也就是當下只有一個最好的位置可下，那就可以提早跳出 MCTS，減少思考時間。

會假設現在跑到第 $i$ 次 MCTS，總共要跑 $N$ 次，然後抓剩下的 $N-i$ 次中有 $0.5$ 都進了第二好的 node 裡，也就是當

$$
v_2+0.5(N-i)<v_1
$$

那 $v_1$ 和 $v_2$ 的差距就算是難以補救了，於是直接跳出。

立意良善，但小心聰明反被聰明誤：

- 實作完，你可能會發現剩餘時間變多了，因為最後 $10$ 手蹦蹦蹦一下就出來了
- 你見獵心喜，想充分利用時間，於是把 `N` 調高，或把 Enhanced Time Management 的 $c$ 調低

問題來了，當遇到強敵時，EARLY-C 的機會會大幅減少，那你當時調高的參數會導致縣在前幾手思考過久，導致 $10$ 到 $20$ 手時被逆轉。另一個要注意的狀況是例如說黑方第一回合，如果你跑夠多會發現最好的起手是邊邊：E9、A5、E1、J5 任選，那就會發生第一好第二好的手本質上都是一樣的，但 EARLY-C 並不會幫你跳出。

上述問題的解法其實不難，就怕比賽才發現，先小輸了一把，第一名拱手讓人 (這我)

- EARLY-C 觸發並不穩定，不要貪圖他的發生，有發生，Enhanced Time Management 的 $\text{RemainingTime}$ 就會變高，自然會調整後續的思考時間
- 可以檢查第一第二好的手是否本質一樣 (旋轉、翻轉後是同個盤面)，其實也可以不要管這種東西

## Tree Recycling

實用指數：★★☆☆☆

想法是這樣，不要每回合都從全新的 tree 開始長，而是從上回合長的 tree ，抓現在盤面的那個 node (某個兩層深的點，自己做一步，對方做一步) 當新的 root，這個樹多大不知道，但越大就越賺。

效果如何呢？單獨使用的效果其實不怎麼樣，對方的 MCTS 和自己的思考方式不一樣，能留到 十多 % 的 tree 就要偷笑了。但，如果不是單獨使用呢...？

## Think when Opponent Think

實用指數：★★★★☆

在 `take_action` 要 return 自己的 move $a$ 之前 ($s\xrightarrow{a}{}s'$)，開 thread 往 $s'$ 持續跑，跑到下一次自己的回合。對方想越久自己也跑越久。

單獨 Tree Recycling 保留的是兩層深的 node，而這裡是一層，也就是猜到對方下什麼回應就好，保留比例大幅提升。在你真正的 MCTS 還沒開跑前 tree 就已經有上百萬個 node 了。

還有一個就是如果對方沒做 Time Management，最後 $10$ 手指要靠對方的時間就能知道要回哪，搭配 EARLY-C 快速結束，會有秒下的樣子，非常爽快 (有贏的話)。

## Cheat Sheet

實用指數：★★★★☆

在空間允許的範圍內，前幾手 (大概 $4$ 手以內) 的下法先自己用很大的 MCTS 先算出該下哪，然後存起來，正式比就讀進來，每次先檢查有沒有先算過，有就省大量時間。

前幾手如果在打扣的過程中都有看自己的扣怎麼下的人，其實大概就知道該下哪。但前幾手複雜度高，跑不夠多又會不小心下出大便手。尤其是黑方第一手花 50 秒在決定要下 E9、A5、E1、J5 哪一個不是超肚爛的嗎？

把關鍵手，真正要好好思考的手 $1\sim20$，縮減到 $5\sim 20$。有時間記得做一下這個。

注意不是前幾手每個組合都要記錄，只要記錄比較可能發生的，例如就兩個夠強的 MCTS 互打，順便紀錄就好。

## Simulation Balancing

實用指數：★★★★★

如果你該做的都做了，遇到強敵會有這個現象：

- 前幾手算出來勝率都會漸漸提高，但大概卡在 $6$ 成上不去
- 之後突然 $3$ 手內勝率大幅下降，然會快速歸 $0$
- 因為 random simulation 的勝率和真實有差異，一直誤以為自己處於優勢，直到對方下出某個實際上是強手，但 random simulation 一直以為很爛的一手

那你就是時候加這個。這通常是 paper 報告的最後一組。他應該很有用，但花時間，code 也要改，還有一些要注意的部分。總之這裡詳細一點的解釋這怎麼做，畢竟報告 10 分鐘我不信有多少人聽懂。

MCTS 中 Simulation 的部分是隨機下看誰贏，這聽起來就超大便的，那我們要改進什麼？我們希望 simulation 反映**勝率**，也就是假設一個 node simulation 很多次，那贏的機率應要趨於真正的勝率。

真正的勝率？一個盤面真正誰贏誰輸是決定性的，這裡的勝率到底是什麼？其實只要理解成給一個很強的 solver 跑，他說勝率多少就多少，例如可以想像是一個 MCTS，就在現在 MCTS 的 leaf 那個位置再跑一個 MCTS，我們稱它為**神解**。

但我們當然沒那美國時間在每個 leaf 都再跑一棵 MCTS，因此要有效率的 simulation，做很多次要能趨近神解。

前置動作是這樣的，我們假設有個方法 $\phi_\theta$ 可以決定每個 move 的**分數**，很簡單的方式是 $\phi$ 吐出來的是一個向量 $\phi(s,a)$，然後內積一個另一個分數向量 $\theta$ 得到分數。這個概念在 threes 的 $TD-\lambda$，上課舉例的五子棋都有講過類似的概念。例如簡單點 $\phi(s,a)=(x,y)$，$x$ 是下完 $a$ 後自己能下的位置數，$y$ 是下完 $a$ 後對方能下的位置數。

然後透過 soft-max，給個 move 被下的機率為

$$
\phi_\theta(s,a)=\frac{\exp(\phi(s,a)^T\theta)}{\sum_b\exp(\phi(s,b)^T\theta)}
$$

去做 simulation。所以在你決定好一種 $\phi$ 的定義法後，現在要把 $\theta$ 調到一個以上步驟做出來會類似神解的數字。

- 所以分數 $\exp(\phi(s,a)^T\theta)$ 就類比於這步的強度嗎？錯！兩者有很微妙的差異，例如現在可能發生我下一個大便手，對方也下一個大便，但總之跑出來勝率是接近神解的就好
- 別忘了這裡要強調效率，因此 $\phi$ 不要定義的太複雜，搞什麼奇怪的 network 或 N-tuple，搞到 MCTS 的次數降太多就 GG 了 (這我)

好所以該如何 train 我們的 $\theta$ 呢？直接上圖

<img style="display: block;margin-left: auto;margin-right: auto;width: 80%;" src="https://i.imgur.com/52rBWza.png">

$s_1$ 就是某個 leaf，首先算出這個點的神解，記做 $\hat V^*(s_1)$，然後做 $M$ 次算出用目前的 $\theta$ 做出來的 simulation 的勝率多少，記做 $V$。接下來做 $N$ 次算說平均是什麼向量導致了這個勝率 $V$ (這裡的 $\psi$ 和前面的 $\phi$ 是同個東西)，記做 $g$，這裡 $z$ 是勝率。

好現在 $\hat V^*(s_1)$ 和 $V$ 有些差異，那該如何調整 $\theta$ 呢？就照 $\hat V^*(s_1)-V$ 的方向調，$a$ 是 learning rate。

## 小結

這比賽最荒謬的就是其實真的想把扣寫好的不多，這比賽保底 70 分，有人第二手投降的，有的 project 3 沒改就上的，還有如果你沒自己的電腦，用 tcglinux，那很可惜你分數也不會多高，只能一個 thread 記憶體也有限。

然後我 time management 沒調好拿了第二，第一是 bitboard + root parallelization，其他都沒做。總之，想一些奇怪的方法看如何增強自己的程式，還是蠻有趣的。