电脑围棋的发展概况-东华大学.PDF

電腦圍棋的發展概況 ： 周政緯 私立輔仁大學資訊工程所研究生 顏士淨國立東華大學資訊工程系副教授 摘 要 電腦對局是人工智慧領域中相當重要的一個分枝。而在圍棋方面，由於它本 身的特質，使得電腦圍棋在繼西洋棋、象棋之後，成為人工智慧中一個相當引人 注目的新挑戰。 在本篇文章當中，我們首先會介紹近 年來引起電腦圍棋界大地震的新演算 法—UCT ，其次則介紹2007 年較為活躍的圍棋程式，最後則是基於上面的敘述， 總結對於電腦圍棋的未來展望。 一、 序論 電腦圍棋自 Zobrist在 1970 年設計出第一個可與人對奕的程式以來[1]，至 今已有約三十年的歷史。由於圍棋本身的特質，使得電腦圍棋在繼西洋棋、象棋 之後，成為人工智慧中一個相當引人注目的新挑戰。 然而電腦圍棋的難點之一，便在於缺乏良好的審局函數[2] ，使其不能與西 洋棋或象棋一般，運用設計良好的審局函數、搜尋樹以及優秀的剪枝法，即可獲 得不錯的棋力；電腦圍 棋大多藉由一些經驗法則，以靜態的評估為主，而動態的 搜尋則僅用於局部的、目標明確的棋串攻殺，較少全局的搜尋。因此，人類的經 驗如何用於電腦圍棋，就成了設計的重點。 自 2003 年起，Bouzy[3]試圖打破這種情況。他運用蒙地卡羅法作為評估函 數，並且試圖運用此一評估函數，作全局性的搜尋，然而在棋力上始終沒有太大 的突破。直到 2006 年，同樣使用蒙地卡羅法的程式 Crazy Stone[4,5] ，才在杜 林舉行的第 11屆電腦奧林匹亞的九路圍棋項目中奪得金牌。雖然如此， Crazy Stone僅在 19路圍棋項目中奪得第 五名，仍未撼動以人類思維為主的圍棋程式 在 19路圍棋的地位。 然而，隨著基於蒙地卡羅的搜尋法「UCT」[16]的出現，以 UCT為基礎的圍 棋程式 MoGo[6,7,8]也逐漸在一些較非正式的比賽中展露頭角。 2007 年 6月，第 12屆電腦奧林匹亞於阿姆斯特丹舉行，上屆冠軍 GNUGO 、亞軍GO Intellect 以 及前文介紹過的 Crazy Stone 等程式均有參賽，MoGo在強敵環伺之下，以全勝 戰績奪得了 19路圍棋項目的金牌， Crazy Stone也拿到了第二名， GNUGO退居第 三。這象徵著 UCT的成功，也代表一 個嶄新的局面即將到來。 在第二章中，我們將介紹這個引起電腦圍棋界大地震的演算法「 UCT」；第三 章則針對 2007 年電腦奧林匹亞 19路圍棋項目的前三名作簡單的介紹。第四章則 9 是本文總結，並對電腦圍棋的未來作一展望。 關於電腦圍棋的規則，可參考 [13] ，電腦圍棋的歷史則見於[14] 。另，附錄 A 為 1997 年至今重要比賽的結果。 二、 UCT 2.1 蒙地卡羅法 將蒙地卡羅法應用於圍棋，最早是由 Bruegmann[9]所提出。其核心的概念， 在於透過統計許多模擬棋局的結果，進行局面的優劣判斷。亦即將蒙地卡羅法做 為一審局函數，以決定著手的好壞。 其中，所謂的「模擬棋局」，指的是對某一目標盤面，由電腦隨機落子，直 到終盤而可以判定勝負為止。Bruegmann的方法裡，在隨機落子時，除了基本的 圍棋規則外，只有一個限制：不得自填眼位，這個限制是防止棋局無法結束而設 的。模擬棋局的結果，與目前常見的只判斷黑勝或白勝不同，而是會判斷輸贏目 數，在決定著手優劣時，則是統計此著手下所有模擬棋局平均的輸贏目數來決定 的。 2.2 UCT UCT的全名是 UCB for Tree Search ，是UCB(Upper confidence Bound)[10] 在 Tree Search 上的應用。而 UCB 本來是為了解決吃角子老虎問題(Bandit Problem)而產生的。所謂的吃角子老虎問題，簡述如下：目前有若干台吃角子老 虎機，每台機器可以投錢並拉動操縱桿，此時會得到收益(reward) ，投錢、拉桿、 得到收益的過程，稱之為一個 Play 。每台吃角子老虎機有不同的收益率，倘若 玩家想要在這若干次的 Play裡獲得最大總收益，那麼玩家該怎麼作 ? 一般來說，玩家會開始動手玩，並且依照目前累積的經驗來決定下一次的 Play要選擇哪一台機器，這稱之 為開發(exploi