騰訊極客挑戰賽第四期：鵝羅斯方塊——賽后復盤

1.比賽總結

??七月底的時候在網路上看到了這樣一個賽事，賽題大概總結起來就是用代碼玩一款十分經典的游戲俄羅斯方塊，通過游戲得分來排名評比，覺得挺有意思，抱著隨便試試的想法就參加了，結果最后獲得了全國第49名，最侄訓得的最高分數是31萬多一點，雖然和第一名的一百多萬還是有不小的差距，需要改進反省的地方還有很多，但這一成績還是基本達到了我的預期的，同時我也是成功獲得了騰訊招聘的綠色通道，豐富了自己的履歷，

2.比賽復盤

??在賽事官網可以找到俄羅斯方塊游戲的比賽入口，進入游戲之后可以發現游戲的界面是一下這樣的：

??光看這個游戲界面，這就是一個普通的俄羅斯方塊游戲，但其實玄機藏在瀏覽器的控制臺中，打開瀏覽器的控制臺，很容易就可以找到這個游戲的原始碼，因為騰訊官方在控制臺的代碼資源中用注釋告訴你了原始碼的網址，我們將整個游戲專案拉到本地之后，就可以“魔改代碼”，大展身手了，
??在本地用IDE打開這個游戲專案，可以看到游戲使用JavaScript寫的，而且是基于vue.js框架，雖然我的“主戰場”是后端Java Web，但對前端JS還是比較熟悉的，特別是vue框架，“魔改代碼”基本上還是綽綽有余的，所以我選擇了直接在原始碼上進行代碼添加，實作用演算法跑俄羅斯方塊，
??經過上網查詢俄羅斯方塊演算法相關資料后，我了解到目前的主流俄羅斯方塊AI演算法是基于A*演算法的啟發式搜索，基本思路就是定義一個啟發函式對當前局面進行評估，對于每一個當前即將下落的方塊，遍歷方塊下落的所有情況——以各個形狀在所有位置下落的情況，對于每一種情況，通過啟發函式算出局面評估的評分，在所有情況中，評分最高的就是當前最優的下落情況，然后將當前方塊旋轉到該最優情況所對應的形狀，再移動到對應最佳位置，下落即可，
??我的演算法思路基本上就是以上所闡釋的啟發式搜索，確定了演算法方向之后，接下來的關鍵就是這個啟發函式該如何設計，這決定了如何定義方塊該以怎樣的形狀，在哪個位置下落，通過網上資料我了解到，目前存在三種比較普遍的方案，
??第一種是最經典的Pierre Dellacherie演算法，其對局面進行評估的啟發函式包含以下6項指標：

?1. landingHeight(下落高度): 指當前板塊放置之后，板塊重心距離游戲區域底部的距離
　
　2. erodedPieceCellsMetric(消行評分): 代表的是消除的行數與當前擺放的板塊中被消除的小方塊的格數的乘積，
　
　3. boardRowTransitions(行變換): 對于每一行小方格，從左往右看，從無小方格到有小方格是一種“變換”，從有小方格到無小方格也是一種“變換”，這個屬性是各行中“變換”之和
　
　4. boardColTransitions(列變換): 每一列的變換次數之和
　
　5. boardBuriedHoles(空洞數): 各列中的空洞的小方格數之和
　
　6. boardWells(井數): 各列中“井”的深度的連加和，井是指中間一列為高度低于左右兩列的情況，整體呈現為凹字形

最后的啟發函式定義為：

value = x1 × landingHeight + x2 × erodedPieceCellsMetric + x3 ×
boardRowTransitions + x4 × boardColTransitions + x5 ×
boardBuriedHoles) + x6 × boardWells


x1:-1
x2: 1
x3:-1
x4:-1
x5:-4
x6:-1

value的取值越高，說明當前下落情況越優，

??第二種是在Pierre Dellacherie演算法的基礎上進行提升的El-Tetris演算法，該演算法對原Pierre Dellacherie演算法的第二項指標erodedPieceCellsMetric有略微調整，同時改進了各個評價指標的系數

?1. landingHeight(下落高度): 指當前板塊放置之后，板塊重心距離游戲區域底部的距離
　
　2. rowsEliminated(消行數): 代表的是消除的行數
　
　3. boardRowTransitions(行變換): 對于每一行小方格，從左往右看，從無小方格到有小方格是一種“變換”，從有小方格到無小方格也是一種“變換”，這個屬性是各行中“變換”之和
　
　4. boardColTransitions(列變換): 每一列的變換次數之和
　
　5. boardBuriedHoles(空洞數): 各列中的空洞的小方格數之和
　
　6. boardWells(井數): 各列中“井”的深度的連加和，井是指中間一列為高度低于左右兩列的情況，整體呈現為凹字形

啟發函式定義為：

value = x1 × landingHeight + x2 × rowsEliminated + x3 ×
boardRowTransitions + x4 × boardColTransitions + x5 ×
boardBuriedHoles) + x6 × boardWells


x1: -4.500158825082766
x2: 3.4181268101392694
x3: -3.2178882868487753
x4: -9.348695305445199
x5: -7.899265427351652
x6: -3.3855972247263626

??第三種是我在相關論文——Improvements on Learning Tetris with Cross Entropy 中看到的又一種改進演算法，這種演算法在Pierre Dellacherie的基礎上增加了兩個評估指標：holeDepth和rowsWithHoles，同時對評估指標的系數進行了重新定義，

?1. landingHeight(下落高度): 指當前板塊放置之后，板塊重心距離游戲區域底部的距離
　
　2. erodedPieceCellsMetric(消行評分): 代表的是消除的行數與當前擺放的板塊中被消除的小方塊的格數的乘積，
　
　3. boardRowTransitions(行變換): 對于每一行小方格，從左往右看，從無小方格到有小方格是一種“變換”，從有小方格到無小方格也是一種“變換”，這個屬性是各行中“變換”之和
　
　4. boardColTransitions(列變換): 每一列的變換次數之和
　
　5. boardBuriedHoles(空洞數): 各列中的空洞的小方格數之和
　
　6. boardWells(井數): 各列中“井”的深度的連加和，井是指中間一列為高度低于左右兩列的情況，整體呈現為凹字形
　
　7. holeDepth（空洞深度）:各列所有的空洞的空洞深度之和
　
　8. rowsWithHoles（存在空洞的行數）：存在空洞的行的行數之和

啟發函式定義為：

value = x1 × landingHeight + x2 × erodedPieceCellsMetric + x3 ×
boardRowTransitions + x4 × boardColTransitions + x5 ×
boardBuriedHoles) + x6 × boardWells + x7 × holeDepth + x8 × rowsWithHoles


x1: -12.63
x2: 6.60
x3: -9.22
x4: -19.77
x5: -13.08
x6: -10.49
x7: -1.61
x8: -24.04

??以上三種啟發函式我都進行了嘗試，呈現出的效果是第二種和第三種啟發函式明顯要比原始的Pierre Dellacherie演算法的啟發函式更加的優秀，但依舊會有不小的幾率中途方塊觸頂死掉，我分析這其中的原因可能是比賽所有的方塊序列都是既定的，而且各個方塊的出現次數不一樣，s型和z型方塊的出現頻率明顯要高于其他I,L,J,T,O型方塊，
??既然AI演算法也有可能方塊觸頂 game over，那么該如何調整呢，我采取的方法是當游戲程序中方塊堆疊過高超過設定閾值時，轉為手動操作方塊下落，AI做不到的事情我來手動完成，當通過我的手動操作，方塊堆疊高度又下降到閾值以下后，又轉換為AI演算法進行操作，在這樣做了反復嘗試之后，分數最高可以達到23、24萬左右的樣子，
??隨后，為了進一步提高分數，我又在演算法中進行了小的調整——在使用AI演算法進行自動方塊下落的程序中，始終保證局面中最左邊的一列中沒有空洞，如果當前下落的位置會使最左邊的一列出現空洞，即使局面評估分數再高也不選擇這個位置進行下落，保證最左邊一列沒有空洞，這樣會使得消去時一次消去多行的可能性有所增加，增加分數倍率，同時也使得局面中的方塊堆疊高度維持在一個中等水平，不會太高也不會太低，也可以增加單次消去分數增加量，體現了“富貴險中求”的精神，

（專案原始碼中官方在注釋里給玩家的建議：富貴險中求）

??但這樣操作又使得AI演算法觸頂暴斃的概率進一步增大了，就算切換成手動操作模式我也無力回天，那么又該怎么辦呢？我想到的方法是——再設定一個高度閾值，當局面中方塊堆疊高度低于這個閾值時，AI演算法采用激進模式——保證最左邊一列沒有空洞，但是當堆疊高度高于這一閾值時，AI演算法采用常規模式——不必保證最左邊一列沒有空洞，這樣來回轉換AI演算法模式，使方塊堆疊高度在一個高度區間內反復橫跳，分數的增速也比只采用常規模式來的更快，這樣進行設定之后，也需要注意一個問題，就是當常規模式切換成激進模式時，需要保證切換的一瞬間局面中最左邊一列是沒有空洞的，不然就會導致激進模式下最左邊一列一直不被填充，
??為了AI演算法不死幾率進一步提高，我依舊在此基礎上設定了手動模式的開啟閾值，以及一個激進模式和常規模式的轉換觸發按鍵，
??最終我的最高分數來到了31萬多一點，排在全國第49名，

3.反思問題

??雖然我最后也是搭上了前50名的末班車，但其實在比賽程序中我還是可以總結出很多問題，首先就是在演算法的選擇上欠妥，這種啟發式搜索演算法僅僅只能最大程度的保證游戲的不死性，但對于如何盡量的去獲得更高的分數還是無能為力的，即使我為了提高分數在該演算法的基礎上做出了一點點的改進，但分數提升幅度依然不大，相較于第一名的100多萬還是有著很大很大的差距，其次是設計演算法時對于如何更有效的提高分數考慮不足，導致最終的分數進步幅度一直很小，
??這些方面的問題在比賽后期一直阻擋著我沖刺更高的分數，引以為戒，

4.參賽原始碼

??參賽原始碼我放在了我的GitHub中，地址：https://github.com/HelloWorld-Ian/tx_geekGame