1、人工智能課程報告推箱子小游戲的人工智能尋路 學院：姓名：學號：班級：指導教師： 人工智能課程報告一簡介推箱子游戲簡介經典的推箱子是一個來自日本的古老游戲，目的是在訓練你的邏輯思考能力。在一個狹小的倉庫中，要求把木箱放到指定的位置，稍不小心就會出現箱子無法移動或者通道被堵住的情況，所以需要巧妙的利用有限的空間和通道，合理安排移動的次序和位置，才能順利的完成任務。勝利條件就是把所有的箱子都推到目的地。本程序的目標就是利用啟發式搜索實現電腦自動推箱子。推箱子游戲地圖程序采用手機中的推箱子小游戲的程序，地圖總共75張，難度由易到難，搜尋路徑的計算復雜度也會越來越高。每一張地圖都以文本文件的形式存儲起來

2、。地圖展示：（第1關）（第35關）（第56關）（第75關）保存到文本文件中的地圖代碼：推箱子中人的行為人只可以推箱子, 不可以拉, 而且一次只能推動一個。即使是處于目的位置的箱子也可以推走。二基本概念啟發式搜索考慮一個普通的圖搜索問題：給出初始狀態(節點 s)和目標狀態(節點 t，可以不止一個)以及 狀態的產生規則，求從 s 到 t 的一條路經。搜索過程可描述如下：1待展開的節點集合(OPEN 表)為 s，已展開的節點集合(CLOSED 表)為 ，節點 s 的層深為 g(s) = 0。2每次從 OPEN 表中取出一個節點 n，根據規則擴展產生一組節點 mi，然后把 n 放入 CLOSED 表中

3、。節點 mi 可能屬于下列三種情況之一：（1）新的節點，則把 mi 的源標記為 n，層深 g(mi) = g(n) + 1，并放入 OPEN 表中。（2）已在 OPEN 表中存在的節點，并且層深 g(mi) > g(n) + 1，說明從 s 到 mi 并且經由 n 的路徑要比先前搜索得到的路徑要短。因此，把 mi 的源改記為 n，層深 g(mi) = g(n) + 1，仍放入 OPEN 表中。（3）已在 CLOSED 表中存在的節點，并且層深 g(mi) > g(n) + 1。同理，把 mi 的源改記為 n，層深 g(mi) = g

4、(n) + 1，并從 CLOSED 表中取出重新放入 OPEN 表中，留待以后重新搜索計算 mi 的子節點的層深。3不斷重復上一步操作，直到滿足下列條件之一：（1）n = t，搜索成功。（2）OPEN 表為空，搜索失敗。在以上過程中，如何從 OPEN 表中選取待擴展的節點是關鍵。如果每次均選取層深 g(n) 最小的節點，以上過程就是寬度優先搜索；如果每次均選取層深 g(n) 最大的節點，以上過程 就是深度優先搜索。啟發式搜索算法A*的思想是，給節點定義一個評價函數f(n) = g(n) + h(n) (1)其中，g(n) 是節點的層深，即從 s 到 n 目前搜索已知的最短路

5、徑長度，h(n) 是節點 n 到目標節點 t 的最短路徑長度的估計值，稱為啟發函數。擁有最小 f(n) 值的節點有希望成為從 s 到 t 的最短路徑上的一個節點，因而被取出并擴展。啟發函數 h(n) 具有下列一些性質(證明略，我也不完全懂)：如果 h(n) 處在從 n 到 t 的最短路徑長度的真實值 h*(n) 的下界，即恒有 h(n) <= h*(n)，則算法A*找到的一定是從 s 到 t 的最短路徑。此時算法A*稱為算法A*。可以想象，h(n) 越接近真實值 h*(n)，它所包含的啟發信息就越多，搜索所需擴展的節點數就越少。如果對所有節點 ni 和 nj (其中

6、nj 是 ni 的子節點)都有 h(ni) - h(nj) <= 1，則稱啟發函數 h(n) 滿足單調限制條件。此時，算法A*在選取節點 n 進行擴展時，必有 g(n) = g*(n)，在搜索過程中不會出現把 mi 從 CLOSED 表中取出重新放入 OPEN 表的情況。三算法的設計與實施推箱子游戲模塊推箱子游戲初始化模塊畫圖模塊移動箱子模塊移動小人模塊功能控制模塊程序中定義的四個函數：int orderDown(NodeInfo *infos, int *opens, const int &open_used, int root);堆的向下(從根到

7、葉)調整，內部使用int orderUp(NodeInfo *infos, int *opens, const int &open_used, int leaf);堆的向上(從葉到根)調整，內部使用template <class Node> int key(Node *nodes, const int &hash_size, const Node &n);在散列數組中查找節點template <class Node> int solve(Node *nodes, int hash_size, Node s);搜索函數，程序的入口基于可重用性的考慮

8、，搜索函數 solve 被定義為模板函數，它操作的對象是一個表示節點的 模板類。節點類要求具有被搜索函數使用的一些基本接口，這些接口描述了節點的基本行為和屬性，而節點的 具體意義(比如表示推箱子的某個狀態)則隱藏在類的實現細節中。節點類的基本接口如下：int from;節點的源，返回目標路徑時使用Node();空節點的構造函數int possibleMoves() const;可能的擴展節點數int move(int sw);按第 sw 種擴展方式改變節點int h() const;啟發函數int isTarget() const;判斷節點是否目標節點int isNull() const;判斷

9、節點是否空節點int hash() const;散列函數friend int operator = (const Node &left, const Node &right);判斷兩個節點是否同一void output() const;輸出為了提高速度，節點的存儲和查找使用開地址散列，使用簡單的線性探測解決沖突。程序中的 Node nodes 和 NodeInfo infos 是并列的兩個散列數組，分別存儲所有已展開的節點 和節點的附加信息(f 值和在 OPEN 表中的位置)。key 根據節點的散列函數 hash() 在散列數組中查找或分配節點。OPEN 表實際上是一個優先隊列

10、，因而采用堆的方式實現。程序中的 int opens 是以數組(完全二叉樹)存儲的堆，數組元素表示節點在散列數組中的位置，最小 f 值的節點可以在 堆的根即 opens0 處中給出。orderDown 和 orderUp 是調整堆的需要。推箱子應用通用程序求解推箱子問題，關鍵是節點類的實現。狀態的劃分推箱子的狀態由人和箱子的位置決定。考慮到人可以在墻壁和箱子圍成的連通區域內任意行走 而不會對局面產生實質性的影響，規定人必須位于他所處的連通區域的左上角。考慮到箱子的全同性，箱子的 坐標應從小到大排序。這些都在構造函數 Box() 或者節點擴展函數 move(sw) 中完成。這時，判斷 兩個狀態是

11、否相等只需分別比較每個箱子和人的坐標是否相等即可。節點的擴展每個箱子可以推向四個方向，因此總的可能的擴展節點數是箱子數的四倍。考慮到人的 可到達范圍(way)的限制，某些箱子的某些方向(push_directions)是不可到達的。另外，地圖中 還存在一些“死位置”(dead_positions)，比如墻角、兩個箱子并列在墻邊等等。還有，箱子的背后 可能是墻壁或者另一個箱子。這些不可能的情況都可以在節點擴展函數 move(sw) 中予以拒絕。啟發函數可以計算所有箱子離最近的目標的距離之和作為啟發函數 h() 的返回值。不難看出，此定義的 啟發函數滿足算法A*的下界條件，因而找到的目標路徑一定是

12、最優解。A*算法的偽代碼如下：創建兩個表，OPEN表保存所有已生成而未考察的節點，CLOSED表中記錄已訪問過的節點。算起點的估價值;將起點放入OPEN表;while(OPEN!=NULL) 從OPEN表中取估價值f最小的節點n; if(n節點=目標節點) break;for(當前節點n 的每個子節點X) 算X的估價值; if(X in OPEN) if( X的估價值小于OPEN表的估價值 ) 把n設置為X的父親; 更新OPEN表中的估價值; /取最小路徑的估價值if(X inCLOSE) if( X的估價值小于CLOSE表的估價值 ) 把n設置為X的父親; 更新CLOSE表中的估價值; 把X

13、節點放入OPEN /取最小路徑的估價值if(X not inboth) 把n設置為X的父親; 求X的估價值; 并將X插入OPEN表中; /還沒有排序/end for 將n節點插入CLOSE表中; 按照估價值將OPEN表中的節點排序; /實際上是比較OPEN表內節點f的大小，從最小路徑的節點向下進行。/end while(OPEN!=NULL)保存路徑，即 從終點開始，每個節點沿著父節點移動直至起點，這就是你的路徑；哈希函數可以將所有箱子的坐標移位相加再平方取中，得到哈希函數 hash() 的返回值。以上是我的推箱子程序的主要思路，如果你感興趣，請進一步閱讀我的程序。(可能不太好讀。)四調試分析

14、我的程序在電腦配置較低的條件下(需要根據情況修改程序中 HASH_SIZE 和 HEAP_SIZE 的設置)基本上可以解六個箱子之內的關，八到十個箱子的關或者特別復雜的六個箱子的關解起來會 比較費勁，特別復雜的八個箱子以上的關基本上就解不了了。啟發式搜索雖然可以在很大程度上 縮小搜索空間，但是無法根本解決指數爆炸的問題。目前我能想到一些改進措施是：如果不苛求最優解，可以適當增大上文提到的啟發函數值。事實上，所有箱子離最近的目標的 距離之和與實際到達目標所需的步數之間有很大的差距，因而擴展生成了許多無關的節點。增大啟發函數 值，例如人為的給它乘以二，以犧牲最優解為代價更快地到達目標。用另一種方式

15、計算每個箱子到達目標所需的步數。考慮一個箱子緊挨著一個目標的情況，因為 地圖和人的位置關系，箱子很可能根本無法一步推到目標上，這時簡單的以箱子和目標的距離計算就 不太合適了。一種可能的辦法是，在正式搜索之前先搜索得出一個箱子從不同的位置出發推到目標所需的 步數。不過，這點改進對搜索的性能能有多大提高還是一個未知數。刪除搜索樹上的“死”分枝。這點屬于對啟發式搜索通用程序的改進，與推箱子無關。但是 測試表明，在推箱子的搜索過程中，“死”分枝的比例一般只占總節點數的一半左右。因此，這點改進帶來 的效果估計也不會很明顯。五結論（包括結果）結論：啟發式搜索可以比較好的解決推箱子問題。運行結果：點擊運行程

16、序，顯示如下圖：可選擇關卡，選擇完關卡后點擊“確定”，然后點擊“演示”，則程序進入自動演示狀態，每點擊一下鼠標，電腦便會自動移動一步，如下圖：當顯示“演示完畢”時，演示結束，電腦便會給出最終結果：六心得體會通過這次上機實習，不僅讓我對人工智能有了一定的了解，更重要的還讓我學會了、或者說是驗證了“做事一定要有次序和對事物的總體把握”這句話。開始我一味的進行調試，急切的想僥幸調試出來，但由于沒有進行深入的考慮，我調試了很久都沒沒有成功，我仔細的分析材料，在原由的基礎上我進行了改正，終于調試成功了，雖然這個過程還是經過了一翻努力，當然汗水還是留的很值，這次編程報告，不僅讓我對人工智能這門課程有了更深入的研究、對很多重要的概念有了鞏固和掌握，還給了我今后做事的啟示。做事要塌實，不能想著一步登天，要有計劃，有目的的進行做事。我們應該認真找到自己的缺點并且及時改正。此時此刻，我心里多了些成就感。這是我整個學習過程中的一次經驗、一次總結，我相信它肯定會給我今后的學習有所啟示和指導作