【程式應用】教自己下棋的電腦程式

■英國的一位研究生開發出了一套下西洋棋的程式。特別的是,這套程式會教自己下棋,而且學得又快又厲害。學了72小時之後,實力大約相當於國際西洋棋大師(International master)的水準。

CC0 Public Domain
CC0 Public Domain

撰文|陳勁豪

對人工智慧領域而言,讓電腦下西洋棋一直是個有趣的題目。以西洋棋而言,棋盤由八乘八共六十四個格子所組成,黑白雙方各有十六個棋子,依照特定的規則輪流下棋。規則簡單卻有接近無窮的發展性。因此如何讓電腦在近乎無限的可能性中挑出最好的下一步,基本上就是個相當大的挑戰。

但對電腦來說,最大的特性就是計算速度快,所以電腦可以利用這個特點,以硬算的方法直接窮舉出之後所有可能的棋步,然後在這些所有的可能性中找出最好的一步。

1996年,IBM推出了「深藍計畫」來挑戰當時的西洋棋棋王卡斯巴洛夫(Garry Kasparov)。初次挑戰,棋王以4-2打敗深藍。在1997年的時候,深藍捲土重來,以每秒鐘計算兩億步,可以估計隨後的12步棋的計算能力,以3.5-2.5打敗了卡司巴洛夫,成為第一個在標準比賽中擊敗世界西洋棋冠軍的電腦系統。

直到現在,電腦西洋棋程式的實力大幅提昇,但是在下棋的技術方面卻沒有顯著提昇,基本上都還是走硬算路線。即便是擁有超強計算能力的深藍,大概也只是跟計算能力幾乎無法相提並論的人類棋王打成平手而已,這顯示西洋棋計算棋步的方式還有很大的改進空間。因為對人類棋手來說,他們不會去考慮一些幾乎不可能的情況,他們只要從最可能的幾個棋子下手開始計算就可以,所以可以大幅簡化計算的複雜度。

倫敦Imperial College London的研究生Matthew Lai開發了一套叫做Giraffe的程式,來挑戰這個問題。簡單的說,他利用神經網路算法(neural network)來讓電腦程式自己訓練自己,或是說,自己教自己下棋。神經網路演算法就像是人類學習下棋一樣,透過學習各種範例,整理出哪些是可行,哪些是不可行的棋步。或是在各種可行的棋步中挑出最有效果的棋步。為了訓練他的程式,Lai準備了一億七千萬個範例來教他的Giraffe,之後還讓他的程式跟自己對戰以吸取經驗。

最後Lai利用Strategic Test Suite這個資料庫來評估Giraffe的實力。測試的滿分是15000分,Giraffe展現了相當好的學習能力,很快的就拿到了6000分,然後在72小時之後,成績提昇到了9700分左右。這表示這個程式的確有經過學習而逐漸進步。Lai表示他的程式有46%的機會可以找到最好的棋步,大約有70%的機會會把最好的棋步選進三個最可能的下一步中。

Giraffe下棋的能力大概都可以達到國際西洋棋大師(International master)的水準,也就是在世界棋手排名的前2.2%,或是可以勝過97.8%的選手。但是跟一般的下棋程式相比,運用神經演算法的Giraffe需要用上相當於十倍棋力的程式的計算時間。

當記者問到Lai的下一個目標,他表示想把這個程式的棋力提升到特級大師(grandmaster)的水準,之後甚至是挑戰其他棋類。

原始論文
Giraffe: Using Deep Reinforcement Learning to Play Chess
arxiv.org/abs/1509.01549

參考資料
1. MIT Technology Review 2015/09/14: Deep Learning Machine Teaches Itself Chess in 72 Hours, Plays at International Master Level
2. Popular Science 2015/09/16 Artificial Intelligence Is Taking Computer Chess Beyond Brute Force
3. Popular Mechanics 2015/09/15 This Chess Engine Learns How to Beat Humans by Playing Against Itself

--
作者:陳勁豪 科教中心特約寫手,從事科普文章寫作。2011年於美國紐約州立石溪大學(SUNY at Stony Brook)取得博士學位,研究主題為相對論性重離子碰撞(Relativistic Heavy Ion Collision)。長期擔任中文科學新聞網站「科景」(Sciscape.org)總編輯。

 

加入好友

人瀏覽過

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

為了避免你是機器人,請在留言前回答以下問題: