熱門游戲2048 - AI程序算法分析
針對目前火爆的2048游戲，有人實現 了一個AI程序，可以以較大概率（高于90%）贏得游戲，并且作者在stackoverflow上簡要介紹了AI的算法框架和實現思路。但是這個回答主要集中在啟發函數的選取上，對AI用到的核心算法并沒有仔細說明。這篇文章將主要分為兩個部分，第一部分介紹其中用到的基礎算法，即Minimax和Alpha-beta剪枝；第二部分分析作者具體的實現。
基礎算法
2048本質上可以抽象成信息對稱雙人對弈模型（玩家向四個方向中的一個移動，然后計算機在某個空格中填入2或4）。這里“信息對稱”是指在任一時刻對弈雙方對格局的信息完全一致，移動策略僅依賴對接下來格局的推理。作者使用的核心算法為對弈模型中常用的帶Alpha-beta剪枝的Minimax。這個算法也常被用于如國際象棋等信息對稱對弈AI中。
Minimax
下面先介紹不帶剪枝的Minimax。首先本文將通過一個簡單的例子說明Minimax算法的思路和決策方式。
問題
現在考慮這樣一個游戲：有三個盤子A、B和C，每個盤子分別放有三張紙幣。A放的是1、20、50；B放的是5、10、100；C放的是1、5、20。單位均為“元”。有甲、乙兩人，兩人均對三個盤子和上面放置的紙幣有可以任意查看。游戲分三步：
-
甲從三個盤子中選取一個。
-
乙從甲選取的盤子中拿出兩張紙幣交給甲。
-
甲從乙所給的兩張紙幣中選取一張，拿走。
其中甲的目標是最后拿到的紙幣面值盡量大，乙的目標是讓甲最后拿到的紙幣面值盡量小。
下面用Minimax算法解決這個問題。
基本思路
一般解決博弈類問題的自然想法是將格局組織成一棵樹，樹的每一個節點表示一種格局，而父子關系表示由父格局經過一步可以到達子格局。Minimax也不例外，它通過對以當前格局為根的格局樹搜索來確定下一步的選擇。而一切格局樹搜索算法的核心都是對每個格局價值的評價。Minimax算法基于以下樸素思想確定格局價值：
-
Minimax是一種悲觀算法，即假設對手每一步都會將我方引入從當前看理論上價值最小的格局方向，即對手具有完美決策能力。因此我方的策略應該是選擇那些對方所能達到的讓我方最差情況中最好的，也就是讓對方在完美決策下所對我造成的損失最小。
-
Minimax不找理論最優解，因為理論最優解往往依賴于對手是否足夠愚蠢，Minimax中我方完全掌握主動，如果對方每一步決策都是完美的，則我方可以達到預計的最小損失格局，如果對方沒有走出完美決策，則我方可能達到比預計的最悲觀情況更好的結局。總之我方就是要在最壞情況中選擇最好的。
上面的表述有些抽象，下面看具體示例。
解題
下圖是上述示例問題的格局樹：
注意，由于示例問題格局數非常少，我們可以給出完整的格局樹。這種情況下我可以找到Minimax算法的全局最優解。而真實情況中，格局樹非常龐大，即使是計算機也不可能給出完整的樹，因此我們往往只搜索一定深度，這時只能找到局部最優解。
我們從甲的角度考慮。其中正方形節點表示輪到我方（甲），而三角形表示輪到對方（乙）。經過三輪對弈后（我方-對方-我方），將進入終局。黃色葉結點表示所有可能的結局。從甲方看，由于最終的收益可以通過紙幣的面值評價，我們自然可以用結局中甲方拿到的紙幣面值表示終格局的價值。
下面考慮倒數第二層節點，在這些節點上，輪到我方選擇，所以我們應該引入可選擇的最大價值格局，因此每個節點的價值為其子節點的最大值：
這些輪到我方的節點叫做max節點，max節點的值是其子節點最大值。
倒數第三層輪到對方選擇，假設對方會盡力將局勢引入讓我方價值最小的格局，因此這些節點的價值取決于子節點的最小值。這些輪到對方的節點叫做min節點。
最后，根節點是max節點，因此價值取決于葉子節點的最大值。最終完整賦值的格局樹如下：
總結一下Minimax算法的步驟：
-
首先確定最大搜索深度D，D可能達到終局，也可能是一個中間格局。
-
在最大深度為D的格局樹葉子節點上，使用預定義的價值評價函數對葉子節點價值進行評價。
-
自底向上為非葉子節點賦值。其中max節點取子節點最大值，min節點取子節點最小值。
-
每次輪到我方時（此時必處在格局樹的某個max節點），選擇價值等于此max節點價值的那個子節點路徑。
在上面的例子中，根節點的價值為20，表示如果對方每一步都完美決策，則我方按照上述算法可最終拿到20元，這是我方在Minimax算法下最好的決策。格局轉換路徑如下圖紅色路徑所示：
對于真實問題中的Minimax，再次強調幾點：
-
真實問題一般無法構造出完整的格局樹，所以需要確定一個最大深度D，每次最多從當前格局向下計算D層。
-
因為上述原因，Minimax一般是尋找一個局部最優解而不是全局最優解，搜索深度越大越可能找到更好的解，但計算耗時會呈指數級膨脹。
-
也是因為無法一次構造出完整的格局樹，所以真實問題中Minimax一般是邊對弈邊計算局部格局樹，而不是只計算一次，但已計算的中間結果可以緩存。
#p#
Alpha-beta剪枝
簡單的Minimax算法有一個很大的問題就是計算復雜性。由于所需搜索的節點數隨最大深度呈指數膨脹，而算法的效果往往和深度相關，因此這極大限制了算法的效果。
Alpha-beta剪枝是對Minimax的補充和改進。采用Alpha-beta剪枝后，我們可不必構造和搜索最大深度D內的所有節點，在構造過程中，如果發現當前格局再往下不能找到更好的解，我們就停止在這個格局及以下的搜索，也就是剪枝。
Alpha-beta基于這樣一種樸素的思想：時時刻刻記得當前已經知道的最好選擇，如果從當前格局搜索下去，不可能找到比已知最優解更好的解，則停止這個格局分支的搜索（剪枝），回溯到父節點繼續搜索。
Alpha-beta算法可以看成變種的Minimax，基本方法是從根節點開始采用深度優先的方式構造格局樹，在構造每個節點時，都會讀取此節點的alpha和beta兩個值，其中alpha表示搜索到當前節點時已知的最好選擇的下界，而beta表示從這個節點往下搜索最壞結局的上界。由于我們假設對手會將局勢引入最壞結局之一，因此當beta小于alpha時，表示從此處開始不論最終結局是哪一個，其上限價值也要低于已知的最優解，也就是說已經不可能此處向下找到更好的解，所以就會剪枝。
下面同樣以上述示例介紹Alpha-beta剪枝算法的工作原理。我們從根節點開始，詳述使用Alpha-beta的每一個步驟：
-
根節點的alpha和beta分別被初始化為
−∞ ，和+∞ 。 -
深度優先搜索第一個孩子，不是葉子節點，所以alpha和beta繼承自父節點，分別為
−∞ ，和+∞ -
搜索第三層的第一個孩子，同上。
-
搜索第四層，到達葉子節點，采用評價函數得到此節點的評價值為1。
-
此葉節點的父節點為max節點，因此更新其alpha值為1，表示此節點取值的下界為1。
-
再看另外一個子節點，值為20，大于當前alpha值，因此將alpha值更新為20。
-
此時第三層最左節點所有子樹搜索完畢，作為max節點，更新其真實值為當前alpha值：20。
-
由于其父節點（第二層最左節點）為min節點，因此更新其父節點beta值為20，表示這個節點取值最多為20。
-
搜索第二層最左節點的第二個孩子及其子樹，按上述邏輯，得到值為50（注意第二層最左節點的beta值要傳遞給孩子）。由于50大于20，不更新min節點的beta值。
-
搜索第二層最左節點的第三個孩子。當看完第一個葉子節點后，發現第三個孩子的alpha=beta，此時表示這個節點下不會再有更好解，于是剪枝。
-
繼續搜索B分支，當搜索完B分支的第一個孩子后，發現此時B分支的alpha為20，beta為10。這表示B分支節點的最大取值不會超過10，而我們已經在A分支取到20，此時滿足alpha大于等于beta的剪枝條件，因此將B剪枝。并將B分支的節點值設為10，注意，這個10不一定是這個節點的真實值，而只是上線，B節點的真實值可能是5，可能是1，可能是任何小于10的值。但是已經無所謂了，反正我們知道這個分支不會好過A分支，因此可以放棄了。
-
在C分支搜索時遇到了與B分支相同的情況。因此講C分支剪枝。
此時搜索全部完畢，而我們也得到了這一步的策略：應該走A分支。
可以看到相比普通Minimax要搜索18個葉子節點相比，這里只搜索了9個。采用Alpha-beta剪枝，可以在相同時間內加大Minimax的搜索深度，因此可以獲得更好的效果。并且Alpha-beta的解和普通Minimax的解是一致的。
#p#
針對2048游戲的實現
下面看一下ov3y同學針對2048實現的AI。程序的github在這里，主要程序都在ai.js中。
建模
上面說過Minimax和Alpha-beta都是針對信息對稱的輪流對弈問題，這里作者是這樣抽象游戲的：
-
我方：游戲玩家。每次可以選擇上、下、左、右四個行棋策略中的一種（某些格局會少于四種，因為有些方向不可走）。行棋后方塊按照既定邏輯移動及合并，格局轉換完成。
-
對方：計算機。在當前任意空格子里放置一個方塊，方塊的數值可以是2或4。放置新方塊后，格局轉換完成。
-
勝利條件：出現某個方塊的數值為“2048”。
-
失敗條件：格子全滿，且無法向四個方向中任何一個方向移動（均不能觸發合并）。
如此2048游戲就被建模成一個信息對稱的雙人對弈問題。
格局評價
作為算法的核心，如何評價當前格局的價值是重中之重。在2048中，除了終局外，中間格局并無非常明顯的價值評價指標，因此需要用一些啟發式的指標來評價格局。那些分數高的“好”格局是容易引向勝利的格局，而分低的“壞”格局是容易引向失敗的格局。
作者采用了如下幾個啟發式指標。
單調性
單調性指方塊從左到右、從上到下均遵從遞增或遞減。一般來說，越單調的格局越好。下面是一個具有良好單調格局的例子：
平滑性
平滑性是指每個方塊與其直接相鄰方塊數值的差，其中差越小越平滑。例如2旁邊是4就比2旁邊是128平滑。一般認為越平滑的格局越好。下面是一個具有極端平滑性的例子：
空格數
這個很好理解，因為一般來說，空格子越少對玩家越不利。所以我們認為空格越多的格局越好。
孤立空格數
這個指標評價空格被分開的程度，空格越分散則格局越差。
具體來說，2048-AI在評價格局時，對這些啟發指標采用了加權策略。具體代碼如下：
- // static evaluation function
- AI.prototype.eval = function() {
- var emptyCells = this.grid.availableCells().length;
- var smoothWeight = 0.1,
- //monoWeight = 0.0,
- //islandWeight = 0.0,
- mono2Weight = 1.0,
- emptyWeight = 2.7,
- maxWeight = 1.0;
- return this.grid.smoothness() * smoothWeight
- //+ this.grid.monotonicity() * monoWeight
- //- this.grid.islands() * islandWeight
- + this.grid.monotonicity2() * mono2Weight
- + Math.log(emptyCells) * emptyWeight
- + this.grid.maxValue() * maxWeight;
- };
有興趣的同學可以調整一下權重看看有什么效果。
對對方選擇的剪枝
在這個程序中，除了采用Alpha-beta剪枝外，在min節點還采用了另一種剪枝，即只考慮對方走出讓格局最差的那一步（而實際2048中計算機的選擇是隨機的），而不是搜索全部對方可能的走法。這是因為對方所有可能的選擇為“空格數×2”，如果全部搜索的話會嚴重限制搜索深度。
相關剪枝代碼如下：
- // try a 2 and 4 in each cell and measure how annoying it is
- // with metrics from eval
- var candidates = [];
- var cells = this.grid.availableCells();
- var scores = { 2: [], 4: [] };
- for (var value in scores) {
- for (var i in cells) {
- scores[value].push(null);
- var cell = cells[i];
- var tile = new Tile(cell, parseInt(value, 10));
- this.grid.insertTile(tile);
- scores[value][i] = -this.grid.smoothness() + this.grid.islands();
- this.grid.removeTile(cell);
- }
- }
- // now just pick out the most annoying moves
- var maxScore = Math.max(Math.max.apply(null, scores[2]), Math.max.apply(null, scores[4]));
- for (var value in scores) { // 2 and 4
- for (var i=0; i<scores[value].length; i++) {
- if (scores[value][i] == maxScore) {
- candidates.push( { position: cells[i], value: parseInt(value, 10) } );
- }
- }
- }
搜索深度
在2048-AI的實現中，并沒有限制搜索的最大深度，而是限制每次“思考”的時間。這里設定了一個超時時間，默認為100ms，在這個時間內，會從1開始，搜索到所能達到的深度。相關代碼：
- // performs iterative deepening over the alpha-beta search
- AI.prototype.iterativeDeep = function() {
- var start = (new Date()).getTime();
- var depth = 0;
- var best;
- do {
- var newBest = this.search(depth, -10000, 10000, 0 ,0);
- if (newBest.move == -1) {
- //console.log('BREAKING EARLY');
- break;
- } else {
- best = newBest;
- }
- depth++;
- } while ( (new Date()).getTime() - start < minSearchTime);
- //console.log('depth', --depth);
- //console.log(this.translate(best.move));
- //console.log(best);
- return best
- }
因此這個算法實現的效果實際上依賴于執行javascript引擎機器的性能。當然可以通過增加超時時間來達到更好的效果，但此時每一步行走速度會相應變慢。
算法的改進
目前這個實現作者聲稱成功合成2048的概率超過90%，但是合成4096甚至8192的概率并不高。作者在github項目的REAMDE中同時給出了一些優化建議，這些建議包括：
- 緩存結果。目前這個實現并沒有對已搜索的樹做緩存，每一步都要重新開始搜索。
- 多線程搜索。由于javascript引擎的單線程特性，這一點很難做到，但如果在其它平臺上也許也可考慮并行技術。
- 更好的啟發函數。也許可以總結出一些更好的啟發函數來評價格局價值。
參考文獻
- 2048 Game
- 2048-AI github
- An Exhaustive Explanation of Minimax, a Staple AI Algorithm
- Tic Tac Toe: Understanding the Minimax Algorithm
- CS 161 Recitation Notes - Minimax with Alpha Beta Pruning
原文鏈接：http://blog.codinglabs.org/articles/2048-ai-analysis.html
【編輯推薦】
