熱門(mén)游戲2048 - AI程序算法分析
針對(duì)目前火爆的2048游戲，有人實(shí)現(xiàn) 了一個(gè)AI程序，可以以較大概率（高于90%）贏得游戲，并且作者在stackoverflow上簡(jiǎn)要介紹了AI的算法框架和實(shí)現(xiàn)思路。但是這個(gè)回答主要集中在啟發(fā)函數(shù)的選取上，對(duì)AI用到的核心算法并沒(méi)有仔細(xì)說(shuō)明。這篇文章將主要分為兩個(gè)部分，第一部分介紹其中用到的基礎(chǔ)算法，即Minimax和Alpha-beta剪枝；第二部分分析作者具體的實(shí)現(xiàn)。
基礎(chǔ)算法
2048本質(zhì)上可以抽象成信息對(duì)稱(chēng)雙人對(duì)弈模型（玩家向四個(gè)方向中的一個(gè)移動(dòng)，然后計(jì)算機(jī)在某個(gè)空格中填入2或4）。這里“信息對(duì)稱(chēng)”是指在任一時(shí)刻對(duì)弈雙方對(duì)格局的信息完全一致，移動(dòng)策略?xún)H依賴(lài)對(duì)接下來(lái)格局的推理。作者使用的核心算法為對(duì)弈模型中常用的帶Alpha-beta剪枝的Minimax。這個(gè)算法也常被用于如國(guó)際象棋等信息對(duì)稱(chēng)對(duì)弈AI中。
Minimax
下面先介紹不帶剪枝的Minimax。首先本文將通過(guò)一個(gè)簡(jiǎn)單的例子說(shuō)明Minimax算法的思路和決策方式。
問(wèn)題
現(xiàn)在考慮這樣一個(gè)游戲：有三個(gè)盤(pán)子A、B和C，每個(gè)盤(pán)子分別放有三張紙幣。A放的是1、20、50；B放的是5、10、100；C放的是1、5、20。單位均為“元”。有甲、乙兩人，兩人均對(duì)三個(gè)盤(pán)子和上面放置的紙幣有可以任意查看。游戲分三步：
-
甲從三個(gè)盤(pán)子中選取一個(gè)。
-
乙從甲選取的盤(pán)子中拿出兩張紙幣交給甲。
-
甲從乙所給的兩張紙幣中選取一張，拿走。
其中甲的目標(biāo)是最后拿到的紙幣面值盡量大，乙的目標(biāo)是讓甲最后拿到的紙幣面值盡量小。
下面用Minimax算法解決這個(gè)問(wèn)題。
基本思路
一般解決博弈類(lèi)問(wèn)題的自然想法是將格局組織成一棵樹(shù)，樹(shù)的每一個(gè)節(jié)點(diǎn)表示一種格局，而父子關(guān)系表示由父格局經(jīng)過(guò)一步可以到達(dá)子格局。Minimax也不例外，它通過(guò)對(duì)以當(dāng)前格局為根的格局樹(shù)搜索來(lái)確定下一步的選擇。而一切格局樹(shù)搜索算法的核心都是對(duì)每個(gè)格局價(jià)值的評(píng)價(jià)。Minimax算法基于以下樸素思想確定格局價(jià)值：
-
Minimax是一種悲觀算法，即假設(shè)對(duì)手每一步都會(huì)將我方引入從當(dāng)前看理論上價(jià)值最小的格局方向，即對(duì)手具有完美決策能力。因此我方的策略應(yīng)該是選擇那些對(duì)方所能達(dá)到的讓我方最差情況中最好的，也就是讓對(duì)方在完美決策下所對(duì)我造成的損失最小。
-
Minimax不找理論最優(yōu)解，因?yàn)槔碚撟顑?yōu)解往往依賴(lài)于對(duì)手是否足夠愚蠢，Minimax中我方完全掌握主動(dòng)，如果對(duì)方每一步?jīng)Q策都是完美的，則我方可以達(dá)到預(yù)計(jì)的最小損失格局，如果對(duì)方?jīng)]有走出完美決策，則我方可能達(dá)到比預(yù)計(jì)的最悲觀情況更好的結(jié)局?？傊曳骄褪且谧顗那闆r中選擇最好的。
上面的表述有些抽象，下面看具體示例。
解題
下圖是上述示例問(wèn)題的格局樹(shù)：
注意，由于示例問(wèn)題格局?jǐn)?shù)非常少，我們可以給出完整的格局樹(shù)。這種情況下我可以找到Minimax算法的全局最優(yōu)解。而真實(shí)情況中，格局樹(shù)非常龐大，即使是計(jì)算機(jī)也不可能給出完整的樹(shù)，因此我們往往只搜索一定深度，這時(shí)只能找到局部最優(yōu)解。
我們從甲的角度考慮。其中正方形節(jié)點(diǎn)表示輪到我方（甲），而三角形表示輪到對(duì)方（乙）。經(jīng)過(guò)三輪對(duì)弈后（我方-對(duì)方-我方），將進(jìn)入終局。黃色葉結(jié)點(diǎn)表示所有可能的結(jié)局。從甲方看，由于最終的收益可以通過(guò)紙幣的面值評(píng)價(jià)，我們自然可以用結(jié)局中甲方拿到的紙幣面值表示終格局的價(jià)值。
下面考慮倒數(shù)第二層節(jié)點(diǎn)，在這些節(jié)點(diǎn)上，輪到我方選擇，所以我們應(yīng)該引入可選擇的最大價(jià)值格局，因此每個(gè)節(jié)點(diǎn)的價(jià)值為其子節(jié)點(diǎn)的最大值：
這些輪到我方的節(jié)點(diǎn)叫做max節(jié)點(diǎn)，max節(jié)點(diǎn)的值是其子節(jié)點(diǎn)最大值。
倒數(shù)第三層輪到對(duì)方選擇，假設(shè)對(duì)方會(huì)盡力將局勢(shì)引入讓我方價(jià)值最小的格局，因此這些節(jié)點(diǎn)的價(jià)值取決于子節(jié)點(diǎn)的最小值。這些輪到對(duì)方的節(jié)點(diǎn)叫做min節(jié)點(diǎn)。
最后，根節(jié)點(diǎn)是max節(jié)點(diǎn)，因此價(jià)值取決于葉子節(jié)點(diǎn)的最大值。最終完整賦值的格局樹(shù)如下：
總結(jié)一下Minimax算法的步驟：
-
首先確定最大搜索深度D，D可能達(dá)到終局，也可能是一個(gè)中間格局。
-
在最大深度為D的格局樹(shù)葉子節(jié)點(diǎn)上，使用預(yù)定義的價(jià)值評(píng)價(jià)函數(shù)對(duì)葉子節(jié)點(diǎn)價(jià)值進(jìn)行評(píng)價(jià)。
-
自底向上為非葉子節(jié)點(diǎn)賦值。其中max節(jié)點(diǎn)取子節(jié)點(diǎn)最大值，min節(jié)點(diǎn)取子節(jié)點(diǎn)最小值。
-
每次輪到我方時(shí)（此時(shí)必處在格局樹(shù)的某個(gè)max節(jié)點(diǎn)），選擇價(jià)值等于此max節(jié)點(diǎn)價(jià)值的那個(gè)子節(jié)點(diǎn)路徑。
在上面的例子中，根節(jié)點(diǎn)的價(jià)值為20，表示如果對(duì)方每一步都完美決策，則我方按照上述算法可最終拿到20元，這是我方在Minimax算法下最好的決策。格局轉(zhuǎn)換路徑如下圖紅色路徑所示：
對(duì)于真實(shí)問(wèn)題中的Minimax，再次強(qiáng)調(diào)幾點(diǎn)：
-
真實(shí)問(wèn)題一般無(wú)法構(gòu)造出完整的格局樹(shù)，所以需要確定一個(gè)最大深度D，每次最多從當(dāng)前格局向下計(jì)算D層。
-
因?yàn)樯鲜鲈?，Minimax一般是尋找一個(gè)局部最優(yōu)解而不是全局最優(yōu)解，搜索深度越大越可能找到更好的解，但計(jì)算耗時(shí)會(huì)呈指數(shù)級(jí)膨脹。
-
也是因?yàn)闊o(wú)法一次構(gòu)造出完整的格局樹(shù)，所以真實(shí)問(wèn)題中Minimax一般是邊對(duì)弈邊計(jì)算局部格局樹(shù)，而不是只計(jì)算一次，但已計(jì)算的中間結(jié)果可以緩存。
#p#
Alpha-beta剪枝
簡(jiǎn)單的Minimax算法有一個(gè)很大的問(wèn)題就是計(jì)算復(fù)雜性。由于所需搜索的節(jié)點(diǎn)數(shù)隨最大深度呈指數(shù)膨脹，而算法的效果往往和深度相關(guān)，因此這極大限制了算法的效果。
Alpha-beta剪枝是對(duì)Minimax的補(bǔ)充和改進(jìn)。采用Alpha-beta剪枝后，我們可不必構(gòu)造和搜索最大深度D內(nèi)的所有節(jié)點(diǎn)，在構(gòu)造過(guò)程中，如果發(fā)現(xiàn)當(dāng)前格局再往下不能找到更好的解，我們就停止在這個(gè)格局及以下的搜索，也就是剪枝。
Alpha-beta基于這樣一種樸素的思想：時(shí)時(shí)刻刻記得當(dāng)前已經(jīng)知道的最好選擇，如果從當(dāng)前格局搜索下去，不可能找到比已知最優(yōu)解更好的解，則停止這個(gè)格局分支的搜索（剪枝），回溯到父節(jié)點(diǎn)繼續(xù)搜索。
Alpha-beta算法可以看成變種的Minimax，基本方法是從根節(jié)點(diǎn)開(kāi)始采用深度優(yōu)先的方式構(gòu)造格局樹(shù)，在構(gòu)造每個(gè)節(jié)點(diǎn)時(shí)，都會(huì)讀取此節(jié)點(diǎn)的alpha和beta兩個(gè)值，其中alpha表示搜索到當(dāng)前節(jié)點(diǎn)時(shí)已知的最好選擇的下界，而beta表示從這個(gè)節(jié)點(diǎn)往下搜索最壞結(jié)局的上界。由于我們假設(shè)對(duì)手會(huì)將局勢(shì)引入最壞結(jié)局之一，因此當(dāng)beta小于alpha時(shí)，表示從此處開(kāi)始不論最終結(jié)局是哪一個(gè)，其上限價(jià)值也要低于已知的最優(yōu)解，也就是說(shuō)已經(jīng)不可能此處向下找到更好的解，所以就會(huì)剪枝。
下面同樣以上述示例介紹Alpha-beta剪枝算法的工作原理。我們從根節(jié)點(diǎn)開(kāi)始，詳述使用Alpha-beta的每一個(gè)步驟：
-
根節(jié)點(diǎn)的alpha和beta分別被初始化為
−∞ ，和+∞ 。 -
深度優(yōu)先搜索第一個(gè)孩子，不是葉子節(jié)點(diǎn)，所以alpha和beta繼承自父節(jié)點(diǎn)，分別為
−∞ ，和+∞ -
搜索第三層的第一個(gè)孩子，同上。
-
搜索第四層，到達(dá)葉子節(jié)點(diǎn)，采用評(píng)價(jià)函數(shù)得到此節(jié)點(diǎn)的評(píng)價(jià)值為1。
-
此葉節(jié)點(diǎn)的父節(jié)點(diǎn)為max節(jié)點(diǎn)，因此更新其alpha值為1，表示此節(jié)點(diǎn)取值的下界為1。
-
再看另外一個(gè)子節(jié)點(diǎn)，值為20，大于當(dāng)前alpha值，因此將alpha值更新為20。
-
此時(shí)第三層最左節(jié)點(diǎn)所有子樹(shù)搜索完畢，作為max節(jié)點(diǎn)，更新其真實(shí)值為當(dāng)前alpha值：20。
-
由于其父節(jié)點(diǎn)（第二層最左節(jié)點(diǎn)）為min節(jié)點(diǎn)，因此更新其父節(jié)點(diǎn)beta值為20，表示這個(gè)節(jié)點(diǎn)取值最多為20。
-
搜索第二層最左節(jié)點(diǎn)的第二個(gè)孩子及其子樹(shù)，按上述邏輯，得到值為50（注意第二層最左節(jié)點(diǎn)的beta值要傳遞給孩子）。由于50大于20，不更新min節(jié)點(diǎn)的beta值。
-
搜索第二層最左節(jié)點(diǎn)的第三個(gè)孩子。當(dāng)看完第一個(gè)葉子節(jié)點(diǎn)后，發(fā)現(xiàn)第三個(gè)孩子的alpha=beta，此時(shí)表示這個(gè)節(jié)點(diǎn)下不會(huì)再有更好解，于是剪枝。
-
繼續(xù)搜索B分支，當(dāng)搜索完B分支的第一個(gè)孩子后，發(fā)現(xiàn)此時(shí)B分支的alpha為20，beta為10。這表示B分支節(jié)點(diǎn)的最大取值不會(huì)超過(guò)10，而我們已經(jīng)在A分支取到20，此時(shí)滿(mǎn)足alpha大于等于beta的剪枝條件，因此將B剪枝。并將B分支的節(jié)點(diǎn)值設(shè)為10，注意，這個(gè)10不一定是這個(gè)節(jié)點(diǎn)的真實(shí)值，而只是上線，B節(jié)點(diǎn)的真實(shí)值可能是5，可能是1，可能是任何小于10的值。但是已經(jīng)無(wú)所謂了，反正我們知道這個(gè)分支不會(huì)好過(guò)A分支，因此可以放棄了。
-
在C分支搜索時(shí)遇到了與B分支相同的情況。因此講C分支剪枝。
此時(shí)搜索全部完畢，而我們也得到了這一步的策略：應(yīng)該走A分支。
可以看到相比普通Minimax要搜索18個(gè)葉子節(jié)點(diǎn)相比，這里只搜索了9個(gè)。采用Alpha-beta剪枝，可以在相同時(shí)間內(nèi)加大Minimax的搜索深度，因此可以獲得更好的效果。并且Alpha-beta的解和普通Minimax的解是一致的。
#p#
針對(duì)2048游戲的實(shí)現(xiàn)
下面看一下ov3y同學(xué)針對(duì)2048實(shí)現(xiàn)的AI。程序的github在這里，主要程序都在ai.js中。
建模
上面說(shuō)過(guò)Minimax和Alpha-beta都是針對(duì)信息對(duì)稱(chēng)的輪流對(duì)弈問(wèn)題，這里作者是這樣抽象游戲的：
-
我方：游戲玩家。每次可以選擇上、下、左、右四個(gè)行棋策略中的一種（某些格局會(huì)少于四種，因?yàn)橛行┓较虿豢勺撸?。行棋后方塊按照既定邏輯移動(dòng)及合并，格局轉(zhuǎn)換完成。
-
對(duì)方：計(jì)算機(jī)。在當(dāng)前任意空格子里放置一個(gè)方塊，方塊的數(shù)值可以是2或4。放置新方塊后，格局轉(zhuǎn)換完成。
-
勝利條件：出現(xiàn)某個(gè)方塊的數(shù)值為“2048”。
-
失敗條件：格子全滿(mǎn)，且無(wú)法向四個(gè)方向中任何一個(gè)方向移動(dòng)（均不能觸發(fā)合并）。
如此2048游戲就被建模成一個(gè)信息對(duì)稱(chēng)的雙人對(duì)弈問(wèn)題。
格局評(píng)價(jià)
作為算法的核心，如何評(píng)價(jià)當(dāng)前格局的價(jià)值是重中之重。在2048中，除了終局外，中間格局并無(wú)非常明顯的價(jià)值評(píng)價(jià)指標(biāo)，因此需要用一些啟發(fā)式的指標(biāo)來(lái)評(píng)價(jià)格局。那些分?jǐn)?shù)高的“好”格局是容易引向勝利的格局，而分低的“壞”格局是容易引向失敗的格局。
作者采用了如下幾個(gè)啟發(fā)式指標(biāo)。
單調(diào)性
單調(diào)性指方塊從左到右、從上到下均遵從遞增或遞減。一般來(lái)說(shuō)，越單調(diào)的格局越好。下面是一個(gè)具有良好單調(diào)格局的例子：
平滑性
平滑性是指每個(gè)方塊與其直接相鄰方塊數(shù)值的差，其中差越小越平滑。例如2旁邊是4就比2旁邊是128平滑。一般認(rèn)為越平滑的格局越好。下面是一個(gè)具有極端平滑性的例子：
空格數(shù)
這個(gè)很好理解，因?yàn)橐话銇?lái)說(shuō)，空格子越少對(duì)玩家越不利。所以我們認(rèn)為空格越多的格局越好。
孤立空格數(shù)
這個(gè)指標(biāo)評(píng)價(jià)空格被分開(kāi)的程度，空格越分散則格局越差。
具體來(lái)說(shuō)，2048-AI在評(píng)價(jià)格局時(shí)，對(duì)這些啟發(fā)指標(biāo)采用了加權(quán)策略。具體代碼如下：
- // 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;
- };
有興趣的同學(xué)可以調(diào)整一下權(quán)重看看有什么效果。
對(duì)對(duì)方選擇的剪枝
在這個(gè)程序中，除了采用Alpha-beta剪枝外，在min節(jié)點(diǎn)還采用了另一種剪枝，即只考慮對(duì)方走出讓格局最差的那一步（而實(shí)際2048中計(jì)算機(jī)的選擇是隨機(jī)的），而不是搜索全部對(duì)方可能的走法。這是因?yàn)閷?duì)方所有可能的選擇為“空格數(shù)×2”，如果全部搜索的話會(huì)嚴(yán)重限制搜索深度。
相關(guān)剪枝代碼如下：
- // 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的實(shí)現(xiàn)中，并沒(méi)有限制搜索的最大深度，而是限制每次“思考”的時(shí)間。這里設(shè)定了一個(gè)超時(shí)時(shí)間，默認(rèn)為100ms，在這個(gè)時(shí)間內(nèi)，會(huì)從1開(kāi)始，搜索到所能達(dá)到的深度。相關(guān)代碼：
- // 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
- }
因此這個(gè)算法實(shí)現(xiàn)的效果實(shí)際上依賴(lài)于執(zhí)行javascript引擎機(jī)器的性能。當(dāng)然可以通過(guò)增加超時(shí)時(shí)間來(lái)達(dá)到更好的效果，但此時(shí)每一步行走速度會(huì)相應(yīng)變慢。
算法的改進(jìn)
目前這個(gè)實(shí)現(xiàn)作者聲稱(chēng)成功合成2048的概率超過(guò)90%，但是合成4096甚至8192的概率并不高。作者在github項(xiàng)目的REAMDE中同時(shí)給出了一些優(yōu)化建議，這些建議包括：
- 緩存結(jié)果。目前這個(gè)實(shí)現(xiàn)并沒(méi)有對(duì)已搜索的樹(shù)做緩存，每一步都要重新開(kāi)始搜索。
- 多線程搜索。由于javascript引擎的單線程特性，這一點(diǎn)很難做到，但如果在其它平臺(tái)上也許也可考慮并行技術(shù)。
- 更好的啟發(fā)函數(shù)。也許可以總結(jié)出一些更好的啟發(fā)函數(shù)來(lái)評(píng)價(jià)格局價(jià)值。
參考文獻(xiàn)
- 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
【編輯推薦】
