導語 | 騰訊雲+社群聯合騰訊碼客、騰訊安全平臺部全新打造的創新賽事【騰訊極客挑戰賽 | 鵝羅斯方塊】正式落幕。玩鵝羅斯方塊，玩點不一樣！在短暫10天內，4570名參賽者或以自己的硬核技術詮釋著 “程式碼無所不能”；或堅持遊戲主義，手玩出一片天。 最終11263次有效提交中，湧現出一批出眾的作品。快跟上團隊！一睹大牛精心貢獻的解題報告。
本期為大家帶來亞軍大佬——北航研究生陳銘煊的報告。看完他的解題過程，小編直呼“我的強迫症治好了！”（請看下方影片）
大佬這樣說
在七月末，出於偶然瞭解到騰訊極客挑戰賽這個充滿趣味性和挑戰性的競賽，於是便報名參加。這次第四期的賽題叫做“鵝羅斯方塊”，要求參賽者用所能盡到的各種方式，在一個JS開發的俄羅斯方塊遊戲中取得儘可能高的分數。經過一週多的持續思考與努力最佳化，最終透過動態規劃+狀態取捨，拿到1378178分，獲得外部賽道銀獎，也算是如願以償。下面是我的比賽經過：
一、線上的啟發式演算法—EI-Tetris
試玩了兩三下我就知道我的手速絕對不可能趕上方塊出現的速度（最高階每塊0。1s）了。於是我想到要找一個合適的AI演算法，然後用自動按鍵在介面上操作方塊。在演算法上我選取了名為EI-Tetris的演算法：
原作者的文章：https：//imake。ninja/el-tetris-an-improvement-on-pierre-dellacheries-algorithm/
一些中文的解釋：https：//wangzhechao。com/e-luo-si-fang-kuai-ai-suan-fa-shi-xian-jiao-cheng/
簡單地說，這個演算法的思路是提取一個結果局面的六個特徵點：
Landing Height：
表示當前方塊放置之後的高度；
Rows eliminated：
表示當前方塊落下後被消減的行數；
Row Transitions：
水平方向上變換次數；
Column Transitions：
垂直方向上的變換次數；
Number of Holes：
空洞個數；
Well Sums：
所有“深井”的深度和。
接著將六個特徵和權重引數向量點積求和，得到結果局面的估價，其中權重引數是經過粒子群演算法迭代選取的：
估價越大，則認為結果局面越好。
每一次我們列舉所有的方塊放置位置，選取最好的局面作目標，執行決策，就是演算法的總流程。可以看出這個演算法很易於實現。
開發方面我Web不太瞭解，對Qt比較熟悉。於是把遊戲頁面用QWebEngine載入，這樣我就可以在視窗中用Qt的方式對遊戲進行操作了：
然而辛苦地倒騰大半天，最後只能拿到大概23W的分數。原因是方塊的數量是居然是有限的（10000塊），哪怕AI再靈活，用完方塊之後遊戲就結束了。看來保證“不死”不是關鍵，得分的要素還是在於迎合特殊的計分方式上。
二、對規則與遊戲程式碼的分析
但如果收遊戲包含10000塊，其計分是這樣的：
顯然我們要一次性消去儘量多的行，同時局面還要壘得足夠高。比方留一個凹槽專門給長條，那麼就有很好的收益。
此外我更仔細地看了網頁和JS檔案的原始碼，發現方塊的序列是完全固定的：由一個固定種子的隨機數生成器來決定方塊的種類，又由已有方塊數對4取模得到方塊的朝向，所有的方塊中心在座標
(0,4)
（上至下第0行，左至右邊第4行）
這樣的話，可以用離線的方式去拼湊方塊，來獲得比線上響應更好的結果了。
三、狀態取捨下的動態規劃
很容易想到動態規劃的思想，我們拿第i步後產生的局面作為一個狀態s，維護到達該狀態的最大分數Scorei，s，那麼我們最好的解就是maxs∈SN（ScoreN，s） ，N=10000，其中SN是N步後所有的合法狀態。我採用四個
uint64_t
的整數儲存局面，每個儲存20×10的局面中的五行。每一次對新方塊，遍歷當前狀態集合中所有的局面，得到新局面集合，並計算到新局面的最大積分。
然而，可能的狀態數目實在太多了，有220×10種，沒有辦法在動態規劃中全部儲存。勢必有狀態取捨。
我一開始的想法是首先在擴充套件的過程中，按照安全性估價函式篩查出固定數目狀態進行儲存（主要目標是局面安全），經過固定步數，再對分數進行貪心，取出唯一最高分狀態繼續擴充套件（主要目標是高分）。
在實踐的過程中經過比對，決定把分數的因素引入估價函式，不再額外對做分數做貪心。每一步都按照估價函式保留一定數目的狀態，並在維護其分數，記憶操作序列和前驅序列。
主體框架：
四、估價函式的選取
在儲存狀態數目一樣的情況下，估價函式決定了哪些狀態值得保留，對於演算法的表現尤為重要。
我的估價函式由安全估分和局面分兩部分組成，以得分小的局面為優：
其中第一項得到了之前EI-Tetris演算法的啟發，實現如下：
其中
params
取值如下：
不同之處去掉了
Landing Height
和
row Elimination
，增加了
Count
引數（局面中已有方塊個數）以激勵堆放。這是因為實踐中發現由於狀態數足夠多，安全性不再居於關鍵地位，更重要的是為後續的得分提供輔助作用。
此外，也去掉了
Well Sums
，因為發現引入的時候會出現局面中會留存一個寬度為2的槽的情況，去掉之後就會只要一個寬度為1的槽來供長條消去，對得分更有效益。
對於第二項，透過不斷地人工調參，我將局面得分的權重
scoreWeight
定在了
1.0/38
。
當然，中間確定估價還經過了大量的嘗試，很多嘗試發現沒有必要，這裡就不再贅述。
實現完畢之後發現效果異常地好，程式會很自然地將方塊疊到兩邊，中間留出了凹槽，每來一個長條都能有很高的分。
演算法的原始碼放在了以下網址：
（https：//github。com/MaxDumbledore/Tencent_Geek_Competition_4）
預設設定的
reservedBoardCount
為1000，已經能跑出130W的成績了，本機大概用時兩分鐘。設定為30000，能跑出137W的成績，大概用時一個半小時。
五、一些可能的改進
首先調參的技術活可能需要額外的演算法做幫助，人工調參確實很困難。
其次擴張時沒有搜尋所有的可放置狀態，為了方便只是考慮了旋轉+降落的情況，透過觀察其他選手的回放，發現考慮在內是有價值的。
另外對於演算法效能上，一些資料結構可以最佳化，另外應該加入OpenMP或者多執行緒做並行化。
最後，該演算法的得分點過於偏向對長條的利用，沒有利用好其他方塊的消行得分。後期增大保留的狀態數對於分數增長幫助也不是很大，估計採用這個演算法架構能到達的上限不會超過140W。如果要突破的話還是需要對其他選手的演算法借鑑一二。
六、總結
總得來說，我的思路並不複雜，高分也有一定運氣成分。賽後透過對其他選手解法的學習，我的眼界也有了開拓。所謂極客挑戰賽，就是不斷追求極致，不斷學習和突破的過程。這是很愉快的參賽經歷，同時我十分期待下一期會有什麼不一樣的新挑戰。
作者簡介
陳銘煊
北京航空航天大學計算機學院碩士研究生
本科就讀於北京航空航天大學大學網路空間安全學院，現於北京航空航天大學計算機學院攻讀計算機視覺方向碩士研究生。曾參與過多項知名演算法競賽，其中ICPC與CCPC區域賽中獲金獎，藍橋杯軟體類獲C++組與Python組的省一等獎，廣泛參與開發類和安全類競賽並取得優異成績。