基于Pierre Dellacherie算法的AI俄羅斯方塊設計

薛 鵬，陶嵐菊

（成都錦城學院，四川 成都 611700）

1 AI俄羅斯方塊的研究背景

俄羅斯方塊是一款經典的益智型游戲，如何在俄羅斯方塊里實現不同形狀的板塊的智能旋轉、下落并最終擺放到合適的位置上，是人工智能（Artificial Intelligence，AI）領域的一個問題[1]。俄羅斯方塊的游戲規則如下：由小方塊組成的不同形狀的板塊陸續從屏幕上方落下來，玩家通過調整板塊的位置和方向，使它們在屏幕底部拼出完整的一條滿行或幾條滿行，這些完整的滿行會隨即消失，給新落下來的板塊騰出空間；與此同時，玩家得到分數獎勵。沒有被消除掉的方塊不斷堆積起來，一旦堆到屏幕頂端的游戲上邊界，玩家便告輸，游戲結束[2]。學者Heidi Burgiel經過研究，已證明俄羅斯方塊游戲最終一定會結束。因此，設計AI的目的就是為了讓AI程序獲得更多的分數。AI俄羅斯方塊的實現方法非常多，其中Thiery&Scherrer算法、Pierre Dellacherie算法、DFS算法都可以實現俄羅斯方塊的AI程序。本文主要通過Pierre Dellacherie算法來實現該程序。

2 問題分析與變量抽象

定義俄羅斯方塊的“不死性”：由于游戲的規則是未消除的方塊累計高度達到游戲上邊界的時候游戲失敗，因此方塊高度越低，整局游戲“不死性”就越強。隨著方塊的積累，整局游戲的“不死性”也在下降。通過對“不死性”的分析，將問題抽象成以下6個變量。

2.1 最大高度

該變量用于統計放置后方塊距離底部的距離。俄羅斯方塊游戲結束的條件就是通過決策放置后的方塊有一部分超出游戲規定的上邊界，這時判定游戲失敗。在游戲過程中，方塊累計高度越高，整局游戲的“不死性”也就越低。因此，通過決策放置方塊后所有方塊中的最大高度是決策的重要考察因素之一。

2.2 消除的滿行中屬于本次下落板塊的方塊數量

由于決策期望是消除更多的行數，因此通過決策放置方塊后，消除的滿行中存在本次放置的板塊的方塊數量越多，則說明這次板塊放置的位置越好。需要設置一個全局的數組，數組中存放每一行方塊的空格數量，就可以通過全局的數組算出消除的滿行中有多少方塊是屬于本次放置的板塊的。游戲過程中，方塊模擬放下的過程中只需要記住方塊放下去后能夠消除的行的編號，遍歷出所有的情況，將消除的滿行行數作為數組的下標進行相加，變量Max_count為其最大值。

2.3 行變換

行變換是指原本這個位置沒有方塊但是經過填充后變成有方塊，或者這個位置本來有方塊但是變成沒有方塊，這兩種情況都可以視為發生過一次行變換。統計出所有的變換量，并返回這個參數，行變換的數量從側面上反映出了方塊的平整程度。如果游戲中方塊擺放得不夠平整，特別是在方塊高度累計過高時，會出現某個高度接近游戲上邊界的方塊從而導致游戲的結束。方塊整體上越平整，游戲整體局面的“不死性”就越強。通過逐層的遍歷來實現行變換的統計。

2.4 列變換

列變換是指原本這個位置沒有方塊但是通過決策導致方塊下落在該位置后變成了有方塊，或者這個位置原本有方塊但是通過決策導致方塊被消除變成了該位置沒有方塊。與行變換幾乎相同，不過列變換反映的是空洞的密集程度。空洞對游戲整體局面的影響非常大，列變換的數值越大，出現空洞的概率也就越大。游戲的失敗往往也是由于空洞數量過多而導致的。列變換的統計和行變換的統計二者的差別就是：列變換是先遍歷列，而行變換是先遍歷行。

2.5 空洞數

游戲的失敗往往都是由空洞數過多而引起的。在方塊的擺放序列中，當一個或者多個空格的周圍全部都是方塊時決策就將這個或這些空格視為空洞。當空洞累計到一定程度的時候，對于底部方塊的消除也將變得困難。空洞數的多少也直接決定著游戲的“不死性”。

2.6 “井”總和

“井”的定義是：它的形狀就像生活中的井。中間沒有被方塊填充，兩邊都有連續的方塊（將游戲的邊界也算作方塊）。此函數計算的是“井”的高度之和。如果“井”的大小就是1個空格，那么算作這個“井”的大小是1；如果“井”的大小是3個空格組成，那么“井”總和是3+2+1。需要注意的地方是，“井”的類比和生活中的井非常相似，方塊兩邊的高度不相同的時候遵循“短板效應”，當中間為空格的時候，如果左邊方塊的高度是4，右邊方塊的高度是3，那么“井”總和依舊是按照3+2+1來作為計算結果進行返回。“井”的存在對游戲整體局面的影響和空洞一樣，同樣是致命的，當“井”沒有被落下來的方塊填充反而是將“井”給覆蓋起來的時候，“井”就會變成空洞，從而降低游戲整體局面的“不死性”。

2.7 分析總結

通過對問題的分析，可通過抽象出的以上6個變量，將問題具體化。將以上6個變量相結合且作為變量代入評估函數，就可以對所有方塊放置的情況進行打分處理，選出分數最高的一種情況來進行方塊的放置。如果有多種情況的分數一樣，則優先選擇靠近左邊落下的方案。

3 程序實現

程序采取的是C語言，基于Dev-C++6.5進行實現。俄羅斯方塊AI程序的實現分為兩部分：第一部分是最基本的游戲內容的實現，這個部分能夠實現最原始的俄羅斯方塊的玩法；第二部分就是決策評估部分，通過枚舉每一種方式的擺放方式并且結合決策評估函數，直接將方塊放置在當前游戲整體局面的最佳位置上面，這一部分也是AI功能的重要部分。

3.1 游戲重要函數實現

3.1.1 游戲邊界的打印

游戲邊界使用二維數組，通過遍歷的方式配合語句printf("◆");進行相應的打印。并且將邊界數組所存在的值設置為1，空白的位置的值設置為0。需要注意的是，當方塊下落觸底的時候，不能將方塊位置數組的值也設置為1，這是因為這樣就會讓墻面和觸底的方塊沒有區別，可能導致消除游戲的邊界問題，所以應該將觸底的方塊位置數組的值設置為2，以便和邊界產生區分。

3.1.2 方塊的打印以及變化

方塊的顯示問題使用結構體數組來定義，一共有6種結構體數組，這些結構體數組通過在地圖數組的對應位置上打印方塊來達到生成方塊的目的。方塊的變化也是結構體數組，根據方塊的類型來進行相應的變化，從而選擇最優方案進行下落。

3.1.3 隨機方塊的生成

隨機方塊通過隨機函數struct block*proBlock(int n)來生成，其中n對應的值是rand()%k+1。這樣就可以生成從1到k的數字，這些生成的隨機數字對應的正是不同的初始方塊。

3.1.4 檢測方塊的狀態

檢測方塊的狀態是指檢測這個方塊是不是應該被固定在這個位置無法移動。方塊無法移動的條件就是四周是邊界或者其他的方塊，如果方塊的四周有其他的方塊或者邊界，那么這個方塊就不能繼續向下移動。根據游戲的初始化設定，地圖中沒有方塊的位置的值是0。通過遍歷，如果方塊處往下一格位置的值是1，那么方塊就應該停止下來。

3.1.5 方塊滿行的消除以及相應分數的增加

當方塊在一行排滿的時候，需要將這一行方塊進行消除。每一次方塊下落之后，都從游戲的底部向上面開始遍歷。方塊位置數組賦值是2，當檢查完一行之后，如果統計為2的變量的數值等于方塊的寬度，那么就認為這一行為滿行；再次遍歷這一行，并且在地圖數組上打印出空格，代表這一行已經被消除。繼續向上遍歷，將上面每一行的方塊都向下移動一格，從而達到視覺上的方塊消除效果。每一次方塊滿行被消除后，全局變量score加上對應的分數。

3.2 評估函數實現

枚舉出所有的情況，模擬每個位置擺放的情況，并評估出該位置對應的價值，找出其中的最大值。若其中有兩個相同的最大值，則方案就是從左邊到右邊依次擺放。評估函數具體實現的程序代碼如下。

t1=getLandingHeight(bb);//放置后，滑塊距離底部的距離;

t2=getRemoveBlock(bb);//放置后，消掉的行數有多少塊是屬于這個滑塊的;

t3=getRowTransitions(bb);//統計每一行的變換;

t4=getColTransitions(bb);//統計每一列的變換;

t5=getHole(bb);//統計空洞的個數;

t6=getWell(bb);//統計“井”的個數;

return k1*t1+k2*t2+k3*t3+k4*t4+k5*t5+k6*t6;

在評估完所有的情況之后，就可以進行AI的具體實現。具體實現方法就是通過枚舉的方式再次模擬方塊所有下落的位置，從左到右再次算出評分，如果算出來的評分等于前面算出來的最佳評分，那么方塊就擺放在這個位置。

4 通過遺傳算法和強化學習的方法選取權重

評估函數為k1*t1+k2*t2+k3*t3+k4*t4+k5*t5+k6*t6，這里ki的權重用于評估當前游戲整體局面的優劣程度，如何獲得更加準確的權重是很重要的一件事情。如果想引入新的變量來評估游戲整體局面的優劣程度，那么就需要考慮原本的權重系數是否還適用于新的評估函數，新的權重系數怎樣設置才能讓消除的行數更多。

本文選擇遺傳算法（Genetic Algorithm），遺傳算法非常廣泛地應用于參數的優化問題，對于系數的選擇也可以看作參數的優化問題。初始設置一個種群（可能存在的解集），通過層層篩選以及交叉組合、變異等方式優勝劣汰，根據得分來判斷系數是否合適，從而不斷接近目標解集。比如，初始化1 000個解集，通過得分來判斷適應度，選擇表現相對良好的解集繼續進行交叉組合，設置一點擾動，從而構成下一代的解集繼續篩選，如此反復。

強化學習也可以作為優化權重的一個選擇。在給定的一個解集中，對其中某個系數進行改動，同時程序獲得一個反饋值，這個反饋值可以由分數的改變來體現，再通過反饋值不斷地調整權重，以便獲得更多的激勵，如此往復便可以獲得更好的權重分布。

5 結束語

本文采用Pierre Dellacherie算法，實現了AI版本的俄羅斯方塊，通過多次的試驗，最高消除行數是16萬行左右，平均消除行數是12萬行左右。還有非常多值得改進的地方：一是程序中有多個地方的復雜度都是n2，有的地方甚至達到了n3，這將會讓決策計算消耗大量的時間，如果游戲地圖開得更大一些就會導致性能有所下降，以至于出現明顯的停頓現象，某些部分可以通過動態規劃算法的思想來進行優化。二是算法的評估參數不夠準確，評估函數前面的參數不夠精準導致不能消除更多的行數，參數的調整涉及深入的算法，需要大量的重復試驗來測試。遺傳算法和強化學習還有很多的方式都可以獲得更加合適的權重，是一個非常值得探討的問題，筆者會在未來進行更多的調整。