高中二年級下學期自主學習作品[經典遊戲破解 - 適者生存解俄羅斯方塊]
經典遊戲破解-適者生存解俄羅斯方塊
作者：朱沿道
高二下自主學習作品
動機
用Unity做完一個遊戲，雖然感到很驕傲，但頓時失去了目標。國中二年級時，為了發洩被家長限制遊戲時間的不悅，決定奮發圖強。既然我不能玩別人的遊戲，那我自己做出來的遊戲你就拿我沒辦法了吧。因為這個原因，我學習程式設計，到了現在。
那時的我認為這個目標我會花一段時間才能完成，但沒想到在高二上就完成了。我了解到我需要一個更遠大的目標，來提供我學習程式的動力。這時突然爆發COVID-19，許多人的性命在短短的一年被取走了。現在科技這麼進步，為何還是阻止不了傳染病的擴散？在反思的過程，發覺到活著的意義：相較於做遊戲，努力地迎合玩家，無止盡的跟隨大眾喜好，不如提升人們生活品質，藉由科技改變環境，即使離開了人世，我的努力還是會繼續留在人世，成為未來人的階梯。數學已發展了許多世紀，幫助人們在研究領域度過重重困難。電腦是一個強大的數學工具，突破了人們對於計算的想像，將會是人類進步的另一利器。因此，我希望可以學習大數據與機器學習，將來可以充分地利用此工具，回饋給人們的生活。
人生的志向已經立定了，還是得要有一個短期目標朝向志向前進。這時，我回想起一年級下學期在社團製作的專案。那時的我對破解遊戲感到興趣，並且立刻數學課所學之期望值應用在此，還參加了小論文競賽，並且獲得了佳作。竟然此舉動受到了不錯的成效，那此時為何不要破解一個關於機器學習的遊戲？
目標
完成一個可以自動遊玩線上俄羅斯方塊的程式。
專案說明
什麼是俄羅斯方塊
俄羅斯方塊是一個益智型電腦遊戲，每一刻都會有俄羅斯方塊從版面上方掉落，可藉由鍵盤控制俄羅斯方塊左右移動與旋轉，當一列被塞滿俄羅斯方塊時，該列會消失，上面所有列向下移一格，目標為不讓堆積的俄羅斯方塊超過最上面的界線，當俄羅斯方塊超過上面界線時，遊戲結束。
確定輸入
在此使用IPO模型，先了解輸入的資料，接著確定輸出的格式，最後再根據輸入與輸出思考處理資料的方法。在此主要有三個欲知的資料，一是現在版面的狀況，接著是正在落下的俄羅斯方塊種類，下一個落下的俄羅斯方塊也是重要的資料。
首先，因為是線上俄羅斯方塊，唯一偵測這些資料的方法就是讀取螢幕某特定位置的顏色。至於這種方法需要先知道偵測的位置，非常麻煩，因此盡量能避免就避免。現在版面的狀況可以在放置時，將放置動作造成的變化記錄起來，正在落下的俄羅斯方塊種類可以從上一次放置前的下一個俄羅斯方塊的種類得知，至於第一個俄羅斯方塊可以獨立偵測。因此，只有下一個落下的俄羅斯方塊使用讀取顏色來辨認。
因為以顏色偵測種類，遊戲的俄羅斯方塊每種都能對到一個顏色，而且俄羅斯方塊本身不能太花俏，影響偵測。下面是我找到符合上述條件遊戲。
▲圖一：Tetris N-Blox 示意圖(圖片來源：螢幕截圖)
確定輸出
玩家在遊玩此遊戲時，會根據現在的版面狀況，與現在正掉落的方塊，藉由鍵盤控制正掉落的方塊，放置在可以阻止俄羅斯方塊不超過上方界線的位置。因此，輸出為操作鍵盤控制落下中的俄羅斯方塊。
以上偵測顏色，螢幕位置，控制鍵盤可使用Python pyautogui插件完成。
確定處理方式
俄羅斯方塊的位置是被限制的，因此，可以找到所有放置的方式，並在這些方式中找到最好的放置方式。至於要如何從這些放置方式找出最好的，可以為每個方式評分，而分數最高者即是最好的放置方式。
在此專案中以三個面向作為評分的標準：放置後高度，放置後產生的陰影格數，與放置後得到的分數。放置後的高度為依此方式放置的俄羅斯方塊，由最下行為0往上數，其最高的方塊之高度。下面I字型的俄羅斯方塊其放置後的高度為7。
▲圖二：放置高度示意圖(資料來源：螢幕截圖)
放置後產生的陰影格數，是指俄羅斯方塊放置後，被此方塊遮擋的空格數量。以下面例子為例，紫色J型俄羅斯方塊之放置後產生的陰影格數為14。
▲圖三：放置後產生的陰影格數示意圖(資料來源：螢幕截圖)
最後的面向是放置後得到的分數，當填滿一列方塊時，在列消失之際，也會獲得分數，值得注意的是，一次填滿的列數越多，獲得的分數也越多。一列到四列所獲得的分數比為1:3:5:8。(在此不考慮特殊得分方式)。
放置後高度、放置後產生的陰影格數這兩個面向是對未來版面不利的，放置後得到的分數則是有利的。因此，最終分數的計算方式：
值得注意的是放置後得到的分數，為了避免分數權重過小，放置後得到的分數並非真正獲得的分數，而是以一次填滿一列時為1時的比值。因此，填滿兩列時為3，三列時為5，四列則是8
最終分數是由三個值所加總起來，每個值是由三個數相乘而來，分別是上是三個面向之一、相對應的權重、與好壞係數。權重大小影響其相對應的面向影響最終分數的程度，權重越大，越能影響最終分數。好壞係數只能為1或是-1，描述此面向對最終分數為正面還是負面。當好壞係數為1，代表此面向對最終分數是正向的，反之當好壞係數是-1時為負向。
權重的大小，是需要在開始程式前去輸入的。權重的大小會影響運算出來最佳放置方式的優劣。尋找最佳權重的方法，為本次的主題：機器學習。
基因演算法
為了更方便的了解下文，我們換個角度思考。上文所做出來的程式，叫做模擬器。藉由輸入模擬器的參數，在這是三個權重，就可以將參數背後的意義以玩俄羅斯方塊的方式表現出來。也就是說，每組參數，就是實驗個體，唯有透過模擬器才能表現出其個體的行為。
生物的演化過程，可以參考達爾文的適者生存法則。首先，生物要有多樣性，接著生物的數量要超過環境負荷，在此情況下，生物會相互競爭，最後最能適應的生物們存活，存活下來的個體生下後代，重複此循環。我們可以藉由此方法找到最適合玩俄羅斯方塊的個體：在尋找最佳個體的程式中，先製造出許多不一樣的個體，並建置一個比賽，個體們藉由模擬器玩俄羅斯方塊與其他個體競爭，唯有最好的個體們可以繁衍後代。重複幾代，就可以得到最佳的個體，也就是最佳的三個權重。
以下是得到最佳權重組的流程圖：
▲圖四：得到最佳權重組的流程圖(資歷來源：作者自製)
有了最佳權重組，就可以藉由模擬器，破解線上的俄羅斯方塊。
製作歷程
我曾經上網查詢提升程式能力的方法，主要有兩點：一是做專案，做專案的過程可以學到不只是寫程式的技巧，也可以進一步的體會思考與除錯的過程。二是將寫專案的過程所遇到的種種困難與體悟到的事放在部落格上，這步驟可以加深印象，並且可以確認是不是真的會，也可以訓練表達能力。我是抱持著這個想法做這個專案的，此學習歷程檔案的內容也同步放在我的部落格裡。
解法
這專案的解法是來自於Youtuber Code bullet 的 “I made a Tetris AI” 影片，此影片有稍微提到解法的大概，因此我是在腦中只有核心概念時下製作。
多執行序
在這專案中，我最印象深刻的是多執行序。當出版完成後，有一個重大的問題。因為個體在每一次放置俄羅斯方塊時，都需要把全部的放置方式都想一遍，包含放置後的分數變化、陰影變化與高度，因此需要限制每場比賽個體可以放置俄羅斯方塊的數量，但此數量如果太少，可以無法準確的知道個體的好壞。實驗得知約在50到100步效果最好，再加上每一場比賽都是約100個個體下去比賽，導致訓練過程的計算量非常的龐大，訓練的時間非常的久。為了解決此問題，我使用多執行序，使同一時間可以有多個個體在使用模擬器，效率提升了不少。
為了得到解答，我學習了搜尋資料的能力。Python裡可以藉由匯入模組添加多執行序的功能，比許多程式語言簡單許多，但因為可能多執行序比較冷門，中文資料不多，API也只有英文版的。因此，從無到有消耗了許多精力。
毅力與耐力
此程式的初稿是在畢業旅行完成了。因為家長意見，同學在畢業旅行時，我在學校自習。在這段時間，我克服了對同學畢業旅行的羨慕，在準備課業之際，用平板電腦在離線的狀態下完成了作品的初稿。
獨具特色的模仿
讓其他人了解我的作品是很重要的。能讓他人了解不只是對作品的肯定，也是自我檢核程式能力的一大方法。在此，我製作了一個用唱的程式使用指南，讓觀眾不會感到無趣。不但是歷史還是迷因，都可以用唱的表達了，那為何我親自撰寫的程式之使用說明不行呢？
心得與未來之路
這是我第一個關於機器學習的專案，也是第二個經典遊戲破解之作。在撰寫過程中，我並沒有對機器學習有嚴重的排斥，很享受那一步步達成小目標，最後完成大目標的感覺。為了提升速度，多執行續讓我吃了許多。不論是思考過程與跳出的除錯訊息都不熟悉，有種重頭再來之感。雖然辛苦，但宛如吃苦瓜，苦中有甘，換來了寶貴的知識與經驗。同時也讓我了解為何YouTube Coding Music 的畫面有張 “Keep calm, ask
stack overflow.” 海報貼在牆壁上。以上這些跡象，是否代表我適合讀資工，我想應多加摸索一番，踢踢鐵板，看看是否對程式有厭惡之感，不然上了大學，每天都要忍受自己所不悅的，挺難受的。
值得一提的是，雖然我使用多執行續，但速度還是以天作為單位，我認為問題出在Python的串列格式。串列可以放各種型態的資料，處理起來也十分方便，但速度不快。在尋找俄羅斯方塊資料時，我發現到Python程式設計師在資料處理時很常使用Pandas與 NumPy，大師們使用此模組一定對資料處理有可處，推測這可能是速度變快的原因。下一步小目標就是學習這兩套模組，並找個遊戲繼續挑戰破解！
作品實體
https://github.com/DCtime/DCtime_TetrisBot
留言
張貼留言