【文章內(nèi)容簡介】 玩家 2輸 玩家 1輸 玩家 2輸 31 Alphabeta剪枝算法 ? Alphabeta剪枝算法是一個簡單的算法，它通過去掉明顯不好的結(jié)點達到極小化博弈樹搜索的目的。 32 33 AI歷史回顧 (5) ? 一個笑話（英俄翻譯） ? The spirit is willing， but the flesh is weak ? 心有余而力不足 ? The vodka is good， but the meat is rotten ? 伏特加酒很不錯，但肉已腐敗 34 AI歷史回顧 (6) ? 出錯的原因 ? spirit 1)精神 2)烈酒 ? 結(jié)論 ? 必須理解才能翻譯，而理解需要知識 35 AI歷史回顧 (7) ? 第三階段（ 60年代中－ 80年代初）知識工程時代 ? 專家系統(tǒng) ? 知識工程 ? 知識工程席卷全球 ? 各國發(fā)展計劃：美國星球大戰(zhàn)計劃、英國 ALVEY計劃、法國 UNIKA計劃、日本五代機計劃、中國863計劃 36 費根鮑姆 （ ） ? 專家系統(tǒng)和知識工程之父 ? 1968年研究出第一個專家系統(tǒng)： DENDRAL，用于質(zhì)譜儀分析有機化合物的分子結(jié)構(gòu) ? 1977年，提出知識工程（ knowledge Engineer)概念 ? “知識就是力量，電子計算機則是這種力量的放大器，而能把人類知識予以放大的機器，也會把一切方面的力量予以放大?！? 37 ? 1965年 Feigenbaum的世界上第一個專家系統(tǒng) 根據(jù)分子式和質(zhì)譜數(shù)據(jù)輔助推斷分子結(jié)構(gòu) . ? 1974年紹特里夫 (Shortliffe)等人開發(fā)的 MYCIN專家系統(tǒng) .用診斷和治療感染性疾病 . ? 1968年 Quilian提出語義網(wǎng)絡知識表示法 ? 1974年 Minsky提出框架 (Frame)理論 ? 1965年 Robinson提出歸結(jié)原理 ? 1972年科麥瑞爾 (Colmerauer)實現(xiàn)第一個 Prolog (PROgramming in LOGic)系統(tǒng) ? 1977年在第五屆 IJCAI上 ,Feigenhaum在“人工智能的藝術(shù) :知識工程及實例研究”中提出“知識工程”的概念 . 38 ? 1982年 1991年日本研制第五代計算機計劃(投資 ) ? 1983年起 (610計劃 )美國研制能看 ,聽 ,說和思考的新一代計算機 (投資 6億多美元 ) ? 1982年 10月英國開始研制第五代計算機 ,5年內(nèi)投資 39 AI歷史回顧 (8) ? 遇到的困難 ? 知識獲取的瓶頸問題 40 AI歷史回顧 (9) ? 第四階段（ 80年代中－ 90年代初）新的神經(jīng)元網(wǎng)絡時代 ? BP算法，解決了多層網(wǎng)的學習問題 ? Hopfield網(wǎng)絡，成功求解了旅行商問題 ? 存在問題： ? 理論依據(jù) ? 解決大規(guī)模問題的能力 41 AI歷史回顧 (10) ? 第五階段（ 90年代初－現(xiàn)在）數(shù)據(jù)與網(wǎng)絡時代 ? 網(wǎng)絡給 AI帶來無限的機會 ? 知識發(fā)現(xiàn)與數(shù)據(jù)挖掘 ? AI走向?qū)嵱没? 42 Research Fields of AI ? 粒度計算 ? 群體智能 43 Problem Resolving ? 問題： ? 博弈問題（ Game Playing）：國際象棋、方盤棋、五子棋、打牌、戰(zhàn)爭等 ? 漢諾塔游戲（ Hanoi Game） ? 人、狼、羊和菜的過河問題 ? 求解微分方程等 ? 涉及的主要技術(shù)： ? 問題表示、問題分解、問題空間搜索、 問題歸約 44 游戲中的代表性成就 ? IBM的 Deep Blue國際象棋程序： 1997年 5月 11日， Deep Blue以 : Garry Kasparov ? 加拿大 Alberta大學研制的西洋跳棋程序 Chinook是第一個在世界錦標賽中戰(zhàn)勝人的程序。（跳棋一共有 5萬億億種走法（ 5 * 10^20）， Chinook則只使用了其中的 100萬億種 (10^14)） ? 黑白棋的智能程序 Logistello在 1997年以 6比 0的比分戰(zhàn)勝了世界冠軍 Takeshi Murakami。 ? 圍棋與西洋雙陸棋 45 視頻游戲 46 視頻游戲（ 2） 47 視頻游戲（ 3） 48 視頻游戲（ 4） 49 Automatic Theorem Proving ? 自動定理證明：讓計算機模擬人類證明定理的方法，自動實現(xiàn)象人類證明定理那樣的非數(shù)值符號的演算過程。是 AI中最早且重要的研究領域之一 ,對 AI的發(fā)展起過重大作用 .許多非數(shù)學問題可轉(zhuǎn)化為自動定理證明來求解 . ? 主要方法 : ? 自然演繹法 : 依據(jù)推理規(guī)則 ,從前提或目標出發(fā) ,并利用公理來證明定理的方法 . ? 判定法 : 對一類問題找出統(tǒng)一的計算機上可實現(xiàn)的算解 .1978年我國數(shù)學家吳文俊教授提出平面幾何和微分幾何定理的機器證明方法 .被認為是當時最好的一種方法 (吳氏方法 ) ? 定理證明器 : 研究一切可判定問題的證明方法 .1964年 Robinson提出歸結(jié)原理 . ? 計算機輔助證明 : “四色定理” . 50 ? 自動定理證明就是機器定理證明 ， 這也是人工智能的一個重要的研究領域 ， 也是最早的研究領域之一 。 定理證明是最典型的邏輯推理問題之一 ， 它在發(fā)展人工智能方法上起過重大作用 。 1976年 7月，美國的阿佩爾 ()等人合作解決了長達 124年之久的難題 四色定理。他們用三臺大型計算機，花去1200小時 CPU時間，并對中間結(jié)果進行人為反復修改 500多處。四色定理的成功證明曾轟動計算機界。 四色定理證明 51 四色定理 ? 地圖四色定理 (Four color theorem)最先是由一位叫古德里（ Francis Guthrie）的英國大學生提出來的。德 摩爾根（ Augustus De Man， 1806～ 1871）1852年 10月 23日致哈密頓的一封信提供了有關四色定理來源的最原始的記載。 四色問題 又稱 四色猜想 ，是世界近代三大數(shù)學難題之一。 ? 四色問題的內(nèi)容是：“任何一張 地圖 只用四種顏色就能使具有共同邊界的國家著上不同的顏色?！庇脭?shù)學語言表示，即“將平面任意地細分為不相重迭的區(qū)域，每一個區(qū)域總可以用 1， 2， 3， 4這四個數(shù)字之一來標記，而不會使相鄰的兩個區(qū)域得到相同的數(shù)字。