2022年人工智能導論實驗報告：吃豆人游戲

1、人工智能試驗報告人工智能導論試驗報告學院：運算機科學與技術學院專業(yè)：運算機科學與技術2022.12.20 目錄人工智能導論試驗報告 . . 1 一、簡介 對該試驗背景,方法以及目的的懂得 . 2 1. 試驗背景 . . 2 2. 試驗方法 . . 3 3. 試驗目的 . . 3 二、方法（對每個問題的分析及解決問題的方法）. 3 Q1: Depth First Search . . 3 1 人工智能試驗報告三、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 試驗結果（解決每個問題的結果）. . 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 自動評分 . . 15 總結及爭論（對該試驗的總結以及任何該試驗的啟示）. 15 一、簡介 對該試驗背景,方法以及目的的懂得 1. 試驗背景1 自人工智能概念被提出,人工智能的進展就受到了很大的關注,取得了長足的進展,成為一門廣泛的交叉和前沿科學；到目前, 弱人工智能取得了長足的進展,而強人工智能就臨時處于瓶頸；2 人工智能試驗報告2吃豆人 Pacman 居住在亮藍色

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

5、中, 我們對下面8 個問題進行爭論, 針對每個問題提出解決方法,逐步完成吃豆人嬉戲：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. 試驗目的1 完成試驗報告中的問題,編寫一系列吃豆人程序,包括到達指定位置以及有效的吃豆；2

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

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

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

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

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

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

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

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

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

15、Search python pacman.py -l mediumMaze -p SearchAgent -a fn=bfs 9 人工智能試驗報告 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 人工智能試驗報告python pacman.py -l mediumDottedMaze -p StayEastSearchAgent python pacman.py

16、 -l mediumScaryMaze -p StayWestSearchAgent 11 人工智能試驗報告Q4: A* Search python pacman.py -l bigMaze -z .5 -p SearchAgent -a fn=astar,heuristic=manhattanHeuristic 12 人工智能試驗報告 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 人工智能試驗報告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 人工智能試驗報告 Q8: Suboptimal Search python pacman.py -l bigSearch -p ClosestDotSearchAgent -z .5 自動評分四、總結及爭論 （對該試驗的總結以及任何該試驗的啟示）1.在這個試驗中,我們對深度優(yōu)先搜尋、廣度優(yōu)先搜尋、代價一樣搜尋和A*算法四種搜15 人工智能試驗報告索方法進行了