貪吃蛇游戲解題報告

1、貪吃蛇問題淺析福州一中 嚴寒凝問題描述貪吃蛇在一個 n*m 的網(wǎng)格上游動，(n=10 m=22)網(wǎng)格上存在一些食物，蛇必須以固定的順序這些食物。在游動過程中，如果蛇碰到自己的身體或網(wǎng)格的邊緣，則結(jié)束。為了簡化問題，作如下假設：初始時，蛇的長度小于網(wǎng)格的列數(shù)，是第一行上的一條線段，如圖這是蛇長為 3 的情況的目標是尋求一組可行解，使得蛇吃到盡可能多的食物。解題思路算法 A 搜索：很明顯，如果搜索所有的狀態(tài)的話，是可以得到一組可行甚至是最優(yōu)的解的，但這個方法時空復雜度太高，不能適應題目 22*10 的規(guī)模。考慮玩時的策略，假設知道所有食物出現(xiàn)的順序，在吃一個蘋果的時候，肯定會盡可能考慮現(xiàn)在采取的這

2、個決策能不能保證蛇可以吃到后面幾個蘋果。我用的是類似貪心的局部化搜索，就是在吃一個蘋果時，選擇一種能夠保證吃到下面 D個蘋果的策略。相當于對于每一個蘋果做一個蘋果數(shù)為 D 的深搜。這樣做至少比直接吃下一個蘋果的貪心。但這個方法我實現(xiàn)了一下（見附件 Snack.pas），取 D=4,但效果不甚理想。首先是狀態(tài)的數(shù)組不能撐到 22*10 需要的那么大。其次，由于我用的是普通的深度優(yōu)先搜索，時間復雜度太高，當 N=10, M=10, 蘋果數(shù)為 100 的時候就撐不下去了。然后我又試了一下 D=0,也就是不考慮后面的蘋果，直接找一種合法到達下一個蘋果的方案，但是效果也不好，而且在大規(guī)模數(shù)據(jù)下經(jīng)常出現(xiàn)誤

3、判無解的情況，因為在找到第一個蘋果之后蛇身就已經(jīng)得不成樣子，。如果用啟發(fā)式搜索的方法，根據(jù)蘋果與蛇間的距離確定搜索順序會有所改進，這個我沒有實現(xiàn)，但估計提高不大。由此看來，搜索的方法不能很好的解決這個問題。那是不是可以不用搜索的方法找出吃下一個蘋果的方法呢？這讓到一個問題：在一定的條件下，（譬如蛇身長度不超過長或?qū)挼淖钚≈担┠懿荒苷业桨福咕W(wǎng)格中的蛇的任意兩種形態(tài)能夠互相轉(zhuǎn)變呢？知道，在網(wǎng)格中處于一條直線的蛇可以卷曲成任意的形狀，因為蛇頭可以到達網(wǎng)的任意格子，可以運用構造的方法。而卷曲的蛇是否也一定可以轉(zhuǎn)化為一條直線，或者貼著網(wǎng)個邊緣的線的形式呢？如果可以的話，可以以直線為中間狀態(tài)，實現(xiàn)這二者

4、之間的轉(zhuǎn)化。換句話說：在給定的兩個蛇的狀態(tài)中，這兩種狀態(tài)之間能不能相互轉(zhuǎn)換呢？有沒有搜索之外的方法，可以較快的判斷這似乎也可以作為一道競賽題，譬如說：不需要知道蛇走的路徑，而僅僅需要求出最多能吃到多少個蘋果。這個問題我沒有解決。希望大家提供幫助。算法 B 構造：由于題目要求的是一組可行解，這很容易讓想到用構造法。事實上，的蘋果。只要讓蛇處在一個經(jīng)過所有格子的回路中循環(huán)游動，就可以保證吃到所有。值得注意的是當圖的行數(shù)和列數(shù)中有一個或全部是偶數(shù)的時候構造這樣的回路。但當行列數(shù)均為奇數(shù)時，是不能構造這樣的回路的。可以用類似的方法在這樣的時候可以先挖去圖的一角（記這個格子為 a），構造出覆蓋除這一角外

5、的回路，這是可以做到的。如果蘋果不出現(xiàn)在a 上，則問題解決。如果蘋果出現(xiàn)在 a 上的話，路的形狀，如圖：只需改變一下回這樣并不影響回路的長度。能夠保證蛇至少可以吃到 （N*M-蛇身初始長度）個蘋果如此，算法 C 遺傳規(guī)劃：這個問題與遺傳算法中經(jīng)典的人工蟻問題有著相似之處，而且該問題也具有局部最優(yōu)可以考慮使用遺傳規(guī)劃算法。我用的是現(xiàn)成的 GPC+ 4.0 遺傳規(guī)劃的庫，定義節(jié)點和函數(shù)如下（和人工螞蟻基本類性，似）:Terminal_T take=TurnRight,TurnLeft,MoveForward, TurnRight, TurnLeft, MoveForward;Function_T

6、fake=IfFoodAhead,2, ( IfFoodAhead,IfDangerAhead, 2, ( IfDangerAhead,IfDangerRight, 2, ( IfDangerRight,IfDangerLeft,Prog2,2, ( IfDangerLeft,2, ( Prog2);用的估值函數(shù)比較簡單，即吃到蘋果的個數(shù)。在某次運行算到第 36 代的時候，得到了這樣一個程序，在 11*20 的網(wǎng)機環(huán)境大致可以吃到 51 個蘋果，對隨Generation : 36Average Fitness : 10.591 Average Length: 129.972 Best Of G

7、eneration was :( ( IfFoodAhead MoveForward ( IfDangerAhead ( IfFoodAhead ( IfDangerAhead ( IfFoodAhead ( Prog2 ( IfDangerLeft ( IfDangerLeft ( IfDangerAhead TurnRight MoveForward ) ( IfDangerLeft TurnRight MoveForward ) ) ( Prog2 ( IfDangerAhead TurnRight TurnRight )( IfFoodAhead ( Prog2 ( IfFoodAhe

8、ad ( IfFoodAhead TurnLeft TurnRight ) ( IfDangerLeftMoveForward TurnLeft ) ) ( IfDangerLeft ( IfDangerAhead TurnLeft MoveForward )( IfFoodAhead MoveForward TurnRight ) ) ) ( IfDangerRight ( IfDangerRight ( Prog2 TurnRight TurnRight ) ( IfDangerAhead TurnLeft TurnLeft ) ) ( IfFoodAhead ( IfDangerAhea

9、d TurnLeftMoveForward ) ( IfDangerRight ( ( IfFoodAhead (Prog2 TurnLeft TurnLeft ) ) ) ) ) ) MoveForward ) ( IfDangerRightProg2 TurnRight TurnLeft ) ( IfDangerAhead TurnLeft TurnLeft ) ) IfDangerAhead TurnLeft MoveForward ) ( IfFoodAhead TurnLeftTurnRight ) ) ) ) ( Prog2 ( IfDangerLeft ( IfFoodAhead

10、 ( IfFoodAhead TurnRight TurnRight ) ( IfDangerRight TurnLeft TurnRight ) ) ( IfDangerLeft ( IfDangerRight TurnLeft MoveForward ) ( IfDangerAhead TurnRight TurnLeft ) ) ) ( IfDangerAhead ( IfFoodAhead ( Prog2 ( Prog2 TurnRight TurnLeft ) MoveForward ) ( IfDangerRight ( IfDangerRight ( IfDangerLeft T

11、urnLeftTurnLeft ) ( IfDangerAhead TurnLeft TurnLeft ) ) ( IfFoodAhead ( IfDangerAhead TurnLeftMoveForward ) ( IfFoodAhead TurnLeft TurnRight ) ) ) )MoveForward TurnLeft ) ( IfFoodAhead ( IfDangerAhead ( IfDangerLeft ( IfFoodAhead IfFoodAhead ( IfDangerAheadTurnRight MoveForward ) )(IfDangerAhead Tur

12、nRight TurnRight ) ( IfDangerRightIfFoodAhead ( IfDangerRight MoveForward TurnLeft ) ( Prog2 TurnRight TurnRight ) ) )IfDangerLeft ( IfFoodAhead ( IfFoodAhead ( Prog2 ( IfDangerLeft TurnRight TurnLeft )MoveForward ) ( IfFoodAhead ( IfFoodAhead ( Prog2 TurnLeft TurnLeft ) ( IfDangerLeft TurnRight Tur

13、nLeft ) ) ( Prog2 MoveForward TurnRight ) ) ) ( Prog2 TurnRight TurnRight ) ) ( IfFoodAhead ( IfDangerLeft MoveForward TurnLeft ) ( IfDangerAhead TurnRight TurnLeft ) ) ) ) ( Prog2 MoveForward TurnRight ) ) ) ) ) ) ( IfFoodAhead ( IfDangerRight TurnLeft TurnRight ) ( Prog2 TurnRight TurnRight ) ) ) ( IfDangerLeft ( IfFoodAhead ( Prog2 MoveForward TurnRight ) ( IfDangerLeft MoveForward TurnRight ) ) ( IfFoodAhead( IfDangerLeft MoveF