2018 秋 電腦對局理論

轉來資工的第一學期當然是修一些很酷的課。這門課聽起來就很酷XD 要感謝韜韜學長跟我一起上課，感謝他跟我一起討論上課內容、作業、還有期末作業 <(_ _)>

在上這堂課之前，我對對局的印象停留在高中時讀過的博弈論還有曾經在 UVA 上面用 IDA* 解過的 15 puzzle game 。不過這堂課除了剛開始的 Basic Search Algorithm 介紹之外，都是沒學過很酷的東西，實在是獲益良多啊！

剛開學的時候加簽的人滿出教室來，估計應該有個 70 人吧ＯＡＯ

老師說為了生物多樣性，所以抽中機率的分佈是：

• 非資工系學生： 3 倍機率
• 資工非大四： 2 倍機率
• 資工大四（我）： 1 倍機率

聽起來就超級劣勢！選到課的人 30 個，加簽到 40 人，所以抽 10 個。結果沒想到我居然抽中了，實在是太幸運了！不過老師第三週的時候也說台下還想簽可是沒簽到的可以上來找他人工加簽，結果沒有人上台，所以學期初就是正好的 40 個人。

Basic Search Algorithms

不外乎從最基本的 BFS 與 DFS 開始介紹。說到這裡就要提到這堂課的特色，教的是非常實際的內容。所以當 Main Memory 不夠的時候，可以把 BFS 中的部分 queue 放在 Disk 上並循序 iterate 進主記憶體裡頭，這種 BFS 也有介紹，這是在 ACM 比賽裡面碰不到的。再來就是搜尋時可以進步的技巧，像是 A* 與 Iterative Deepening ，還有湊在一起做 IDA* 。基本上到這裡如果覺得吃力的大概要認真考慮停修了ＱＡＱ

2 Player Game

這裡會介紹會兩人遊戲的許多種類與定義，因為是期中考會考名詞解釋所以上課時可以多想一遍背起來。

C.E. Shannon’s 1950 computer chess paper

學 CS 的人應該會覺得這個人的名字怎麼一直出現。老師會用一整份投影片介紹這篇論文，也建議去讀原論文，在寫期末作業的時候很有用。

這是一篇超級酷的論文，結論的地方把未來搜尋演算法的發展都預言出來了，真的很神。裡面對棋類的處理（初盤、中盤、殘局）， Move Ordering ，還有訂定子力（piece value），審局函數的重要性。老師會談笑風生的提出一些實作 AI 時可能發生的錯誤與細節，像是有可能會吃不到對方的棋子而導致和局這種很荒謬的事。當時大家會覺得好笑彷彿很理所當然似的，結果我寫期末作業時都有一一遇到ＱＡＱ好顯這幾堂課算是有好好聽，一步步的把細節補上看著 AI 進步的成就感真的超讚的！

Alpha-Beta Search

Aka. Min-max algorithm ，老師會介紹演算法的證明，把節點分成不同 Type 並保證搜尋的節點在一定的範圍內。證明跟定義一定要好好背，因為是期中考必考。雖然作業沒有要求實作這個演算法，但是我覺得寫個 Alpha-Beta 來跟 Monte Carlo PK 應該會蠻有收穫的。

Homework 1 – Sokoban Solver

倉庫番（aka 推箱子）應該是大家蠻耳熟能詳的遊戲。這份作業就是從老師介紹的 Basic Search Algorithm 裡頭試圖生出給定盤面下正確走法的程式，詳細敘述可以看這裡。這個單人遊戲在 Computer Game Theory 裡面算是很有代表性的一個遊戲，因為他是少數幾個人類目前表現得會比電腦好的遊戲。（在大盤面上也是）

從這裡就會開始體驗到搜尋演算法的樂趣，剛開始會生出一個基本的 BFS ，只能解出小範圍的測資。再來加入剪枝，陸續測試各種 Heuristic ，做出 Reverse Search 之後做 Bi-Directional Search ，最後為了變更快還幫做了盤面狀態壓縮。真的是獲益良多的一份作業。

Midterm

老師很逗，滿分 180 分的就是暗示考試時間 180 分鐘你該對題目的時間分配。

會在考試前開示各種必考題與題型，記得去上課。

Monte Carlo Search

自從電腦速度大增之後， AI 表現上在 2013 終於超越 Alpha-Beta 的演算法。隨機走不下，依靠大數法則的抽樣（靠賽）來判斷各走法的好壞。這時候要小心觀察樹的展開，展開良好的樹才可以導出正確的結果。介紹完基本演算法後有一些 enhancement ，這些加強是在作業二時可以加進去實驗看看。

Homework 2 – Solve variation of Einstein Würfelt Nicht

中文名字好像叫愛因斯坦棋。要用 Monte Carlo Search 、UCB & UCT 、 還有 （Progressive Pruning / RAVE）擇一，以上三者來解出愛因斯坦棋的一個變形。規則一言難盡，可以直接看 spec 。其實玩一玩這個棋就會發現，先手優勢極大，而且好壞步是非常明顯的。由此我推斷 Alpha-Beta 應該比 Monte Carlo 更適合這個遊戲才對。這份作業強制要求了你去體驗各種 enhancement ，不過寫起來不難，我花的時間反而比前一個作業少XD

Enhanced Alpha-Beta Search: NegaScout

結合了 Scout 的 Alpha-Beta Search ，也是期末作業要求實作的演算法。這堂課我去體檢了，所以沒聽到ＱＡＱ～

Advanced Techniques

介紹了 Transposition Table 、 Zobrist’s Hash 、還有很多可以被應用在期末作業的 Heuristic ，像是 Killer Heuritic 還有 History Heuristic 。可惜這兩個 Heuristic 來不及在期末作業裡面做出來，這兩個應該會大大的增加 AI 的實力。而 T-Table 還有 Z-Hash 我覺得都是很實用的技巧，對演算法的 Refinement 真是這門課的精華啊！

## Final Project – Chinese Dark Chess AI

期末作業要做出暗棋 AI ，然後在學期結束後的下一週老師會挑一天來讓同學把 AI 拿出來互相傷害，是為 NTU CSIE CUP of Computer Chinese Dark Chess Competition 。

作業要求時實做 NegaScout 與 T-Table 。因為其他各種 Project 的干擾，暗棋大賽（2018/01/17 9:00 AM）倒數 36 小時才開始動工，不過大。概剩 9 個小時的時候驚險地完成了 AI 。短短時間內體驗了設計 AI 的魅力。剛開始會與助教提供的 template 跳恰恰，雙方進入重複盤面導致和局。再來解決跳恰恰的問題之後要變成無法成功把對方剩餘的棋子困住而導致 30 步內沒吃子而和局。這才想起來老師那時候談笑風生講出來的那些問題，原來真的都遇到了ＯＡＯ

我發現審局函數佔了非常大的作用，從吃子，到殘局的困子都是中間卡住無法取勝時加進去的。另外搭配用 Z-Hash 實做出來的 T-Table 來做加速與判斷重複盤面。其實這大概就可以算是 AI 的基本架構了。再來的 Heuristic 還有殘局資料庫就是去優化這個基本架構。寒假這陣子無聊來把 History Heuristic 還有 Killer Heuristic 也加進去看看。

當下拿到第一場真人首勝時實在是非常開心XD。後來發現原來我的 AI 架構其實算是蠻完整的！？中規中矩的就贏了蠻多場，總共比了 12 場，戰績 6 勝 4 敗 2 和，排名第七！因為勝負分是正的關係，所以還拿到了加分，算是為這堂課畫下很好的句點。

在比暗棋大賽的過程中才發現有一些情況是寫的時候沒有想到的，因為 template 太弱了XD 其他像是解決複雜的殘局還有運氣不好無法取勝時想辦法逼和的走法這些都是漏掉的，要不然應該可以再少一敗跟多兩勝。另外在開發 AI 時程式逐漸變得龐大，而用 Unit Test 來確保程式正確進行也是我學到重要的一課。而在 AI 對局的時候其實會產生一些有助於 debug 的數據，其實也需要適當的 log 起來，這是我沒做到需要改進的。

Conclusion

學期初 40 個到最後只剩下 25 個人參加暗棋大賽（停修率 35%！），雖然只有三份作業但是每一份都讓你吃到飽XD 但是這堂課真的是一門程式設計技巧大補丸，不上可惜。

最後謝謝教授幽默的講課，還有助教非常用心的準備作業！

Original link: eopXD