2022年人工智能導(dǎo)論實(shí)驗(yàn)報(bào)告：吃豆人游戲

1、人工智能試驗(yàn)報(bào)告人工智能導(dǎo)論試驗(yàn)報(bào)告學(xué)院：運(yùn)算機(jī)科學(xué)與技術(shù)學(xué)院專業(yè)：運(yùn)算機(jī)科學(xué)與技術(shù)2022.12.20 目錄人工智能導(dǎo)論試驗(yàn)報(bào)告 . . 1 一、簡介 對(duì)該試驗(yàn)背景,方法以及目的的懂得 . 2 1. 試驗(yàn)背景 . . 2 2. 試驗(yàn)方法 . . 3 3. 試驗(yàn)?zāi)康?. . 3 二、方法（對(duì)每個(gè)問題的分析及解決問題的方法）. 3 Q1: Depth First Search . . 3 1 人工智能試驗(yàn)報(bào)告三、Q2: Breadth First Search . . 4 Q3: Uniform Cost Search . . 5 Q4: A* Search . . 6 Q5: Corners

2、Problem: Representation . 6 Q6: Corners Problem: Heuristic . . 6 Q7: Eating All The Dots: Heuristic . 7 Q8: Suboptimal Search . . 7 試驗(yàn)結(jié)果（解決每個(gè)問題的結(jié)果）. . 7 四、Q1: Depth First Search . . 7 Q2: Breadth First Search . . 9 Q3: Uniform Cost Search . . 10 Q4: A* Search . . 12 Q5: Corners Problem: Representati

3、on . 13 Q6: Corners Problem: Heuristic . . 14 Q7: Eating All The Dots: Heuristic . 14 Q8: Suboptimal Search . . 15 自動(dòng)評(píng)分 . . 15 總結(jié)及爭論（對(duì)該試驗(yàn)的總結(jié)以及任何該試驗(yàn)的啟示）. 15 一、簡介 對(duì)該試驗(yàn)背景,方法以及目的的懂得 1. 試驗(yàn)背景1 自人工智能概念被提出,人工智能的進(jìn)展就受到了很大的關(guān)注,取得了長足的進(jìn)展,成為一門廣泛的交叉和前沿科學(xué)；到目前, 弱人工智能取得了長足的進(jìn)展,而強(qiáng)人工智能就臨時(shí)處于瓶頸；2 人工智能試驗(yàn)報(bào)告2吃豆人 Pacman 居住在亮藍(lán)色

4、的世界里,在這個(gè)世界有彎曲的走廊和美味佳肴；嬉戲的高目的就是掌握嬉戲的主角小精靈吃掉藏在迷宮內(nèi)全部的豆子,并且不能被幽靈抓到；效地瀏覽世界將是吃豆人把握世界的第一步；3通過本學(xué)期的學(xué)習(xí)我們已經(jīng)初步把握了人工智能的基本學(xué)問,在試驗(yàn)中就應(yīng)用這些學(xué)問使用人工智能操縱吃豆人嬉戲；2. 試驗(yàn)方法1 在本試驗(yàn)中 , Pacman 智能體將找到通過迷宮世界的路徑 , 既包括到達(dá)一個(gè)指定的位置,也包括高效地搜集食物；我們編輯文件 search.py 和 searchAgents.py,編寫一系列吃豆人程序,包括到達(dá)指定位置以及有效的吃豆,并將其應(yīng)用到 關(guān)人工智能功能的完善；Pacman場景,完成對(duì)相2在本試驗(yàn)

5、中, 我們對(duì)下面8 個(gè)問題進(jìn)行爭論, 針對(duì)每個(gè)問題提出解決方法,逐步完成吃豆人嬉戲：Q1: Depth First Search Q2: Breadth First Search Q3: Uniform Cost Search Q4: A* Search Q5: Corners Problem: Representation Q6: Corners Problem: Heuristic Q7: Eating All The Dots: Heuristic Q8: Suboptimal Search 3. 試驗(yàn)?zāi)康? 完成試驗(yàn)報(bào)告中的問題,編寫一系列吃豆人程序,包括到達(dá)指定位置以及有效的吃豆；2

6、 通過分析吃豆人嬉戲鞏固課堂上所學(xué)內(nèi)容；3 復(fù)習(xí) python 語言的使用；二、方法（對(duì)每個(gè)問題的分析及解決問題的方法）Q1: Depth First Search 應(yīng)用深度優(yōu)先算法找到一個(gè)特定的位置的豆,我們通過depthFirstSearch函數(shù)實(shí)現(xiàn)深度優(yōu)先搜尋的功能；深度優(yōu)先遍歷的方法是,從圖中某頂點(diǎn)v 動(dòng)身：直至圖中和v 有路徑相通1拜訪頂點(diǎn) v；對(duì)圖進(jìn)行深度優(yōu)先遍歷；2依次從 v 的未被拜訪的鄰接點(diǎn)動(dòng)身,的頂點(diǎn)都被拜訪；3 人工智能試驗(yàn)報(bào)告3如此時(shí)圖中尚有頂點(diǎn)未被拜訪,就從一個(gè)未被拜訪的頂點(diǎn)動(dòng)身,重新進(jìn)行深度優(yōu)先遍歷,直到圖中全部頂點(diǎn)均被拜訪過為止；深度優(yōu)先搜尋的次序如下圖所示：在

7、depthFirstSearch 中,由于搜尋過程中火重復(fù)拜訪到部分節(jié)點(diǎn),所以需要對(duì)于每個(gè)節(jié)點(diǎn)設(shè)置標(biāo)記, 以指示該節(jié)點(diǎn)是否被拜訪過；先將每個(gè)后繼節(jié)點(diǎn)壓入搜尋棧中,然后以深度優(yōu)先的次序進(jìn)行搜尋,判定是否符合目標(biāo)狀態(tài),并將符合結(jié)果的節(jié)點(diǎn)放入結(jié)果集；Q2: Breadth First Search 應(yīng)用寬度優(yōu)先算法找到一個(gè)特定的位置的豆,我們通過breadthFirstSearch函數(shù)實(shí)現(xiàn)深度優(yōu)先搜尋的功能；廣度優(yōu)先搜尋算法的思想是：從圖中某頂點(diǎn) v 動(dòng)身,在拜訪了 v 之后依次拜訪 v 的各個(gè)未曾拜訪過的鄰接點(diǎn), 然后分別從這些鄰接點(diǎn)動(dòng)身依次拜訪它們的鄰接點(diǎn),并使得“ 先被拜訪的頂點(diǎn)的鄰接點(diǎn)先于后

8、被拜訪的頂點(diǎn)的鄰接點(diǎn)被拜訪,都被拜訪到； 假如此時(shí)圖中尚有頂點(diǎn)未被拜訪,直至圖中全部已被拜訪的頂點(diǎn)的鄰接點(diǎn) 就需要另選一個(gè)未曾被拜訪過的頂點(diǎn)作為新的起始點(diǎn),重復(fù)上述過程,直至圖中全部頂點(diǎn)都被拜訪到為止；如下圖：4 人工智能試驗(yàn)報(bào)告在 breadthFirstSearch 中,大體的搜尋思路與深度優(yōu)先算法一樣,只是搜尋的次序發(fā)生了變化；在這里留意, 在深度優(yōu)先搜尋和廣度優(yōu)先搜尋方法中,我們使用的圖搜尋算法是一樣的,但是涉及到詳細(xì)的數(shù)據(jù)結(jié)構(gòu)卻是不同的；在深度優(yōu)先搜尋算法中,我們使用棧進(jìn)行操作,在深度優(yōu)先搜尋算法中,我們使用隊(duì)列進(jìn)行操作,如下圖所示； 這兩種數(shù)據(jù)結(jié)構(gòu)的不同之處就在于其中元素的輸出次序

9、,在深度優(yōu)先搜尋中需要根據(jù)壓棧次序的逆序進(jìn)行搜尋,咋子廣度優(yōu)先搜尋中需要根據(jù)入隊(duì)次序的次序進(jìn)行搜尋；Q3: Uniform Cost Search 很多情形下,路徑中的代價(jià)是可以轉(zhuǎn)變的,在這個(gè)問題中,我們完成代價(jià)一樣搜尋方法；代價(jià)一樣搜尋, 其實(shí)就是一個(gè)貪心搜尋,取代擴(kuò)展深度最淺的節(jié)點(diǎn),代價(jià)一樣搜尋擴(kuò)展的是路徑消耗最低的節(jié)點(diǎn) n；假如全部單步耗散都相等的話,這種算法就和廣度優(yōu)先搜尋算法是5 人工智能試驗(yàn)報(bào)告一樣的； 不過,這樣在擴(kuò)展到一個(gè)具有能返回到同一狀態(tài)的零耗散行動(dòng)的節(jié)點(diǎn)時(shí)就會(huì)陷入無限循環(huán)；在 uniformCostSearch 函數(shù)中,我們運(yùn)算每條路徑的總代價(jià),將總代價(jià)作為優(yōu)先級(jí)進(jìn)行搜尋

10、,待搜尋序列儲(chǔ)備于隊(duì)列中；對(duì)于每個(gè)節(jié)點(diǎn),使用代價(jià)函數(shù) getCostOfActions 運(yùn)算其所產(chǎn)生的代價(jià),并依次作為搜尋的優(yōu)先級(jí)進(jìn)行搜尋；Q4: A* Search 同樣的,對(duì)于每個(gè)節(jié)點(diǎn)添加是否被拜訪的標(biāo)記；A*算法是一種靜態(tài)路網(wǎng)中求解最短路最有效的直接搜尋方法,也是很多其他問題的常用啟示式算法,對(duì)代價(jià)一樣搜尋算法進(jìn)行了改進(jìn),加入了一個(gè)估量代價(jià) h ；公式表示為：fn=gn+hn, 其中 fn 是從初始狀態(tài)經(jīng)由狀態(tài) n 到目標(biāo)狀態(tài)的代價(jià)估量,gn 是在狀態(tài)空間中從初始狀態(tài)到狀態(tài) n 的實(shí)際代價(jià), hn 是從狀態(tài) n 到目標(biāo)狀態(tài)的正確路徑的估量代價(jià)（對(duì)于路徑搜尋問題,狀態(tài)就是圖中的節(jié)點(diǎn),代價(jià)就

11、是距離）；在本試驗(yàn)中, 我們使用曼哈頓距離作為啟示函數(shù)；在 aStarSearch 函數(shù)中, 我們第一搜尋具有最低組合成本和啟示式的節(jié)點(diǎn)；類似于問題三, 我們運(yùn)算每個(gè)節(jié)點(diǎn)的代價(jià),并以此為依據(jù)搜尋產(chǎn)生結(jié)果集,在搜尋的過程中,仍需要標(biāo)記節(jié)點(diǎn)是否已經(jīng)被拜訪過；Q5: Corners Problem: Representation 找到全部的角落, 在角落迷宮的四個(gè)角上面有四個(gè)豆,角落的最短的路徑；通過這個(gè)函數(shù)找到一條拜訪全部四個(gè)在 CornersProblem類中,我們使用_init_函數(shù)儲(chǔ)備墻壁的位置,吃豆人的起點(diǎn)和角落位置,定義新的函數(shù)getStartState用于獲得節(jié)點(diǎn)起始狀態(tài),isGoal

12、State函數(shù)判定當(dāng)前節(jié)點(diǎn)是 否 為 目 標(biāo) 節(jié) 點(diǎn) , getSuccessors函 數(shù) 返 回 后 繼 狀 態(tài) , 所 需 的 操 作 以 及 代 價(jià) ,getCostOfActions 函數(shù)運(yùn)算動(dòng)作序列所需的代價(jià)；查找后繼節(jié)點(diǎn)時(shí),在四個(gè)方向一次遍歷,使用 directionToVector 移動(dòng)位置,假如沒有墻,就把下一個(gè)的狀態(tài),動(dòng)作,花費(fèi)的步數(shù)加入下一節(jié)點(diǎn)Q6: Corners Problem: Heuristic 構(gòu)建合適的啟示函數(shù),完成問題 5 中的角落搜尋問題；在問題五使用的 CornersProblem 類中定義 cornersHeuristic 函數(shù),為角落問題構(gòu)造啟示函數(shù)；

13、在 cornersHeuristic 函數(shù)中使用了 GetNextNodes 函數(shù)獵取下一個(gè)節(jié)點(diǎn),isGoal 函數(shù)判定是否為目標(biāo)；6 人工智能試驗(yàn)報(bào)告 Q7: Eating All The Dots: Heuristic 用完可能少的步數(shù)吃掉全部的豆子；這個(gè)問題利用之前 法在這里不再詳述；A*算法可以很簡單找到解,此種方下面在 FoodSearchProblem 類中定義函數(shù)foodHeuristic,構(gòu)建合適的啟示函數(shù)完成豆子搜索（啟示式）問題；Q8: Suboptimal Search 次最優(yōu)搜尋,定義一個(gè)優(yōu)先吃最近的豆子的函數(shù),以此來提高搜尋速度；補(bǔ) 充 AnyFoodSearchPr

14、oblem 目 標(biāo)測 試 函 數(shù), 并在 ClosestDotSearchAgent 當(dāng) 中 添加findPathToClosestDot 函數(shù),用于查找最近的豆子；三、試驗(yàn)結(jié)果（解決每個(gè)問題的結(jié)果）Q1: Depth First Search python pacman.py -l tinyMaze -p SearchAgent python pacman.py -l mediumMaze -p SearchAgent 7 人工智能試驗(yàn)報(bào)告python pacman.py -l bigMaze -z .5 -p SearchAgent 8 人工智能試驗(yàn)報(bào)告Q2: Breadth First

15、Search python pacman.py -l mediumMaze -p SearchAgent -a fn=bfs 9 人工智能試驗(yàn)報(bào)告 python pacman.py -l bigMaze -p SearchAgent -a fn=bfs -z .5 Q3: Uniform Cost Search python pacman.py -l mediumMaze -p SearchAgent -a fn=ucs 10 人工智能試驗(yàn)報(bào)告python pacman.py -l mediumDottedMaze -p StayEastSearchAgent python pacman.py

16、 -l mediumScaryMaze -p StayWestSearchAgent 11 人工智能試驗(yàn)報(bào)告Q4: A* Search python pacman.py -l bigMaze -z .5 -p SearchAgent -a fn=astar,heuristic=manhattanHeuristic 12 人工智能試驗(yàn)報(bào)告 Q5: Corners Problem: Representation python pacman.py -l tinyCorners -p SearchAgent -a fn=bfs,prob=CornersProblem python pacman.py

17、-l mediumCorners -p SearchAgent -a fn=bfs,prob=CornersProblem 13 人工智能試驗(yàn)報(bào)告Q6: Corners Problem: Heuristic python pacman.py -l mediumCorners -p AStarCornersAgent -z 0.5 Q7: Eating All The Dots: Heuristic python pacman.py -l trickySearch -p AStarFoodSearchAgent 14 人工智能試驗(yàn)報(bào)告 Q8: Suboptimal Search python pacman.py -l bigSearch -p ClosestDotSearchAgent -z .5 自動(dòng)評(píng)分四、總結(jié)及爭論 （對(duì)該試驗(yàn)的總結(jié)以及任何該試驗(yàn)的啟示）1.在這個(gè)試驗(yàn)中,我們對(duì)深度優(yōu)先搜尋、廣度優(yōu)先搜尋、代價(jià)一樣搜尋和A*算法四種搜15 人工智能試驗(yàn)報(bào)告索方法進(jìn)行了