|
||||
撰文/卡倫·A·弗蘭克爾(Karlen A Frankel)
12年前,IBM公司研制的超級計算機『深藍』(Deep Blue)在6局比賽中擊敗了國際象棋世界冠軍加裡·卡斯帕羅夫(Garry Kasparov)。這個裡程碑式的事件終結了人類在又一個智力策略游戲上的統治地位。只有亞洲的圍棋仿佛是計算機科學的『阿喀琉斯之踵』:人類總是能夠輕松擊敗計算機。但最近出現的一種新的圍棋算法,卻能戰勝高水平的棋手。
圍棋的復雜度高,且極具欺騙性,對計算機程序提出了巨大的挑戰。圍棋的棋盤由兩組數量相同、互相正交的平行線構成,分為9線小棋盤與19線大棋盤兩種。對弈雙方分執黑白兩色棋子。通過在棋盤的交叉點上落子,棋手要盡可能擴張自己的領地並包圍對方棋子。在大棋盤的對弈中,每一步可采取的策略數量都非常巨大。對局中期,平均每一步能采取200種不同的策略,相比而言,國際象棋中每一步數十種的可選策略就顯得微不足道了。此外,還要考慮數量眾多的後續策略。由於棋盤上每個位置都對應著三種狀態:黑子佔據、白子佔據和空位,N個位置便可構成3N種不同的狀態。如果考慮規則約束,小棋盤大約有1038種不同的狀態,大棋盤的狀態數量則達到了驚人的10170種。其他一些因素也會影響比賽勝負:棋盤上棋子的數量優勢並不能確保勝利,棋手必須在考慮局部形式的同時,兼顧全局。
為了處理如此眾多的可能情況,人工智能專家已經設計出一些算法,來限制搜索的范圍,但它們都無法在大棋盤的比賽中戰勝實力稍強的人類棋手。去年秋季,兩位匈牙利研究人員報告了一種新算法,它的勝率比現有最佳算法提高了5%,能夠在小棋盤的比賽中與人類職業棋手抗衡。這種被稱為UCT(Upper Confidence bounds applied to Trees)的算法,是匈牙利國家科學院計算機與自動化研究所(位於布達佩斯)的列文特·科奇什(Levente Kocsis)與加拿大阿爾伯塔大學(University of Alberta,位於埃德蒙頓)的喬鮑·塞派什瓦裡(Csaba Szepesv?ri)合作提出的,是著名的蒙特卡羅方法(Monte Carlo method)的擴展應用。
20世紀70年代,蒙特卡羅方法首次運用於圍棋程序,這種方法的作用類似於選舉投票:用統計采樣的方式,預測大規模群體的表現與特質。圍棋程序會隨機出招,模擬大量的比賽,對候選走法加以評估並排序。然而,每一步都采用評估值最高的走法,並不能保證獲得比賽的勝利。相反,這種方法僅僅是限制了搜索的范圍。
UCT擴展了蒙特卡羅方法,集中關注那些最有希望贏得比賽的走法。科奇什說:『UCT的主要思想是對走法進行選擇性采樣。』他解釋說,這種算法必須達到一種平衡,既要嘗試當前的最佳走法,發現其中可能隱藏的昏招,還要搜索『當前並非最佳的走法,以確保不會因為先前的估計錯誤而錯失妙招』。
UCT為每一種走法計算一個索引值,然後按照索引值最高的走法出招。索引值由采用該走法後最終取勝的概率(即勝率)決定,該走法被計算卻未被采用的次數也對索引值有一定的影響。UCT會在內存中維護一棵『決策樹』,用來記錄每一種走法的統計數據。如果遇到一種先前從未計算過的走法,算法就會將它納入決策樹,並隨機出招完成餘下的比賽。
判定隨機比賽的勝負後,UCT就會更新比賽中采用過的所有走法的統計數據。如果該走法的索引值等於它的勝率,算法就能快速選定這招最有希望獲勝的策略。但開局時走出妙招,仍然無法確保比賽的最終勝利。所以在選擇走法時,UCT會增大計算次數少的候選走法的權值,以使勝率的總體分布趨向平坦。
法國南巴黎大學的數學家西爾萬·熱利(Sylvain Gelly)與巴黎技術學校的王毅早(Yizao Wang,音譯)將UCT集成到一個他們稱之為MoGo的程序中。該程序的勝率竟然比先前最先進的蒙特卡羅擴展算法幾乎高出了一倍。今年春季,MoGo在小棋盤的比賽中擊敗了實力強勁的業餘棋手,在大棋盤比賽中也擊敗了實力稍弱的業餘棋手,充分展示了能力。熱利認為UCT易於實現,並有進一步完善的空間。科奇什預言,10年以後,計算機就能攻克最後的壁壘,終結人類職業棋手對圍棋的統治。
(譯/陳家乾 校/虞駿)
請您文明上網、理性發言並遵守相關規定,在註冊後發表評論。 | ||||