1.簡介
很多人都玩過2048，我就比較老套，因為我一向看不上這類單機游戲，但是就在某一天泡腳的無聊時光，拿了媳婦兒的手機，左看看右點點，莫名打開了2048，嗯... 這真是一款打發無聊時光的 "good game"，通過滑動來使得每行或每列相鄰并且相同的數字相加而得到一個最大的數字，最后的數字越大，得分越高！于是，我在想，是否能像魔方一樣，有一定的套路來幫助我們決定每一步該往哪個方向滑動最佳，以便獲得最好的成績呢？
2.如何玩2048
2048是在4×4方格中玩的游戲，方格的每個位置都可能是空的，也可能是一個帶有數字的方塊，
開始游戲時，方格上會在隨機位置產生兩個方塊，數字為“ 2”或“ 4”，每個方塊都有10％的幾率是“ 4”，否則為“2”，
通過將所有方塊向某個方向（上，下，左或右）移動來進行游戲，這樣做時，彼此相鄰且一起移動的具有相同值的所有方塊將合并成一個新的方塊，該方塊的值等于前兩個方塊的和：
進行滑動后，將在隨機位置產生一個新的方塊，新方塊有 90% 的幾率為 ”2“, 10% 的幾率是 ”4“，
然后，繼續進行游戲，直到方格中不再有能移動的方塊為止，
按理來說，這游戲的目標是達到一個值為“ 2048”的方塊就結束了，但是，we never stop，我們可以繼續進行游戲，來爭取更大的勝利，理論上，方塊最大值為 “ 131072” ，
3.問題說明
想要解決這個游戲，是個灰常因缺斯汀的問題，因為我們不僅要正確預測每個新方塊產生的位置，而且還要正確地預測它是“ 2”還是“ 4”，這是隨機事件，理論上每一次都預測正確是不可能的，
因此，不可能有一種演算法每次都能輕松而正確解決難題，我們能盡可能做到的玩好這個概率游戲，確定每個步驟的最佳操作，
不管什么時候，我們只能采取四種行為，然后面臨的挑戰是確定這四項舉措中哪一項將取得最佳的長期效果，
我們的演算法基于 [Expectimax] 演算法，它本身是 [Minimax] 演算法的一種變體，但是樹的路由會根據它們發生的可能性進行加權，
從本質上講，我們將游戲視為兩人游戲：
- 玩家一（人類玩家）可以向四個方向的某個方向移動方塊，
- 玩家二（計算機玩家）可以將方塊放置在方格的任一空白位置，
基于此，我們可以根據每個動作發生的概率對每個動作生成結果樹，然后，這可以為我們提供確定哪種人員舉動可能給出最佳結果所需的詳細資訊，
3.1. 游戲流程圖
游戲玩法的一般流程： 
我們可以在“添加隨機方塊”程序中看到游戲的隨機性——既要找到隨機的正方形來添加方塊，又要為方塊選擇一個隨機值，
然后，我們面臨的挑戰是在“確定下一步行動”步驟中確定要做什么，這是我們玩游戲的演算法，
總體上看似看似簡單：
我們需要做的是模擬每一種可能，確定哪個滑動給出最佳結果，然后使用它，
因此，我們現在將演算法簡化為模擬任何給定的移動并為結果生成分數，
這是一個分為兩部分的程序，第一步是看是否可以移動，如果不能移動，則以“ 0”的分數提前中止，如果可以移動，那么我們將繼續進行真正的演算法，在該演算法中確定移動的效果如何：
3.2 確定下一步行動
到目前為止，演算法的主要部分是模擬滑動，然而關鍵的問題是：如何為每個可能的移動進行評分，這下就是 Expectimax 演算法發揮作用的時候了！
我將模擬兩個玩家的所有可能動作，并進行幾個步驟，然后看看其中哪個能帶來最佳結果，
對于人類玩家而言，只有“上”，“下”，“左”和“右”的這四個動作， 對于計算機則是，將“ 2”或“ 4” 方塊隨機放置在空白的位置：
該演算法是遞回的，每個遞回步驟只有在距離真實游戲中的實際移動有一定深度時才會停止，這樣導致流程圖會回圈回傳自身，但實際上我們將這么做：
- 1.如果處于極限深度則停止，為當前模擬的方格計算分數，
- 2.計算機模擬所有可能的移動：模擬任何可能的人類玩家移動，回傳人的移動，并計算出的分數，
- 3.對模擬移動計算出的分數相加，然后對該移動發生的可能性進行加權，
完成此操作后，我們將所有計算出的分數相加，這就是我們要從當前游戲板上進行的移動的最終分數，因為我們執行了四次操作（從當前游戲界面開始，每個可能的動作都獲得一個），所以我們最終得到了四個分數，其中得分最高的就是應該做出的動作，
3.3. 計分
此時，剩下要做的就是計算方格的分數，但還需要考慮，如何從這個位置繼續得分，
通過添加幾個因素以及適當的權重，可以實作很多方法，例如：
- 空方塊數
- 可能合并的次數——即，兩個相鄰位置中相同數字的次數
- 每個方塊上的最大值
- 所有方塊的總和
- 方格的單一性——確定方格的結構好壞，使得方塊的值在一個方向上增加，
4.偽代碼
現在我們知道了演算法的作業原理，接下來探索一些詳細描述演算法的偽代碼，
我對游戲的實際玩法并不感冒，只對確定移動的演算法有點興趣，所以從這里開始：
現在到了這樣的步驟：從第一個方塊開始，模擬每一個可能的動作，并回傳得分最好的那一個，因此我們需要為新模擬的方格生成分數，
因為使用的是遞回演算法，所以我增加了一個深度限制，用來停止，否則可能會無止境運行下去， 
這又是一個遞回，模擬了每個人移動一定數量的步驟，并確定哪些移動可以拿到最佳的結果，
剩下的唯一事情就是為移動后得到的每個方格，計算出最終分數，當然，這也沒有十全十美的演算法，不同的因素會造成不同的結果，
5.性能優化
到目前為止，我們已經有了一種演算法來嘗試解決游戲問題，但是它效率不高，由于程序的特性，總是會有一定程度的重復，
我們已經在上面的演算法中做了一些優化，不處理對游戲沒有任何影響的移動，但是，我們還有其他方法可以減少作業量，例如跟蹤移動的累積概率，以及在移動的概率太低時停止，
我們還可以動態確定深度次數的限制，上面的偽代碼的硬編碼限制為3，但我們可以在計算開始時根據方格的形狀動態計算該限制，
此外，由于可以多次重新訪問同一方格的位置，因此我們可以記住這些位置并快取這些位置的分數，而不必每次都重新計算它們，潛在地，我們可以提前生成每個方塊可能的位置，但是最多有2048個方塊，281,474,976,710,656個可能的位置，因此這可能不可行，
但是，我們可以做的最重要的優化是調整生成方格分數的演算法，計分的因素和權重與我們的演算法發揮得如何直接相關，
六，結論
2048是一款非常有趣的游戲，可以嘗試破解，雖然沒有完美的方法，但是我們可以用一些啟發式的方法，來探索游戲的最佳路徑，
這類原則同樣適用其他型別的兩人游戲（例如國際象棋），在這種游戲中，無法準確預測別人會做什么，
思考一下，棋牌類游戲電腦托管代打的策略是什么呢？在評論區留下你的答案吧！
如果你覺得文章還不錯，記得關注公眾號： 鍋外的大佬 劉一手的博客
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/227172.html
標籤：AI