【正文】 2023/1/22 19:08:2419:08:2422 January 2023? 1一個人即使已登上頂峰，也仍要自強不息。勝人者有力，自勝者強。 一月 21一月 21Friday, January 22, 2023? 閱讀一切好書如同和過去最杰出的人談話。 。 一月 2119:08:2419:08Jan2122Jan21? 1世間成事，不求其絕對圓滿，留一份不足，可得無限完美。 2023/1/22 19:08:2419:08:2422 January 2023? 1做前，能夠環(huán)視四周；做時，你只能或者最好沿著以腳為起點的射線向前。 一月 21一月 2119:08:2419:08:24January 22, 2023? 1他鄉(xiāng)生白發(fā)，舊國見青山。 一月 21一月 21Friday, January 22, 2023? 雨中黃葉樹，燈下白頭人。初始狀態(tài)為空棋盤，從起點到終點的路徑表明了贏棋的走法。? 按交叉概率 pc之行 交叉 操作。模擬退火? 一次對參數(shù)改變一點，測試。棋盤控制174。和負(fù)極大值搜索結(jié)合在每一層都進(jìn)行 Beta剪枝。這一過程稱為 α剪枝。估價函數(shù)定義如下– 設(shè)棋局為 P，估價函數(shù)為 e(P)– (1) 若 P對任何一方來說都不是獲勝的位置，則e(P)=e(那些仍為 MAX空著的完全的行、列或?qū)蔷€的總數(shù) )e(那些仍為 MIN空著的完全的行、列或?qū)蔷€的總數(shù) )– (2) 若 P是 MAX必勝的棋局，則 e(P)＝ +∞。? (5) 如果一個行動方案能獲得較大的倒推值，則它就是當(dāng)前最好的行動方案。　　 (3) 為計算得分，需要根據(jù)問題的特性信息定義一個估價函數(shù)，用來估算當(dāng)前博弈樹端節(jié)點的得分。　　我們假定 MAX先走，處于奇數(shù)深度級的節(jié)點都對應(yīng)下一步由 MAX走，這些節(jié)點稱為 MAX節(jié)點，相應(yīng)地偶數(shù)級為 MIN節(jié)點?！　?(2) 在博弈樹中， 或 節(jié)點和 與 節(jié)點是逐層交替出現(xiàn)的。此時，如果我們站在 MAX方的立場上，則可供 MAX方選擇的若干行動方案之間是 或 關(guān)系，因為主動權(quán)操在 MAX方手里，他或者選擇這個行動方案，或者選擇另一個行動方案，完全由 MAX方自已決定。　　 (3) 任何一方在采取行動前都要根據(jù)當(dāng)前的實際情況，進(jìn)行得失分析，選取對自已為最有利而對對方最為不利的對策，不存在擲骰子之類的 碰運氣 因素。稱之為 走法產(chǎn)生 。棋為 例（ 1）第一步該做什么？數(shù)據(jù)結(jié)構(gòu)的選取 —— 棋盤表示占用空間 〉少操作速度 〉快是否方便 〉方便在機器中表示棋局，讓程序知道博弈狀態(tài)。極大極小算法是所有搜索算法的基礎(chǔ)。這個博弈樹的根節(jié)點是當(dāng)前時刻的棋局，它的兒子節(jié)點是假設(shè)再行棋一步以后的各種棋局，孫子節(jié)點是從兒子節(jié)點的棋局再行棋一步的各種棋局，以此類推，構(gòu)造整棵博弈樹，直到可以分出勝負(fù)的棋局。? 1997年 IBM的 “深藍(lán) ”戰(zhàn)勝了國際象棋世界冠軍卡斯帕羅夫，驚動了世界。電腦棋手：永不停歇的挑戰(zhàn)！? 2023年 “ 更弗里茨 ” 擊敗了除了克拉姆尼克之外的所有排名世界前十位的棋手。? 圖搜索算法中的幾個重要名詞術(shù)語– （ 1） OPEN表與 CLOSE表– （ 2）搜索圖與搜索樹你可曾聽說過 “深藍(lán) ”？ 1997年 5月 11日， IBM開發(fā)的 “深藍(lán) ”擊敗了國際象棋冠軍卡斯帕羅夫。在這種情況下 , 窮盡式搜索策略諸如深度優(yōu)先或廣度優(yōu)先搜索 , 在一個給定的較實際的時空內(nèi)很可能得不到最終的解? 和發(fā)明創(chuàng)造的所有規(guī)則一樣 , 啟發(fā)式策略也是極易出錯的圖搜索策略? 圖搜索策略的定義– 圖搜索策略可看作一種在圖中尋找路徑的方法。醫(yī)療診斷即是一例。– 如 , 廣度優(yōu)先法幾乎可以用于解一切搜索問題：九宮圖 (八數(shù)碼難題 ), hanoi塔 (焚塔問題 ), 旅行推銷員 , 華容道 , 以至魔方等等。3747384732847473764766475274525247826345725138251? 啟發(fā)性信息– 用于指導(dǎo)搜索過程，且與具體問題求解有關(guān)的控制性信息稱為啟發(fā)性信息? 啟發(fā)信息的強度– 強：降低搜索工作量，但可能導(dǎo)致找不到最 優(yōu)解– 弱：一般導(dǎo)致工作量加大，極限情況下變?yōu)? 盲目搜索，但可能可以找到最優(yōu)解希望：? 引入啟發(fā)知識，在保證找到最佳解的情況下，盡可能減少搜索范圍，提高搜索效率。6382475141313768617452818831476626646165525238686844737647525247528847314747如果沒有后繼節(jié)點，則轉(zhuǎn)向上述第(2)步。無信息圖搜索過程? 寬度優(yōu)先搜索– (1) 把起始節(jié)點放到 OPEN表中 (如果該起始節(jié)點為一目標(biāo)節(jié)點，則求得一個解答 )。– (4) 如果節(jié)點 n的深度等于最大深度，則轉(zhuǎn)向 (2)。　 王 A：壽命 47，有兒子王 B王 B王 B2　　王 B1：壽命 77，有兒子王 C王 C2　　王 B3：壽命 52，有兒子王 D1　　王 B2：壽命 65，有兒子王 E王 E2　　王 F1：壽命 32　　王 G1：壽命 96　　王 C2：壽命 87，有兒子王 F1　　王 D1：壽命 77，沒有兒子　　王 E1：壽命 57，有兒子王 G1　　王 E2：壽命 92，有兒子王 H1 　　王 C1：壽命 27，沒有兒子　　王 H1：壽命 51? 若 X=57，如何尋找？無信息圖搜索過程? 深度優(yōu)先搜索– (1) 把起始節(jié)點 S放到未擴展節(jié)點 OPEN表中。對已在 CLOSED表上的每個 M成員，確定是否需要更改圖 G中通向它的每個后裔節(jié)點的指針方向。把 M的這些成員作為 n的后繼節(jié)點添入圖 G中。? (4) 選擇 OPEN表上的第一個節(jié)點，把它從OPEN表移出并放進(jìn) CLOSED表中。這一過程稱為 “擴展一個節(jié)點 ”。 一些基本概念? 節(jié)點深度：根節(jié)點深度 =0其它節(jié)點深度 =父節(jié)點深度 +10123一些基本概念（續(xù) 1）? 路徑設(shè)一節(jié)點序列為 (n0, n1,…,nk)，對于 i=1,…,k，若節(jié)點 ni1具有一個后繼節(jié)點 ni，則該序列稱為從 n0到 nk的路徑。14, RETURN CONS(R, PATH)?；厮菟阉魉惴?1（續(xù)）9, RULES:=TAIL(RULES)。5, IF LENGTH(DATALIST)BOUND RETURN FAIL。存在問題及解決辦法? 問題：– 深度問題– 死循環(huán)問題? 解決辦法：– 對搜索深度加以限制– 記錄從初始狀態(tài)到當(dāng)前狀態(tài)的路徑回溯搜索算法 1BACKTRACK1（ DATALIST） DATALIST：從初始到當(dāng)前的狀態(tài)表（逆向）返回值：從當(dāng)前狀態(tài)到目標(biāo)狀態(tài)的路徑（以規(guī)則表的形式表示）或 FAIL。7, RDATA:=GEN(R, DATA)。3, RULES:=APPRULES(DATA)。 遞歸的思想（續(xù)）當(dāng)前狀態(tài)目標(biāo)狀態(tài) g回溯搜索算法BACKTRACK（ DATA） DATA：當(dāng)前狀態(tài)。(2,4)())Q((1,2))Q((1,2))((1,1))((1,1)())Q((1,2))Q((1,2))((1,1))((1,1)(2,4))((1,1)(2,4)())()((1,1))((1,1)(2,3)) ((1,1)(2,4))((1,1)(2,4)(2,4))()Q((1,1))((1,1))(有兩種基本方式 :– 一種是不考慮給定問題所具有的特定知識 , 系統(tǒng)根據(jù)事先確定好的某種固定排序 , 依次調(diào)用規(guī)則或隨機調(diào)用規(guī)則 ,這實際上是盲目搜索的方法 , 一般統(tǒng)稱為無信息引導(dǎo)的搜索策略。還可以分得更細(xì)。搜索技術(shù)? 搜索問題是 AI核心理論問題之一– 一般一個問題可以用好幾種搜索技術(shù)解決 , 選擇一種好的搜索技術(shù)對解決問題的效率很有關(guān)系 , 甚至關(guān)系到求解問題有沒有解。A紐厄爾 )和 H當(dāng)對這些后繼狀態(tài)使用算子生成更進(jìn)一步狀態(tài)時，首先應(yīng)對哪一狀態(tài)進(jìn)行操作呢？這取決于搜索策略，不同搜索策略的操作順序是不相同的。? 下棋（撲克、西洋跳棋、國際象棋、象棋等）（屬于