Day23 Opening Book
===
以前在參加圍棋比賽的時候，我都會特地準備開局，就是對我想下出的開局做研究，然後將其記熟，比賽時在開局階段就不必花費太多時間思考，基本上所有棋手都會先研究開局，畢竟比賽會有時間限制，而開局階段是最能夠提前研究的階段，大多數棋手都會盡量節省開局的用時，將時間與精力投入到中後半盤。
不只是圍棋，西洋棋跟象棋也有很多知名開局，圍棋的話除了開局還有定石，就是局部雙方都可以滿意的下法，人類可以提前將開局的研究結果記起來，那電腦為什麼不行呢？
昨天提到了利用Transposition Table來儲存過往盤面資訊，那同理我們也可以先儲存開局啊，把計算好的開局先儲存起來，只要遇到相同盤面就只要查表就好了，這也是一種可以大幅提升程式棋力的優化方式。

## Opening Book
Opening Book (開局庫)就是用來儲存開局的，而開局庫的好處除了讓程式在開局時的速度提升之外，還有另外兩大優點：
1. **避免重複錯誤**：如果你的程式會在某個情況下犯錯，那它再次遇到一樣有機會犯錯，如果這個錯誤是發生在開局時，那使用開局庫就是一種很簡單有效的優化方式。
2. **多樣化開局**：開局庫能夠提供多種開局選擇，讓程式不會總是選擇相同的開局，就算你在MCTS中有加上更多的隨機性，但它的選點始終有限，像是目前的圍棋AI的實力都已經遠超人類，那加入開局庫不是為了讓AI棋力變得更強，而是為了貼近人類的需求，讓AI能下出類似指導棋效果的開局，這樣才有教學意義。
(像是黑嘉嘉圍棋教室中提供多種不同風格的AI，歡迎大家去體驗看看，再次偷偷置入XDD)

### 建立開局庫的方式
建立開局庫的方式主要分成兩種：
* **被動式建構**
可以利用人類高手經過長時間研究累積下來的經驗法則，比如[西洋棋開局庫](https://zh.wikipedia.org/zh-tw/%E5%9B%BD%E9%99%85%E8%B1%A1%E6%A3%8B%E5%BC%80%E5%B1%80%E5%88%97%E8%A1%A8)，或是直接蒐集大量高手棋譜，對其進行分析與統計，比如之前很有名的圍棋網站奇譜士。
* **主動式建構**
直接用搜索的方式來計算盤面，可以是Minimax、MCTS等各種方式，沒錯連Minimax都可以(當然你得搭配很多剪枝的方式)，因為這次沒有什麼時間限制，你可以將深度設得非常深，花個一星期甚至一個月去建構開局庫，比如[AlphaGo開局庫](https://alphagoteach.deepmind.com/)。

### 儲存與使用方式
儲存的資訊通常包含盤面資訊、勝率或評分、可能的下一手、搜索次數等，總之就是看你的需求決定要存下哪些資訊。
使用的話當然不可能將盤面一一做比對，如果你費時一個月建出了一個超大型開局庫，有10萬個盤面，每下一手就要去搜索這個龐大開局庫，那用時可能還比沒有開局庫來得更長......
可以跟昨天一樣使用hash，程式載入開局庫就建一個hash map，遇到一個新盤面就去查詢，還可以用樹狀結構表示，節點為盤面，邊為可能的走法，從根節點開始比對，一路沿著分支走下去，離開開局庫時稱為**脫譜(drop out of book)**。

### 其他開局庫
有時候我們不是從初始狀態開始設計開局庫的，也可能是局部的固定變化，例如圍棋定石庫(Joseki Book)，如下圖是一個19x19圍棋盤的右下角。


要考慮到鏡像對稱、旋轉、黑白(先後手)交換等16種看似不同但其實相同的盤面，以下四個角落要視為同一種定石，其實一般開局庫也需要考慮這些，只是在定石上比較明顯就是了。


### 教學開局庫
2017年12月11日[AlphaGo開局庫](https://alphagoteach.deepmind.com/)正式上線。
根據黃士傑學長臉書的資訊，這個開局庫收集了23萬個人類的棋譜，收錄了約6000個近代圍棋史上主要的開局變化，每一個開局變化都固定延伸20步棋，每個下法都經過1000萬次的模擬，整個教學工具約有2萬個分支變化、37萬個盤面。

雖然現在應該沒有人會使用這個開局庫來練習了，但在當時這絕對是變化最多最強大的圍棋開局庫，Deepmind團隊並沒有只是設計出AlphaGo把人類電爆後就結束了，而是利用他們龐大的資源創建了這個開局庫讓人類學習，感恩Deepmind讚嘆Deepmind。

## Reference
* [電腦六子棋開局庫系統之設計與研製](https://hdl.handle.net/11296/z3rr9s)
* [十九路圍棋開局庫研製](https://hdl.handle.net/11296/rq2k22)
* [以棋型分數、開局庫、平行化方法改良 MCTS 外圍開局五子棋程式](https://hdl.handle.net/11296/8axvtu)