電腦進軍圍棋界

電腦進軍圍棋界
撰文╱Karen A. Frenkel｜譯者╱王怡文
轉載自《科學人》2007年7月第65期

新的圍棋演算法現身，目標是戰勝人腦！

10年前，IBM的西洋棋程式「深藍」（Deep Blue）在一場六回合比賽中，打敗了世界冠軍卡斯帕洛夫（Garry Kasparov），這個事件建立了一個里程碑，迫使人類再度讓出另一種策略遊戲的主宰權。唯獨亞洲的圍棋，看來可能是計算機科學的罩門，能讓人類狠狠擊敗電腦。不過，現在出現了一種新的演算法，它能與棋力高強的人類棋手匹敵，而且獲勝。

對電腦程式設計師而言，圍棋已證實是項艱鉅的挑戰，因為這個遊戲的複雜度高深莫測。這種棋戲是在九乘九或十九乘十九格線的交叉點上，放置黑棋與白棋，以佔領地域並且包圍對手為目標。特別是在大棋盤上，每一手的可能棋步都非常多，對弈當中平均每手可能的位置有200種，相較之下西洋棋只有數十種。而且圍棋的分支因數（支化係數）相當可觀，對於棋盤上有ñ個位置的狀況來說，可能的盤面有3^N種 因為每個位置有黑棋，白棋或空點等三種可能性。小棋盤的合理盤面約有10 ³⁸種，大棋盤則大約有10 ¹⁷⁰種。此外並非盤面上棋子較多就必定獲勝，棋手必須兼顧局部與整體盤勢。

為了對付為數如此繁浩的選擇，人工智慧專家設計了演算法來限制搜尋次數，但那些程式都未能在大棋盤上擊敗棋力較強的人類。2006年年秋天，有兩位匈牙利研究人員發表了一種演算法，勝率高出當時最佳圍棋程式大約5％，而且能夠在小棋盤上匹敵職業棋士，他們是匈牙利科學院計算與自動化研究所（位於布達佩斯）的柯西斯（Levente Kocsis），以及現任教於加拿大亞伯達大學（位於艾德蒙頓市）的季佩斯伐利（CsabaSzepesvári）。他們所發展出的這種演算法，名為「樹狀結構信賴上界法」（UCT），是從著名的蒙地卡羅法擴充而來。

蒙地卡羅法首次應用於圍棋程式是在1970年年代，這個演算法的原理有點像政治民調：進行統計採樣以預測更廣大群眾的行為或特性這個演算法在下圍棋時，會在背後試玩大量的隨機棋局來為候選棋步打分數，然後將棋步排名。然而，在每一種盤面中採用分數最高的棋步，並不保證能夠贏得棋局。相反的，這樣只是限制了可能棋步的數量。

UCT運用蒙地卡羅的方式又更進一步，它鎖定最可能獲勝的棋步，進行搜尋，柯西斯表示：「主要概念在於棋步的採樣有選擇性。」他解釋說，這個演算法必須取得一個平衡，既要試用當時看來最佳的選擇，以找出可能的弱點，又要探索「看起來比較不完美的選擇，以確保不會因為先前的估算錯誤而遺漏掉好的選擇」。

UCT計算出棋步的索引值，並且選擇索引值最高的棋步。這個演算法利用勝率（代表該盤面發展成勝的頻率）以及該盤面已考慮過但尚未採用的次數，來計算索引值。UCT在記憶體中建造一棵決策樹，利用它追踪這些統計數字。當UCT遇上之前未考慮過的一個棋步，就將棋步加入決策樹中，然後隨機下完剩餘的棋局。

接著，UCT判斷隨機棋局終局的輸贏，然後更新棋局中所下過全部棋步的統計數字。如果索引值等於該棋步的勝率，演算法很快就能鎖定最可能致勝的路徑；然而最初的成功路徑，並非最後產生致勝棋步的保證，所以在選擇棋步時，UCT會將贏率加權計分，較少被考慮到了候選棋步權值較高。這個點子是從吃角子老虎問題（bandit problem）借來的─賭徒玩數台吃角子老虎而不知道它們的平均報酬率時，選擇性地加權計分，能產生最大的利益。

南巴黎大學的傑利（Sylvain Gelly）和巴黎近郊法國綜合理工學院的王一早（Yizao Wang）兩位數學家，已經將UCT整合進一個個他們命名為魔圍棋（MoGo）的程式，它跟之前最先進的蒙地卡羅擴充演算法相比，勝率高出95％，目前魔圍棋已經是最頂尖的圍棋演算法，它在今年春天展現實力，在九乘九棋盤上贏了棋力高強的業餘棋手，在大棋盤上也擊敗了棋力較弱的棋手。傑利說，UCT程式寫起來簡單，而且還能再改善。因此柯西斯說，最後一道防線被攻陷，終結圍棋界由人類職業棋士稱霸的時代，也許10年內就會發生。

(本文由教育部補助「AI報報─AI科普推廣計畫」取得網路轉載授權)