資訊科技

電腦進軍圍棋界

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

撰文/佛蘭克(Karen A. Frenkel)
翻譯/王怡文

資訊科技

電腦進軍圍棋界

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

撰文/佛蘭克(Karen A. Frenkel)
翻譯/王怡文

圍棋攻防戰:圍棋界目前仍然由人類稱霸,但是有個新演算法已經能擊敗齊力高強的棋手。


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


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


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


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


【欲閱讀更豐富內容,請參閱科學人2007年第65期7月號】



更多相關文章

2018年12月202期睡眠學習不是夢 雜誌訂閱

本期最新文章