文／邱恆毅 資訊科學與工程研究所碩士生

講者Mr. Owen Randall來自於阿爾伯塔大學 (University of Alberta)，他在阿爾伯塔大學攻讀了碩士學位並且後來逕行修讀博士學位。目前是Martin Müller教授研究團隊當中的一員，研究領域包含強化學習(reinforcement learning)及遊戲樹(game-tree)相關的研究等。Martin Müller教授也是AlphaGo團隊的領導者David Silver的博士指導教授。

本次的演講，講者Mr. Owen Randall為我們介紹了他作為第一作者的論文: “Expected Work Search: Combining Win Rate and Proof Size Estimation”。提出這個方法的動機在於他們的研究團隊發現若是單單只靠勝率(win rate)或是證明數(proof size)來評估一個盤面可能是不夠的，這會導致一些問題。

以圍棋為例，若單單只靠勝率來評估盤面，當我們有一個非常好的盤面，各個位置的勝率都接近100%，agent便有可能會下在盤面上的任何位置上，但能夠使用最少步數取得勝利的下法可能只有少數幾個（甚至只有一個），下在其他位置上雖然最終仍然能獲得勝利，但會需要花費更多的步數，也就耗費更多的運算資源。因此，在這個層面上，他們希望可以在勝率差不多的條件下，盡可能找出可以最快獲勝的步數（也就是proof size最小的）。

另一方面，若僅僅依靠proof size來評估盤面，當我們有一個可以吃掉對手棋子的盤面時，因為我們吃掉了對手的棋子，導致我們可以下的位置變多了，因此branching factor也就隨之上升，但這樣便導致proof number search(PNS)會傾向於不對這個位子做expansion，也就導致了我們的勝率降低。因此，從這個角度來看，他們希望可以在proof size跟勝率之間取得良好的平衡，既可以不要花太多時間證明，又可以有不錯的勝率。

這篇論文提出的方法 ─ Expected Work Search(EWS)，其中最主要的貢獻在於這個方法提供了一個可以很好地在勝率與proof size中取得平衡的方法，它同時考慮了勝率與proof size的資訊去對game tree上各個node的children做排序，藉由這個排序，我們就可以選擇proof size相對小且勝率又不錯的child做expansion，以此來達到速度快、勝率高的目的，他們的方法相較於傳統的go-solver加速了6倍以上的速度，這證明了此方法的可行性。此研究已撰寫成論文，並獲得IJCAI頂尖會議接受。

最後，在演講結束後，聽眾與講者一同共進午餐，我們非常感激可以有這樣難得的機會可以和來自世界一流大學的講者進行學術上的交流，這是一個令人難忘的經驗。