基于Pierre Dellacherie算法的AI俄羅斯方塊設(shè)計(jì)

薛 鵬，陶嵐菊

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

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

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

2 問(wèn)題分析與變量抽象

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

2.1 最大高度

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

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

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

2.3 行變換

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

2.4 列變換

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

2.5 空洞數(shù)

游戲的失敗往往都是由空洞數(shù)過(guò)多而引起的。在方塊的擺放序列中，當(dāng)一個(gè)或者多個(gè)空格的周?chē)慷际欠綁K時(shí)決策就將這個(gè)或這些空格視為空洞。當(dāng)空洞累計(jì)到一定程度的時(shí)候，對(duì)于底部方塊的消除也將變得困難。空洞數(shù)的多少也直接決定著游戲的“不死性”。

2.6 “井”總和

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

2.7 分析總結(jié)

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

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

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

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

3.1.1 游戲邊界的打印

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

3.1.2 方塊的打印以及變化

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

3.1.3 隨機(jī)方塊的生成

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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