我使用Expectimax優化開發了2048 AI ，而不是@ovolve算法使用的minimax搜索。AI會簡單地對所有可能的移動執行最大化，然后對所有可能的圖塊生成進行期望(通過圖塊的概率加權，即4的概率為10％，2的概率為90％)。據我所知，不可能修剪Expectimax優化(除去刪除極不可能的分支)，因此使用的算法是經過仔細優化的蠻力搜索。

性能

AI的默認配置(最大搜索深度為8)從10ms到200ms的任何時間執行移動，具體取決于電路板位置的復雜程度。在測試中，人工智能在整個游戲過程中的平均移動速率為每秒5-10次移動。如果將搜索深度限制為6個動作，則AI可以輕松地每秒執行20個以上的動作，這使您可以進行一些有趣的觀看。

為了評估AI的得分表現，我運行了AI 100次(通過遙控器連接到瀏覽器游戲)。對于每個圖塊，以下是該圖塊至少獲得一次的游戲比例：

2048: 100%

4096: 100%

8192: 100%

16384: 94%

32768: 36%

最低分數為124024；AI的最高得分是794076。中位數是387222。AI從未失敗過獲得2048個圖塊(因此，即使每100場游戲中有一次它也不會輸掉游戲)；實際上，它在每次運行中至少獲得了8192個磁貼！

這是最佳運行的屏幕截圖：

32768瓷磚，得分794076

該游戲在96分鐘內進行了27830次移動，或平均每秒4.8次移動。

實作

我的方法將整個電路板(16個條目)編碼為單個64位整數(其中，圖塊為四位，即4位塊)。在64位計算機上，這使整個電路板可以在單個計算機寄存器中傳遞。

位移操作用于提取單獨的行和列。單個行或列是16位數量，因此大小為65536的表可以編碼對單個行或列進行操作的轉換。例如，將移動作為4個查詢實現到預先計算的“移動效果表”中，該表描述了每個移動如何影響單個行或一列(例如，“向右移動”表包含條目“ 1122-> 0023”，該條目描述了當向右移動時，行[2,2,4,4]變為行[0,0,4,8]。

還可以使用表查找來進行計分。這些表包含在所有可能的行/列上計算的啟發式分數，并且一塊木板的結果分數就是每個行和列中表值的總和。

這種棋盤表示形式以及用于移動和得分的表格查找方法，使AI可以在短時間內搜索大量游戲狀態(在我的2011年中期筆記本電腦的一個核心上每秒可搜索超過10,000,000個游戲狀態)。

Expectimax搜索本身被編碼為遞歸搜索，它在“期望”步驟(測試所有可能的瓦片生成位置和值，并通過每種可能性的概率加權其優化得分)和“最大化”步驟(測試所有可能的移動)之間交替并選擇得分最高的那個)。當樹搜索看到先前看到的位置(使用轉置表)，達到預定義的深度限制或達到極不可能的板狀態(例如，通過獲取6個“ 4”圖塊達到該狀態)時，樹搜索終止從起始位置開始連續排成一行)。典型的搜索深度是4-8步。

啟發式

幾種啟發式方法用于將優化算法引向有利位置。啟發式算法的精確選擇對算法的性能有很大的影響。權衡各種啟發式方法并將其組合到位置分數中，該分數確定給定板位置的“好”程度。然后，優化搜索將旨在使所有可能的董事會職位的平均分數最大化。如游戲所示，實際得分不用于計算棋盤得分，因為它過于權重而無法合并磚塊(延遲合并可能產生巨大收益)。

最初，我使用了兩種非常簡單的啟發式方法，分別為開放正方形和在邊緣具有較大值的對象授予“獎勵”。這些啟發式方法的效果非常好，經常達到16384，但從未達到32768。

PetrMorávek(@xificurk)采用了我的AI，并添加了兩個新的啟發式方法。第一種啟發式方法是對具有非單調的行和列的行列進行懲罰，該行和列隨等級的增加而增加，以確保數量較少的非單調行不會嚴重影響得分，但是數量較大的非單調行將嚴重損害得分。第二種啟發式方法計算了除開放空間之外的潛在合并數(相鄰的相等值)。這兩種啟發式算法將算法推向單調板(更易于合并)，并推向具有大量合并的板位置(鼓勵它在可能的情況下對齊合并以產生更大的效果)。

此外，Petr還使用“元優化”策略(使用稱為CMA-ES的算法)對啟發式權重進行了優化，其中權重本身已進行調整以獲得最高的平均得分。

這些變化的影響極為顯著。該算法從大約13％的時間達到16384瓦片到90％的時間達到了它，并且算法在1/3的時間開始達到32768(而舊的啟發式算法從未產生過32768瓦片) 。

我相信啟發式方法仍有改進的空間。該算法肯定還不是“最優”的，但是我覺得它已經接近了。

人工智能在超過三分之一的游戲中獲得了32768瓦，這是一個巨大的里程碑。聽到有人在正式游戲中獲得32768的成績(即未使用savestates或undo等工具)，我會感到驚訝。我認為65536磁貼觸手可及！

您可以自己嘗試AI。該代碼可從https://github.com/nneonneo/2048-ai獲得。

總結

以上是生活随笔為你收集整理的2048小游戏最佳算法C语言,2048游戏的最佳算法是什么？的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。