薛 鵬，陶嵐菊

（成都錦城學(xué)院，四川 成都 611700）

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

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

2 問題分析與變量抽象

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

2.1 最大高度

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

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

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

2.3 行變換

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

2.4 列變換

列變換是指原本這個位置沒有方塊但是通過決策導(dǎo)致方塊下落在該位置后變成了有方塊，或者這個位置原本有方塊但是通過決策導(dǎo)致方塊被消除變成了該位置沒有方塊。與行變換幾乎相同，不過列變換反映的是空洞的密集程度?？斩磳τ螒蛘w局面的影響非常大，列變換的數(shù)值越大，出現(xiàn)空洞的概率也就越大。游戲的失敗往往也是由于空洞數(shù)量過多而導(dǎo)致的。列變換的統(tǒng)計和行變換的統(tǒng)計二者的差別就是：列變換是先遍歷列，而行變換是先遍歷行。

2.5 空洞數(shù)

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

2.6 “井”總和

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

2.7 分析總結(jié)

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

3 程序?qū)崿F(xiàn)

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

3.1 游戲重要函數(shù)實現(xiàn)

3.1.1 游戲邊界的打印

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

3.1.2 方塊的打印以及變化

方塊的顯示問題使用結(jié)構(gòu)體數(shù)組來定義，一共有6種結(jié)構(gòu)體數(shù)組，這些結(jié)構(gòu)體數(shù)組通過在地圖數(shù)組的對應(yīng)位置上打印方塊來達(dá)到生成方塊的目的。方塊的變化也是結(jié)構(gòu)體數(shù)組，根據(jù)方塊的類型來進(jìn)行相應(yīng)的變化，從而選擇最優(yōu)方案進(jìn)行下落。

3.1.3 隨機方塊的生成

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

3.1.4 檢測方塊的狀態(tài)

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

3.1.5 方塊滿行的消除以及相應(yīng)分?jǐn)?shù)的增加

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

3.2 評估函數(shù)實現(xiàn)

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

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

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

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

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

t5=getHole(bb);//統(tǒng)計空洞的個數(shù);

t6=getWell(bb);//統(tǒng)計“井”的個數(shù);

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

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

4 通過遺傳算法和強化學(xué)習(xí)的方法選取權(quán)重

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

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

強化學(xué)習(xí)也可以作為優(yōu)化權(quán)重的一個選擇。在給定的一個解集中，對其中某個系數(shù)進(jìn)行改動，同時程序獲得一個反饋值，這個反饋值可以由分?jǐn)?shù)的改變來體現(xiàn)，再通過反饋值不斷地調(diào)整權(quán)重，以便獲得更多的激勵，如此往復(fù)便可以獲得更好的權(quán)重分布。

5 結(jié)束語

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