前言

在盆友圈里收到消息,鵝廠舉辦了一場俄羅斯方塊的刷分比賽,私聊一下發圖的同學拿到了體驗連接,好像還挺簡單的嘛,遂決定抽空參賽。

由于上班時候在負責別的項目,整體參賽時間并不多,上班不摸魚,妻子下班比我晚半小時,下班還要路上買菜、回家做飯、洗碗、拖地、洗衣服blabla,周末還要和父母相聚喝一下早茶聊幾句日常,實在躲不掉,這么算起來其實最后的參賽時間也就10小時左右。

本來打算用C語言重寫AI邏輯然后計算,無奈時間上并不足夠,我也知道JS的運行效率相對較低,但是這也是我時間限制之內能夠做到的最大操作了,望各位看官大佬們見笑。

代碼分析

show me the code!!!

好吧,github地址在這,master上面幾條提交記錄,都是針對不同分數的調參結果

https://github.com/jiabuda/tetris-ai

用1小時準備開發環境

前面說了,參賽時間并不多,當我著手準備參賽的時候已經是周三夜晚,幸好主辦方并沒有在代碼上刁難選手,直接在js里面提供了壓縮前的代碼,由于平時也經常采用vue框架開發項目,所以類似動態渲染、閉包這種寫法并不在話下。用谷歌瀏覽器打開頁面,F12然后點擊source先把首頁源碼摳下來,然后把所有min.js都替換成未壓縮前的js代碼,試運行了一次,能跑通,下落幾次然后輸出方塊操作步驟無誤,第一步結束。

用2小時研究算法

周四上一天班下來,上班午休也有搜索了一下相關的資料,還在github上下載了C#和JS版的兩份俄羅斯方塊的AI程序,到了晚上,抽時間研究一下相關算法,相信很多參賽的朋友首先搜索到的算法應該都是這個PD算法,作者名字還超級難念,暫且念作皮埃爾·得拉契吧,本人熟練粵語、國語、英語,和別人說起這個名字,都想含在嘴里吐不出來的感覺,相關資料如下

El-Tetris – An Improvement on Pierre Dellacherie’s Algorithm

從算法上看,并不是太復雜,針對一個方塊,旋轉4次90度,針對每一列的下落到底情況,對最后的整體疊加狀態進行評分,一共有6個評分值,還有通過群論推斷出來的6個相應的權重

評分 =  下落位置的高度 *-4.500158825082766 + 消行數 *3.4181268101392694+        行變換*-3.2178882868487753 + 列變換 *-9.348695305445199+        空洞數 *-7.899265427351652 + 井統計 *-3.3855972247263626

具體的參數介紹可以查看相關的文章,其中行變換、列變換、井統計都是有一定理論的,這也是影響AI外掛擺放形態的關鍵,另外,使用這種算法是針對隨機方塊,對當前局面進行的一種評分,網絡上很多繼承這種方法的代碼,都號稱能做到玩不死,跑了一晚手工停止。但是這也是限制這種算法在這個比賽的一個很大的因素。

用2小時分析【鵝羅斯方塊】代碼并加入外掛

周五上班下來,晚上開始動手搞鵝廠的代碼了,現在這個地方引入一個自定義的AI文件,這種做法也是很多網頁型外掛的常用做法,包括某電商大廠經常推出積分活動,論壇里就經常有大佬寫出JS的外掛,只要執行一句代碼,引入他寫的js文件,網頁上就可以自動瀏覽,自動積分等等……

<!-- 俄羅斯方塊核心計算文件,包含:獲取方塊、移動方塊、旋轉方塊、邊界檢測等功能 --><script type="text/javascript" src="js/tetris.core.js"></script><!--引入自定義AI--><script type="text/javascript" src="js/tetris.ai.js"></script><!-- 俄羅斯方塊游戲主文件,包含:游戲的啟動暫停、游戲時鐘單步 runner 的邏輯控制(playStep 和 replayStep)、游戲回放(playRecord)、畫布渲染 --><script type="text/javascript" src="js/tetris.game.js"></script>

然后找到俄羅斯方塊核心代碼里面,生成新方塊的位置,把AI代碼植入

this.trackOp('new');if (isValid) {    this.nextBrickRawInfo = nextBrickRawInfo;}//在這里可以觸發AI計算,傳入當前的網格狀態,和輪到哪一個方塊了window.ai.calc(this.grids, this.brickCount - 1)

然后在AI代碼里面做了兩個比較簡單的函數,用來加速AI的計算和方便自己使用

//官方代碼的網格用字符串形式,這里轉成boolean形式,true代表有方塊占有,false代表沒有getBooleanGrid()//下落函數,官方的下落函數計算目的太多,修改不方便,這里自己重寫一個,計算方塊下落后,返回最終的網格狀態drop()//格子是否有效函數,判斷下落后到哪一行停止posValid()

有了上述的幾個函數之后,其實都大概可以推斷出我的意圖了

有了最終的網格狀態之后,就可以送入評分函數了,由于評分函數涉及較多理論,需要的請看源碼吧,評分之后很簡單的一個取最大評分數之后,獲取到旋轉的方向和應該從哪一列下落,就可以調用相關函數進行操作游戲了

let game = window.game//1毫秒后自動操作setTimeout(() => {    for (let i = 0; i < bestS; i++) {        //旋轉方塊        game.tetris.rotate()    }    if (bestC > 4) {        //右移        game.playStep('right', bestC - 4, true)    }    if (bestC < 4) {        //左移        game.playStep('left', 4 - bestC, true)    }    //下落到底    game.tetris.drop();}, 1)

這里一個簡單的外掛就已經完成了,整個游戲已經可以自己玩下去了,使用PD算法可以獲得15w分左右的分數

用2小時改進,使用DFS進行多層搜索

其實參賽的初期,看到有的選手已經拿到了100w+的分數,我就知道這個游戲肯定不會那么簡單,有網友稱PD算法是針對無狀態局面,意思就是AI壓根就不知道下一個方塊是什么,只是針對當前給到的方塊給出最佳的位置。而鵝廠的代碼是使用線性同余隨機數產生的方塊排列,理論上可以遍歷所有的方塊獲取最佳排序,然后給出設定的條件拿到最好的路徑。

因為工作原因,平時公司的工作都是針對棋類進行算法編寫,所以我知道這個計算量根本就不是普通計算機可以承受的,一層搜索就40種可能(當然沒把o型特殊性考慮,這里只是純理論說說),二層搜索就1600種可能,三層搜索就64000種可能……

“只有一種可能性”是奇異博士通過“時間寶石”窺視未來,得到了14000506次結局當中唯一一次勝利的機會。

所以不用想了,搜索個10層,比找到打敗滅霸的方法還要難。而且針對鵝羅斯方塊的計分方式,因為是采用【富貴險中求】的方式進行計分,可能第一層搜索到的低分數局面,大概率會在第二層中獲得高分數(例如二層消4),所以盲目地對第一層進行剪枝是不可取的。

所以,我這里簡單地使用了二層搜索,取二層的最高分,然后把第一層的結果輸出給畫面進行擺放,這時候可以獲得了20W分的成績。但是,缺點也帶進來了,DFS需要時間進行計算以獲得高分數,不使用深度搜索,3分鐘就可以打完10000個方塊,使用DFS兩層搜索,需要20分鐘才能結束,而且還可能因為過度追求高分數,而把自己“絆死”的局面,導致AI完全找不到一種可以放方塊的可能性,然后結束了游戲。

最后一天沖刺,人肉調參算出高分數

改用DFS的時候已經是周六,當天還被家里人拉出去喝早茶,然后參觀別人家的魚池,泡茶磕龍眼聊聊家常,足足閑了一天。本來打算能有20W分就算了吧,但看了下形勢,可能掉出名次拿不到任何獎勵,那也心有不甘。這時候我最容易想到的方式就是調參,因為PD的參數沒有針對【富貴險中求】這個玩法進行優化,查看了幾次“絆死”的局面,AI對于“井統計”這個參數并不重視導致最后一個深深的井把自己送進了死路。所以調整了幾個參數,進行了跑分。

這里有一個比較有趣的插曲,本人上班的電腦是九代i5+16G臺式機,平日在家會用家里的老筆記本處理一下服務器故障,需要的時候遠程一下辦公室電腦進行編程操作。偏偏那天網絡抽了風的慢,鼠標一卡一卡的,遂放棄遠程連接。把家里所有能跑JS的設備都堆到一起,同時對不同的參數組合進行刷分。

刷分的時候已經是周日的早上10點多了,做完家務開始處理最后的沖刺

出場的設備有四代的i5,某果11,某為P30Pro,還有一臺平時刷b站用的2代賽揚chromebook,居然刷了幾次分數,發現某果的處理器對于h5優化真的是出奇的好,用一騎絕塵來形容真不是夸張,用這個DFS無剪枝的算法跑到300個方塊僅需要40多秒,而四代的i5還需要50秒,當然9代i5只需要28秒就可以了。

最后調節了幾個參數,跑了一下午的分,也沒有想過上三層搜索,三層搜索估計到比賽結束都不知道能不能跑完一輪,一個方塊要差不多1.5s的運算時間。修正了幾次參數之后,用某果11跑出了47w的成績,把這個參數轉到筆記本上重跑一次,然后輸出操作步驟上傳成績,用這個分數作為最終成績提交。

后記

感謝大會主辦方組織的這次比賽,作為一個轉行從事程序工作的中年程序員,沒有受過專業的軟件開發教育,對于算法也是靠著自己的理解來掌握,畢竟大學里面不是計算機系,沒有接觸過相關的課程。這次能低門檻地參與到大廠的比賽中,與一眾大佬們切磋技藝,雖然最后分數不高,但志在參與,目標就是為家里愛妻拿一張視頻會員卡?？吹絼e的選手不斷曬出縝密的思路,認識到自己向專業領域要走的路還很長,還需要加油。