?●○?●○?●○?●○●?○●?○●?○●?○2.3博弈樹搜索20世紀60年代，研制出的西洋跳棋和國際象棋的博弈程序達到了大師級的水平。1958約翰?麥卡錫提出博弈樹搜索算法1997年，IBM公司研制的“深藍”國際象棋程序，采用博弈樹搜索算法，該程序戰勝了國際象棋世界冠軍卡斯帕羅夫。1.概述正在與深藍下棋的卡斯帕羅夫博弈問題特點：雙人對弈，輪流走步。信息完備，雙方所得到的信息是一樣的。零和，即對一方有利的棋，對另一方肯定是不利的，不存在對雙方均有利或無利的棋。1.概述博弈的特性兩個棋手交替地走棋；比賽的最終結果，是贏、輸和平局中的一種；可用圖搜索技術進行，但效率很低；博弈的過程，是尋找置對手于必敗態的過程；雙方都無法干預對方的選擇。1.概述2.Grundy博弈下棋的雙方是對立的，命名博弈的雙方，一方為“正方”，這類節點稱為“MAX”節點；另一方為“反方”，這類節點稱為“MIN”節點。正方和反方是交替走步的，因此MAX節點和MIN節點會交替出現。2.Grundy博弈Grundy博弈是一個分錢幣的游戲。有一堆數目為N的錢幣，由兩位選手輪流進行分堆，要求每個選手每次只把其中某一堆分成數目不等的兩小堆。例如，選手甲把N分成兩堆后，輪到選手乙就可以挑其中一堆來分，如此進行下去，直到有一位選手先無法把錢幣再分成不相等的兩堆時就得認輸。2.Grundy博弈設初始狀態為(7，MIN)，建立問題的狀態空間圖，圖中所有終結點均表示該選手必輸的情況，取勝方的目標是設法使棋局發展為結束在對方走步時的終結點上。MIN先走MAX必勝2.Grundy博弈結點A是MAX的搜索目標，而結點B，C則為MIN的搜索目標。2.Grundy博弈搜索策略要考慮的問題是：對MIN走步后的每一個MAX結點，必須證明MAX對MIN可能走的每一個棋局對弈后能獲勝，即MAX必須考慮應付MIN的所有招法，這是一個與的含意，因此含有MAX符號的結點可看成與結點。

2.Grundy博弈對MAX走步后的每一個MIN結點，只須證明MAX有一步能走贏就可以，即MAX只要考慮能走出一步棋使MIN無法招架就成，因此含有MIN符號的結點可看成或結點。2.Grundy博弈對弈過程的搜索圖呈現出與或圖表示的形式。實現一種取勝的策略就是搜索一個解圖的問題，解圖就代表一種完整的博弈策略。2.Grundy博弈中國象棋一盤棋平均走50步，總狀態數約為10的161次方。假設1毫微秒走一步，約需10的145次方年。結論：不可能窮舉。3.極小極大搜索過程對各個局面進行評估評估的目的：對后面的狀態提前進行考慮，并且以各種狀態的評估值為基礎作出最好的走棋選擇。評估的方法：用評價函數對棋局進行評估。贏的評估值設為+∞，輸的評估值設為-∞，平局的評估值設為0。評估的標準：由于下棋的雙方是對立的，只能選擇其中一方為評估的標準方。3.極小極大搜索過程MAX節點和MIN節點命名博弈的雙方，一方為“正方”，對每個狀態的評估都是對應于該方的輸贏的。例如，贏2個，輸1個等，都是指正方的。正方每走一步，都在選擇使自己贏得更多的節點，因此這類節點稱為“MAX”節點；3.極小極大搜索過程另一方為“反方”，對每個狀態的評估都是對應于對手的輸贏的。例如，贏2個，輸一個，其實是指自己輸2個，贏1個的。反方每走一步，都在選擇使對手輸得更多的節點，因此這類節點稱為“MIN”節點。3.極小極大搜索過程由于正方和反方是交替走步的，因此MAX節點和MIN節點會交替出現。3.極小極大搜索過程正方（MAX節點）從所有子節點中，選取具有最大評估值的節點。反方（MIN節點）從其所有子節點中，選取具有最小評估值的節點。反復進行這種選取，就可以得到雙方各個節點的評估值。這種確定棋步的方法，稱為極小極大搜索法。

3.極小極大搜索過程3.極小極大搜索過程5-333-3022-30-23541-30689-3MINMAX0MAXMIN3.極小極大搜索過程015-333-3022-30-23541-30689-30-33-3-3-21-36-3031601MAXMINMAXMIN3.極小極大搜索過程

在九宮格棋盤上，兩位選手輪流在棋盤上擺各自的棋子(每次一枚)，誰先取得三線的結果就取勝。設程序方MAX的棋子用(×)表示，MAX先走。對手MIN的棋子用(o)表示。例如：3.極小極大搜索過程MIN取勝

估計函數f(p)=(所有空格都放上MAX的棋子之后，MAX的三子成線數)－(所有空格都放上MIN的棋子之后，MIN的三子成線的總數)

若P是MAX獲勝的格局，則f(p)=+∞；若P是MIN獲勝的格局，則f(p)＝-∞。3.極小極大搜索過程3.極小極大搜索過程估計函數值f(p)=6-4=2估計函數f(p)=(所有空格都放上MAX的棋子之后，MAX的三子成線(行、列、對角)數)－(所有空格都放上MIN的棋子之后，MIN的三子成線(行、列、對角)的總數)當前棋局f(p)=23.極小極大搜索過程一字棋第一階段搜索樹3.極小極大搜索過程一字棋第二階段搜索樹3.極小極大搜索過程一字棋第三階段搜索樹

設有一個擺放三個子的棋盤殘局，如下圖所示，〇和╳在結束前有三步棋可以走，而且設走第一步的是╳。這時存在著三個空格A，B，C，用博弈樹搜索算法判斷應該把棋子放到哪一格內。

AB╳╳╳〇〇C〇棋盤殘局舉例：3.極小極大搜索過程AB╳╳╳〇〇C〇╳B╳╳╳〇〇C〇╳〇╳╳╳〇〇C〇╳B╳╳╳〇〇〇〇0A╳╳╳╳〇〇C〇〇╳╳╳╳〇〇C〇A╳╳╳╳〇〇〇〇AB╳╳╳〇〇╳〇〇B╳╳╳〇〇╳〇A〇╳╳╳〇〇╳〇-1-0-10--0MAX節點MIN節點終端節點3.極小極大搜索過程

對于棋盤殘局中的╳來說，最好的選擇，是將╳放在C的位置上，這時可以導致平局局面。

3.極小極大搜索過程-剪支法的引入在極小極大法中，必須求出所有終端節點的評估值，當預先考慮的棋步比較多時，計算量會大大增加。為了提高搜索的效率，引入了通過對評估值的上下限進行估計，從而減少需進行評估的節點范圍的-剪支法。4.-搜索過程

作為正方出現的MAX節點，假設它的MIN子節點有N個，那么當它的第一個MIN子節點的評估值為時，則對于其它的子節點，如果有高過的，就取那最高的值作為該MAX節點的評估值；如果沒有，則該MAX節點的評估值為。總之，該MAX節點的評估值不會低于，這個就稱為該MAX節點的評估下限值。4.-搜索過程

MAX節點的評估下限值

MIN節點的評估上限值

作為反方出現的MIN節點，假設它的MAX子節點有N個，那么當它的第一個MAX子節點的評估值為時，則對于其它子節點，如果有低于的，就取那個低于的值作為該MIN節點的評估值；如果沒有，則該MIN節點的評估值取。總之，該MIN節點的評估值不會高過，這個就稱為該MIN節點的評估上限值。4.-搜索過程剪支法

MAX節點MIN節點=剪支ABCD4.-搜索過程

設MAX節點的下限為，則其所有的MIN子節點中，其評估值的上限小于等于的節點，其以下部分的搜索都可以停止了，即對這部分節點進行了剪支。

設MIN節點的上限為，則其所有的MAX子節點中，其評估值的下限大于等于的節點，其以下部分的搜索都可以停止了，即對這部分節點進行了剪支。MAX節點MIN節點=剪支ABCD4.-搜索過程剪支法

ABCDEFGHIJKLNOM4.-搜索過程MAX節點MAX節點MIN節點終端節點35652164MAX節點(5,)35652164(6,)(2,)(-,5)(-,2)(5,)MIN節點終端節點剪支剪支ABCDEFGHIJKLNOMMAX節點4.-搜索過程一字棋第一階段-剪支方法4.-搜索過程4.-搜索過程極大節點的下界為。極小節點的上界為。剪支的條件：后輩節點的值≤祖先節點的值時，剪支后輩節點的值≥祖先節點的值時，剪支簡記為：極小≤極大，剪支極大≥極小，剪支4.-搜索過程86-31453-3503-3022-30-2309-300-303305411-31661abcdefghijkmnMAXMINMAXMIN改進方法

使用-剪支技術，當不滿足剪支條件(即)時或值比值大不了多少或極相近時，這時也可以進行剪支，以便有條件把搜索集中到會帶來更大效果的其他路徑上，這就是中止對效益不大的一些子樹的搜索，以提高搜索效率。

4.-搜索過程

不嚴格限制搜索的深度。當到達深度限制時，如出現博弈格局有可能發生較大變化時，則應多搜索幾層，使格局進入較穩定狀態后再中止，這樣可使倒推值計算的結果比較合理，避免考慮不充分產生的影響，這是等候狀態平穩后中止搜索的方法。

4.-搜索過程當算法給出所選的走步后，不要馬上停止搜索，而是在原先估計可能的路徑上再往前搜索幾步，再次檢驗會不會出現意外，這是一種增添輔助搜索的方法。

4.-搜索過程對某些博弈的開局階段和殘局階段，往往總結了一些固定的對弈模式，因此可以利用這些知識編好走步表，以便在開局和結局時使用查表法。只是在進入中盤階段后，再調用其他有效的搜索算法，來選擇最優的走步。4.-搜索過程演講完畢，謝謝觀看！附錄資料：人工智能簡介?AboutTeachingPlan基本要求：人工智能是計算機科學中涉及研究、設計和應用智能機器的一個分支，是目前迅速發展的一門新興學科，新思想新方法層出不窮。其基本思想是利用機器來模仿和執行人腦的功能，如判斷、推理、證明、識別、感知、理解、設計、思考、規劃、學習和問題求解等思維活動。對于培養學生計算機技術的應用能力，開闊思路和視野，有重要意義。

?AboutTeachingPlan因此，要求學生掌握知識表示和問題求解的幾種常用方法，尤其是不確定性推理；掌握機器學習基本概念，了解幾種機器學習方法尤其是神經網絡學習方法；掌握專家系統的概念，了解專家系統設計方法，掌握一些智能控制方法，了解國內外人工智能研究尤其是機器人的最新進展；具有一定的人工智能編程設計能力（利用Lisp或Prolog語言）。?AboutTeachingPlan課程內容以及學時分配人工智能引論(1) 人工智能概念及與計算機的關系，研究途徑、內容和應用領域概況介紹，其他最新材料。符號主義、連接主義、行為主義三大流派人工智能數學基礎(1)知識表示方法（2） 狀態空間法、問題歸約法，謂詞邏輯法、產生式表示法（動物識別系統）；CLIPS語言；語義網絡法、框架法（這是結構化表示）；劇本、過程、Petri網、面向對象的表示。?AboutTeachingPlan 搜索技術和策略（3-4）狀態空間法，盲目搜索和啟發式搜索，A*算法；海伯倫理論、消解原理和策略；與\或形推理和搜索策略；其他求解技術。 不確定推理技術（3-4）主觀Bayes理論；可信度方法和證據理論；系統組織技術；非單調推理；Rete快速算法；模糊推理技術；基于語義網絡和框架不確定推理； 專家系統（2）專家系統概念、結構和知識獲取；黑板模型、知識組織、管理及系統建造和開發工具；專家系統舉例及編程。

人工智能程序設計（1）人工智能語言基本機制：LISP和PROLOG。?AboutTeachingPlan 模式識別導論（3）模式識別專題：概率模式識別。模式識別專題：結構模式識別 機器學習（1）：機械,解釋經驗,事例,歸納,概念,類比學習等；統計,結構,模糊模式識別。 專題講座（3次） 1)神經網絡基本理論和應用 (史奎凡課程：安排于人工智能理論與應用課程內)； 2)智能體（Agent）； 3)自然語言處理； 4)智能控制和機器人科學 智能控制的結構理論和研究領域，智能控制系統及應用示例；機器人規劃、機器視覺和自然語言理解等。?AboutTeachingPlan 實踐：1) 搜索技術和策略2) 不確定推理技術3) 專家系統：動物識別系統4) 模式識別技術5) 調研： 搜索技術和策略、不確定推理技術、統計模式識別、機器學習等四個領域進展報告。?ChapterOne:BriefIntroductiontoArtificialIntelligence1.WhatisAI?人工智能（ArtificialIntelligence,AI）是當前科學技發展的一門前沿學科，同時也是一門新思想，新觀念，新理論，新技術不斷出現的新興學科以及正在發展的學科。它是在計算機科學，控制論，信息論，神經心理學，哲學，語言學等多種學科研究的基礎發展起來的，因此又可把它看作是一門綜合性的邊緣學科。它的出現及所取得的成就引起了人們的高度重視,并取得了很高的評價。有的人把它與空間技術，原子能技術一起并譽為20世紀的三大科學技術成就。?Intelligence智能是知識與智力的總合。 知識——智能行為的基礎； 智力——獲取知識并運用知識求解問題的能力。智能具有以下特征：(1)具有感知能力——指人們通過視覺、聽覺、觸覺、味覺、嗅覺等感覺器官感知外部世界的能力；(2)具有記憶與思維的能力——這是人腦最重要的功能，亦是人之所以有智能的根本原因；(3)具有學習能力及自適應能力；(4)具有行為能力。ArtificialIntelligence人工智能——計算機科學的一個分支，是智能計算機系統，即人類智慧在機器上的模擬，或者說是人們使機器具有類似于人的智慧（對語言能理解、能學習、能推理）。?2.BriefHistoryofAI (1) 孕育（1956年前）古希臘的Aristotle（亞里士多德）（前384-322），給出了形式邏輯的基本規律。英國的哲學家、自然科學家Bacon（培根）（1561-1626），系統地給出了歸納法。“知識就是力量”德國數學家、哲學家Leibnitz（布萊尼茨）（1646-1716）。提出了關于數理邏輯的思想，把形式邏輯符號化，從而能對人的思維進行運算和推理。做出了能做四則運算的手搖計算機英國數學家、邏輯學家Boole（布爾）（1815-1864）實現了布萊尼茨的思維符號化和數學化的思想，提出了一種嶄新的代數系統——布爾代數。?美籍奧地利數理邏輯學家Godel（哥德爾）（1906-1978），證明了一階謂詞的完備性定；任何包含初等數論的形式系統，如果它是無矛盾的，那么一定是不完備的。意義在于，人的思維形式化和機械化的某種極限，在理論上證明了有些事是做不到的。英國數學家Turing(圖靈)（1912-1954）,1936年提出了一種理想計算機的數學模型（圖靈機），1950年提出了圖靈試驗，發表了“計算機與智能”的論文。圖靈獎。美國數學家Mauchly，1946發明了電子數字計算機ENIAC美國神經生理學家McCulloch，建立了第一個神經網絡數學模型。美國數學家Shannon（香農）,1948年發表了《通訊的數學理論》，代表了“信息論”的誕生。? (2) 形成（1956-1969）1956年提出了“ArtificialIntelligence（人工智能）”1956年夏由麻省理工學院的J.McCarthy、M.L.Minsky,IBM公司信息研究中心的N.Rochester,貝爾實驗室的C.E.Shannon共同發起，邀請了Moore,Samuel,Selfridge,Solomonff,Simon,Newell等人，10位數學家、信息學家、心理學家、神經生理學家、計算機科學家，在Dartmouth大學召開了一次關于機器智能的研討會，會上McCarthy提議正式采用了ArtificialIntelligence（人工智能）這一術語。這次會議，標志著人工智能作為一門新興學科正式誕生了。 McCarthy（麥卡錫）——人工智能之父。這次會議之后的10年間，人工智能的研究取得了許多引人矚目的成就.機器學習方面：塞繆爾于1956年研制出了跳棋程序，該程序能從棋譜中學習，也能從下棋實踐中提高棋藝；?在定理證明方面：王浩于1958年在IBM機上證明了《數學原理》中有關命題演算的全部定理（220條），還證明了謂詞演算中150條定理85%；1965年，魯賓遜（Robinson）提出了消解原理；在模式識別方面：1959年塞爾夫里奇推出了一個模式識別程序；1965年羅伯特（Robert）編制出可辨別積木構造的程序；在問題求解方面：1960年紐厄爾等人通過心理學試驗總結出了人們求解問題的思維規律，編制了通用問題求解程序GPS,可以用來求解11種不同類型的問題；在專家系統方面：斯坦福大學的費根鮑姆（E.A.Feigenbaum）自1965年開始進行專家系統DENDRAL（化學分析專家系統），1968年完成并投入使用；在人工智能語言方面：1960年McCarthy等人建立了人工智能程序設計語言Lisp，該語言至今仍是建造智能系統的重要工具；1969年成立了國際人工智能聯合會議（InternationalJointConferencesOnArtificialIntelligence）? (3) 發展（1970年以后）70年代，開始從理論走向實踐，解決一些實際問題。同時很快就發現問題：歸結法費時、下棋贏不了全國冠軍、機器翻譯一團糟。以Feigenbaum為首的一批年輕科學家改變了戰略思想，1977年提出知識工程的概念，以知識為基礎的專家咨詢系統開始廣泛的應用。著名專家系統的有：DENDRAL化學分析專家系統（斯坦福大學1968）MACSYMA符號數學專家系統（麻省理工1971）MYCIN診斷和治療細菌感染性血液病的專家咨詢系統（斯坦福大學1973）CASNET(CausalASsciationalNetwork)診斷和治療青光眼的專家咨詢系統（拉特格爾斯（Rutgers）大學70年代中）CADUCEUS(原名INTERNIST)醫療咨詢系統（匹茲堡大學）；HEARSAYI和II語音理解系統（卡內基-梅隆大學）PROSPECTOR地質勘探專家系統（斯坦福大學1976）XCON計算機配置專家系統（卡內基-梅隆大學1978）??80年代，人工智能發展達到階段性的頂峰。?87,89年世界大會有６－７千人參加。硬件公司有上千個。并進行Lisp硬件、Lisp機的研究。?在專家系統及其工具越來越商品化的過程中,國際軟件市場上形成了一門旨在生產和加工知識的新產業——知識產業。應該說，知識工程和專家系統是近十余年來人工智能研究中最有成就的分支之一。?同年代，1986年Rumlhart領導的并行分布處理研究小組提出了神經元網絡的反向傳播學習算法，解決了神經網絡的根本問題之一。從此，神經網絡的研究進入新的高潮。?90年代，計算機發展趨勢為小型化、并行化、網絡化、智能化。?人工智能技術逐漸與數據庫、多媒體等主流技術相結合，并融合在主流技術之中，旨在使計算機更聰明、更有效、與人更接近。?日本政府于1992年結束了為期十年的稱為“知識信息處理體統”的第五代計算機系統研究開發計劃。并開始了為期十年的實況計算（RealWordComputing）計劃。?3.ResearchObjectsandMainContents

(1)人工智能的研究目標

人工智能的長期研究目標：構造智能計算機。

人工智能的近期研究目標：使現有的電子計算機更聰明，更有用，使它不僅能做一般的數值計算及非數值信息的數據處理，而且能運用知識處理問題，能模擬人類的部分智能行為。?(2)人工智能研究的基本內容

1.機器感知以機器視覺與機器聽覺為主。機器感知是機器獲取外部信息的基本途徑，是使機器具有智能不可或缺的組成部分，對此人工智能中已形成兩個專門的研究領域——

模式識別和自然語言理解。2.機器思維指通過感知的外部信息及機器內部的各種工作信息進行有目的的處理。主要開展以下幾方面的研究：(1)知識表示(2)知識的組織，累計，管理技術(3)知識的推理(4)各種啟發式搜索及控制策略(5)神經網絡，人腦的結構及其工作原理?3.機器學習

使計算能自動獲取知識，能直接向書本學習，能通過與人談話學習，能通過對環境的觀察學習，并能在實踐中自我完善。4.機器行為機器行為主要指計算機的表達能力，即“說”、“寫”、“畫”等，對智能機器人，還應該有人的四肢功能，即能走路，能取物，能操作等。5.智能系統及智能計算機的構造技術?4.ResearchObjectsandMainContents人工智能面世以來，其研究途徑存在兩種不同的觀點：以符號處理為核心的方法——主張通過運用計算機科學的方法進行研究，實現人工智能在計算機的模擬。以網絡連接為主的連接機制方法——主張用生物學的方法進行研究，搞清楚人類智能的本質。(1)以符號處理為核心的方法該方法起源于紐厄爾等人的通用問題求解系統（GPS），用于模擬人類求解問題的心理過程，逐漸形成為物理符號系統，這種方法認為： 人類研究的目標是實現機器智能，而計算機自身具有符號處理能力，這種能力本身就蘊含著演繹推理的內涵，因而可通過運行相應的程序來體現某種基于邏輯思維的智能行為，達到模擬人類智能活動的效果。目前人工智能的大部分研究成果都是基于這種方法實現的。?

該方法的主要特征是：

?立足于邏輯運算和符號操作，適合于模擬人的邏輯思維過程，解決需要進行邏輯推理的復雜問題；

?知識可用顯式的符號表示；

?便于模塊化；?能與傳統的符號數據庫鏈接；?可對推理結論做出解釋，便于對各種可能性進行選擇。

但該方法不適合于形象思維；而且在用符號表示概念時其有效性在很大程度上取決于符號表示的正確性，且對帶噪聲的信息及不完整的信息難以處理。(2)以網絡連接為主的連接機制方法該方法是在人腦神經元及其相互連接而成網絡的啟示下，試圖通過多人工神經元間的并行協同作用來實現對人類智能的模擬。該方法認為：大腦是人類一切智能活動的基礎，因而從大腦神經元及其連接機制著手進行研究，搞清楚大腦的結構及它進行信息處理的過程及機理，可望揭示人類智能的奧秘，從而真正實現人類智慧在機器上的模擬。?該方法的主要特征：?通過神經元之間的并行協同作用實現信息處理，處理過程具有并行性、動態性、全局性；?通過神經元間分布式的物理聯系存儲知識和信息，因而可以實現聯想功能，對于帶有噪聲、缺損、變形的信息能進行有效地處理。近期的一些研究表明，該方法在模式識別、圖像信息壓縮等方面取得了一些研究成果；?通過神經元間連接強度的動態調整來實現對人類學習、分類等的模擬；?適合于模擬人類的形象思維過程；?求解問題時，可以比較快地球的一個近似解。該方法不適合于模擬人的邏輯思維過程，而且就目前神經網絡的研究現狀來看，由固定的體系結構與組成方案所構成的系統還達不到開發多種多樣知識的要求。?(3)系統集成

?符號方法善于模擬人的邏輯思維過程，求解問題時，如果問題有解，它可以準確地求出最優解；但求解過程的運算量將隨問題的復雜性的增加成指數性增長，另外其知識和信息的符號化過程需要由人來完成，它自身不具備這種功能。?連接機制方法善于模擬人的形象思維過程，求解問題時，由于它的并行處理能力，可以較快地得到問題的解，但解一般是近似的，次優