計算機人工智能論文(2)
計算機人工智能論文篇二
計算機博弈與人工智能
計算機博弈,歷來是人工智能的一個重要的研究領域,早期人工智能的研究實踐,正是從計算機下棋開始。因為人類開發(fā)下棋軟件,目的是讓計算機模仿人腦進行思維,如果能夠掌握下棋的本質,也許就掌握了人類智能行為的核心,那些能夠存在于下棋活動中的重大原則,或許就存在于其它任何需要人類智能的活動中。所以說,下棋軟件某種意義上可以代表人工智能的發(fā)展程度。
從上世紀六十年代的“跳棋機”到1997年的“深藍”,計算機下棋程序在人機對弈中取得了一個又一個勝利,但是這些程序雖然屬于人工智能范疇,實際上它們并沒有多少“智”的成分,主要部分都是在可行范圍內搜索。各種研究也大都是怎樣使搜索更快更有效。它們缺乏“智”的成分的根本原因,是我們自己并不清楚人類是以怎樣的形式思考的。比如你寫一個名字問一名教師,這人是不是他班上的學生。教師馬上就可以回答是或不是。如果你問計算機,計算機也可以馬上正確地回答是或不是。但計算機的方式是把這個名字與學生名單里所有名字一一比較以后得出的答案。計算機搜索很快,全走一遍幾乎可以瞬間完成。但我們知道教師是不可能在短時間內把班上所有學生的名單過一遍的。類似的,我們看到一個人的照片,馬上就知道我們以前見沒見過這個人,我們不可能在短時間內把我們以前見過的人都檢查一遍,那么我們是怎樣得出結論的呢?現在我們對此還不是完全清楚。
下棋的時候棋盤上可走的地方很多,但下棋的人并不是每種走法都去考慮。那么哪些位置需要考慮,哪些位置不需要考慮,這就是“模式識別”問題。人腦有“模式識別”功能,可以很快得出一個大致的結論,計算機沒有這種功能,只好所有的位置都考慮。在人機博弈中,計算機人工智能的基本思考方法是窮舉法,即通過對所有可能的招法的演化結果進行比較,最后選擇出一個最好的招法。例如在象棋的某個“局面”中,如果有38種合乎規(guī)則的棋子走法,無論選擇其中哪一種,都會再生成一個新局面。將所有這些變化列起來,就會形成一棵“博弈樹”,計算機要做的,就是比較最后一層結果,選擇其中一個最好的,然后逆推,找到本局面下最好的一個走法,計算機的這種思考能力在中局搏殺階段表現得尤為明顯。另外,在人機對弈中,計算機面對每一步棋時,都將會模仿人的思考方法盡可能地簡化搜索范圍,然后對其進行橫向比較并選擇最優(yōu)走法。但是,國際象棋的變化總數達到10的123次方,而中國象棋的變化數量比這還要多得多,可達10的144次方以上,圍棋的變化就更多,達10的172次方以上,計算機不可能算出棋盤上的所有變化。因此,所謂的“利用窮舉法選擇最好的走法”,指的是棋局的局部,并且是在有限的步驟里,而不是通盤窮舉,它更沒法對整盤棋的形勢做正確判斷。這就是它中盤計算超強而大局觀差的原因。半個世紀以前人們就開始研究國際象棋程序,但因計算機性能問題,在人機對弈中計算機始終表現不佳,因為大空間搜索不可行,就只能用人們設計的判別模式進行選擇性地搜索(模仿人的思維)。選擇不見得對,搜索又不徹底,結果當然不會好到哪里去。好在計算機的性能發(fā)展得很快,到了1997年,IBM的深藍用“硬搜索”打敗了人類國際象棋世界冠軍卡斯帕羅夫。當然深藍還請了一些國際象棋專家指點判別程序,但主要靠的還是硬搜索。
目前,在三大棋類項目中,國際象棋和中國象棋兩項,計算機的水平都已經可以跟最頂級的職業(yè)棋手抗衡了,但在圍棋項目中計算機的水平卻始終上不去,目前圍棋計算機大賽獲得冠軍的軟件也只勉強達到業(yè)余初段水平,和頂級職業(yè)棋手相比,大概要被讓七子。
為什么計算機圍棋的水平和象棋比差這么多呢?除了資金等投入上有差距外,大致還有以下幾個原因:
(1)國際象棋盤60格,中國象棋90個交叉點,而圍棋則有361個交叉點。象棋一局棋一般三四十個回合七八十步棋,而圍棋一盤棋一般要一百多手棋,最多的會超過三百手棋,這使圍棋的計算量遠遠超過象棋,因此對計算機的性能提出了更高的要求,但按照傳統的解決問題的思路,目前計算機還不能滿足這種要求。
(2)中國象棋和國際象棋的目的比較明確,就是保存子力,保衛(wèi)老將(王)。而圍棋以占地多少決定勝負,厚勢與薄味、要子和廢子、模樣和實地,這些都是判斷上的問題,很難在程序中做出界定。
(3)在象棋中,計算占的比重很大,象棋中每個棋子的價值都是可以量化的,例如國際象棋中后相當于三個馬或九個兵,在棋局的不同階段或子力優(yōu)勢時再加上不同的權值,因此計算機可以用準確無誤的計算來彌補它判斷上的不足。但圍棋的計算只是圍棋的一部分,尤其是序盤階段,對全局形勢的分析與判斷才是重點,由于在棋局進程中,隨著周圍的棋子布置不同,原有棋子的價值在不斷地發(fā)生變化,如何判斷取舍,這一方面正是計算機的弱點,也無法通過計算來彌補。
計算機圍棋的難點之一,是缺乏好的估值函數,使計算機圍棋不能如象棋一樣,運用好的估值函數、搜尋樹及-剪枝法,即可獲得不錯的棋力,計算機圍棋大多依靠一些經驗法則,以靜態(tài)的評估為主,而動態(tài)的搜索則僅用于局部的、目標明確的棋串攻殺,全局的搜索較少。因此,人類的經驗如何用于計算機圍棋,就成了設計的重點。
圍棋中一般認為達到業(yè)余初段水平才算入門,多年來計算機圍棋的水平一直在門外徘徊,直到目前的最新技術,以蒙特卡羅方法為基礎的UCT算法出現以后,計算機圍棋終于達到了業(yè)余初段水平,而且從發(fā)展?jié)摿砜催€有很大提升空間。
蒙特卡羅是位于摩納哥的賭城,蒙特卡羅方法(Monte Carlo,縮寫為MC)的名稱象征性地表明該方法的概率統計的特點,它是把所求解的問題同一定的概率模型相聯系,用計算機實現統計模擬或抽樣,以獲得問題的近似解。MC怎樣用于圍棋呢?針對某局面下的某一手棋,由計算機模擬后續(xù)對局,得到這手棋的獲勝概率,把所有可能下法的獲勝概率都算出來后,選擇獲勝概率最大的下法。MC直接用在圍棋上的缺點十分突出,首先是浪費了模擬次數,因為在有限的時間內只能模擬出一定的棋局數。其次,它沒有考慮對方的下一手,如果我們把MC當作估值函數,那么對比傳統的人機博弈程序,簡單的MC相當于只搜索了一步。如果估值無比精準的話,那么這一步足矣。實際上圍棋還不存在這么精確的估值,以MC的估值速度,往深算幾步,耗費的時間無法接受。所以人們對算法進行了改進,首先是根據棋形和基本著法進行智能判定,只對合理的著法作模擬,對明顯不合理的招法予以舍棄,其次,對難以判定優(yōu)劣的多種可選方案,用AMAF算法進行隨機選擇。
以蒙特卡羅方法為基礎的UCT算法,是目前計算機圍棋在計算手筋和局部戰(zhàn)斗上的最好的算法,在9€?的小棋盤上有過戰(zhàn)勝職業(yè)棋手的記錄,但它也有自己的局限,如果沒有新的算法上的突破,很難跳出業(yè)余的段位,和職業(yè)棋手進行對抗。假如將來有一天,計算機圍棋程序戰(zhàn)勝了頂級職業(yè)棋手,是否說明計算機已經具有智能了呢?我們仍然不能得出這個結論。
計算機人工智能論文相關文章：
計算機人工智能論文(2)
