子計畫四：雙層疊工作層級運算系統應用於外圍開局五子棋及相關程式之研發

雙層疊工作層級運算系統(Two-Tier JLCS)的發展已日趨穩定，且AlphaZero的方法極有潛力，於是本子計畫在執行期間致力改良AlphaZero的演算法，並將AlphaZero的方法套用到外圍開局五子棋(Outer-Open Gomoku)及其他電腦對局程式上，包含中國跳棋(Chinese Checkers)、突圍棋(Breakthrough)、八路黑白棋(Othello 8x8)、十路黑白棋(Othello 10x10)、5五將棋(Minishogi)等項目。本子計畫去年有兩篇論文已被CG2018 (The 10th International Conference on Computers and Games)研討會接受，一篇是以連線型遊戲(井字遊戲及外圍開局五子棋)為實驗對象，我們針對連線型遊戲的特性，以限制搜尋範圍及考慮搜尋深度的獎勵，以減少搜尋廣度與深度的方式來設計，已獲得不錯的成效，我們繼續努力補充實驗數據。在期中報告也增加介紹另一篇CG2018論文所使用的殘局庫設計方法。本期末結案報告則再增加中國跳棋的介紹作為成果的呈現。另外我們也發表各棋類改良技術論文，發表在國內外期刊及研討會。 中國跳棋遊戲是家喻戶曉的棋盤遊戲，但針對提升電腦對局棋力的研究並不多，過去以蒙地卡羅樹搜尋法來設計的雙人中國跳棋AI已經能表現出一定的棋力，但還是有改進的空間。中國跳棋除了要使棋子能夠快速前進外，也要在適當的時機後退，取得攻防之間的平衡。本研究基於蒙地卡羅樹搜尋法探討雙人中國跳棋的改良方案，並加入自我強化學習的做法，採用AlphaZero的方法來訓練神經網路。為了在有限的硬體資源及時間條件下取得訓練成效，於是本研究針對中國跳棋的特性加入一些人為知識，並預先產生棋譜作為自我強化學習的訓練資料，最後透過走步修正的想法使訓練更精準，經實驗證實本計畫提出的方案能在短時間內訓練出具有相當棋力的中國跳棋程式。 另外本子計畫亦致力於發展其他電腦對局程式，如象棋(Chinese Chess)、愛因斯坦棋(EinStein Wurfelt Nicht)、麻將(Mahjong)、數織(Nonogram)、蘇拉卡爾塔棋(Surakarta)等。這兩年間共參與五次國際性電腦對局競賽(TAAI 2017, ICGA 2018, TAAI 2018, TCGA 2019, ICGA 2019)，在這五次競賽中，本子計畫的研究群累計獲得22個金牌、18個銀牌、10個銅牌，還在TAAI 2017電腦對局競賽獲得團體總錦標第二名的榮譽。 在論文發表方面，本子計畫在計畫執行期間已發表了4篇SCIE期刊論文、3篇EI國際研討會論文、及4篇國內研討會論文。目前還有2篇EI國際研討會論文及1篇國內研討會已被接受，另外有1篇SCIE期刊論文正在審查中。綜合上述各點，本子計畫已達成預期的進度及目標。