小男孩‘自慰网亚洲一区二区,亚洲一级在线播放毛片,亚洲中文字幕av每天更新,黄aⅴ永久免费无码,91成人午夜在线精品,色网站免费在线观看,亚洲欧洲wwwww在线观看

搜索
分享

熱門游戲2048

 pphsy 2015-06-19

針對(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ì)稱雙人對(duì)弈模型（玩家向四個(gè)方向中的一個(gè)移動(dòng)，然后計(jì)算機(jī)在某個(gè)空格中填入2或4）。這里“信息對(duì)稱”是指在任一時(shí)刻對(duì)弈雙方對(duì)格局的信息完全一致，移動(dòng)策略僅依賴對(duì)接下來(lái)格局的推理。作者使用的核心算法為對(duì)弈模型中常用的帶Alpha-beta剪枝的Minimax。這個(gè)算法也常被用于如國(guó)際象棋等信息對(duì)稱對(duì)弈AI中。

Minimax

下面先介紹不帶剪枝的Minimax。首先本文將通過(guò)一個(gè)簡(jiǎn)單的例子說(shuō)明Minimax算法的思路和決策方式。

問(wèn)題

現(xiàn)在考慮這樣一個(gè)游戲：有三個(gè)盤子A、B和C，每個(gè)盤子分別放有三張紙幣。A放的是1、20、50；B放的是5、10、100；C放的是1、5、20。單位均為“元”。有甲、乙兩人，兩人均對(duì)三個(gè)盤子和上面放置的紙幣有可以任意查看。游戲分三步：

  1. 甲從三個(gè)盤子中選取一個(gè)。

  2. 乙從甲選取的盤子中拿出兩張紙幣交給甲。

  3. 甲從乙所給的兩張紙幣中選取一張，拿走。

其中甲的目標(biāo)是最后拿到的紙幣面值盡量大，乙的目標(biāo)是讓甲最后拿到的紙幣面值盡量小。

下面用Minimax算法解決這個(gè)問(wèn)題。

基本思路

一般解決博弈類問(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)解往往依賴于對(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算法的步驟：

  1. 首先確定最大搜索深度D，D可能達(dá)到終局，也可能是一個(gè)中間格局。

  2. 在最大深度為D的格局樹(shù)葉子節(jié)點(diǎn)上，使用預(yù)定義的價(jià)值評(píng)價(jià)函數(shù)對(duì)葉子節(jié)點(diǎn)價(jià)值進(jìn)行評(píng)價(jià)。

  3. 自底向上為非葉子節(jié)點(diǎn)賦值。其中max節(jié)點(diǎn)取子節(jié)點(diǎn)最大值，min節(jié)點(diǎn)取子節(jié)點(diǎn)最小值。

  4. 每次輪到我方時(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é)果可以緩存。

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è)步驟：

  1. 根節(jié)點(diǎn)的alpha和beta分別被初始化為?∞，和+∞。

  2. 深度優(yōu)先搜索第一個(gè)孩子，不是葉子節(jié)點(diǎn)，所以alpha和beta繼承自父節(jié)點(diǎn)，分別為?∞，和+∞

  3. 搜索第三層的第一個(gè)孩子，同上。

  4. 搜索第四層，到達(dá)葉子節(jié)點(diǎn)，采用評(píng)價(jià)函數(shù)得到此節(jié)點(diǎn)的評(píng)價(jià)值為1。

  5. 此葉節(jié)點(diǎn)的父節(jié)點(diǎn)為max節(jié)點(diǎn)，因此更新其alpha值為1，表示此節(jié)點(diǎn)取值的下界為1。

  6. 再看另外一個(gè)子節(jié)點(diǎn)，值為20，大于當(dāng)前alpha值，因此將alpha值更新為20。

  7. 此時(shí)第三層最左節(jié)點(diǎn)所有子樹(shù)搜索完畢，作為max節(jié)點(diǎn)，更新其真實(shí)值為當(dāng)前alpha值：20。

  8. 由于其父節(jié)點(diǎn)（第二層最左節(jié)點(diǎn)）為min節(jié)點(diǎn)，因此更新其父節(jié)點(diǎn)beta值為20，表示這個(gè)節(jié)點(diǎn)取值最多為20。

  9. 搜索第二層最左節(jié)點(diǎn)的第二個(gè)孩子及其子樹(shù)，按上述邏輯，得到值為50（注意第二層最左節(jié)點(diǎn)的beta值要傳遞給孩子）。由于50大于20，不更新min節(jié)點(diǎn)的beta值。

  10. 搜索第二層最左節(jié)點(diǎn)的第三個(gè)孩子。當(dāng)看完第一個(gè)葉子節(jié)點(diǎn)后，發(fā)現(xiàn)第三個(gè)孩子的alpha=beta，此時(shí)表示這個(gè)節(jié)點(diǎn)下不會(huì)再有更好解，于是剪枝。

  11. 繼續(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í)滿足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分支，因此可以放棄了。

  12. 在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的解是一致的。

針對(duì)2048游戲的實(shí)現(xiàn)

下面看一下ov3y同學(xué)針對(duì)2048實(shí)現(xiàn)的AI。程序的github在這里，主要程序都在ai.js中。

建模

上面說(shuō)過(guò)Minimax和Alpha-beta都是針對(duì)信息對(duì)稱的輪流對(duì)弈問(wèn)題，這里作者是這樣抽象游戲的：

  • 我方：游戲玩家。每次可以選擇上、下、左、右四個(gè)行棋策略中的一種（某些格局會(huì)少于四種，因?yàn)橛行┓较虿豢勺撸Ｐ衅搴蠓綁K按照既定邏輯移動(dòng)及合并，格局轉(zhuǎn)換完成。

  • 對(duì)方：計(jì)算機(jī)。在當(dāng)前任意空格子里放置一個(gè)方塊，方塊的數(shù)值可以是2或4。放置新方塊后，格局轉(zhuǎn)換完成。

  • 勝利條件：出現(xiàn)某個(gè)方塊的數(shù)值為“2048”。

  • 失敗條件：格子全滿，且無(wú)法向四個(gè)方向中任何一個(gè)方向移動(dòng)（均不能觸發(fā)合并）。

如此2048游戲就被建模成一個(gè)信息對(duì)稱的雙人對(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)策略。具體代碼如下：

  1. // static evaluation function  
  2. AI.prototype.eval = function() {  
  3.     var emptyCells = this.grid.availableCells().length;  
  4.    
  5.     var smoothWeight = 0.1,  
  6.         //monoWeight   = 0.0,  
  7.         //islandWeight = 0.0,  
  8.         mono2Weight  = 1.0,  
  9.         emptyWeight  = 2.7,  
  10.         maxWeight    = 1.0;  
  11.    
  12.     return this.grid.smoothness() * smoothWeight  
  13.         //+ this.grid.monotonicity() * monoWeight  
  14.         //- this.grid.islands() * islandWeight  
  15.         + this.grid.monotonicity2() * mono2Weight  
  16.         + Math.log(emptyCells) * emptyWeight  
  17.         + this.grid.maxValue() * maxWeight;  
  18. }; 

有興趣的同學(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)剪枝代碼如下：

  1. // try a 2 and 4 in each cell and measure how annoying it is  
  2. // with metrics from eval  
  3. var candidates = [];  
  4. var cells = this.grid.availableCells();  
  5. var scores = { 2: [], 4: [] };  
  6. for (var value in scores) {  
  7.     for (var i in cells) {  
  8.         scores[value].push(null);  
  9.         var cell = cells[i];  
  10.         var tile = new Tile(cell, parseInt(value, 10));  
  11.         this.grid.insertTile(tile);  
  12.         scores[value][i] = -this.grid.smoothness() + this.grid.islands();  
  13.         this.grid.removeTile(cell);  
  14.     }  
  15. }  
  16.    
  17. // now just pick out the most annoying moves  
  18. var maxScore = Math.max(Math.max.apply(null, scores[2]), Math.max.apply(null, scores[4]));  
  19. for (var value in scores) { // 2 and 4  
  20.     for (var i=0; i<scores[value].length; i++) {  
  21.         if (scores[value][i] == maxScore) {  
  22.             candidates.push( { position: cells[i], value: parseInt(value, 10) } );  
  23.         }  
  24.     }  
  25. } 

搜索深度

在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)代碼：

  1. // performs iterative deepening over the alpha-beta search  
  2. AI.prototype.iterativeDeep = function() {  
  3.     var start = (new Date()).getTime();  
  4.     var depth = 0;  
  5.     var best;  
  6.     do {  
  7.         var newBest = this.search(depth, -10000, 10000, 0 ,0);  
  8.         if (newBest.move == -1) {  
  9.             //console.log('BREAKING EARLY');  
  10.             break;  
  11.         } else {  
  12.             best = newBest;  
  13.         }  
  14.         depth++;  
  15.     } while ( (new Date()).getTime() - start < minSearchTime);  
  16.     //console.log('depth', --depth);  
  17.     //console.log(this.translate(best.move));  
  18.     //console.log(best);  
  19.     return best  
  20. } 

因此這個(gè)算法實(shí)現(xiàn)的效果實(shí)際上依賴于執(zhí)行javascript引擎機(jī)器的性能。當(dāng)然可以通過(guò)增加超時(shí)時(shí)間來(lái)達(dá)到更好的效果，但此時(shí)每一步行走速度會(huì)相應(yīng)變慢。

算法的改進(jìn)

目前這個(gè)實(shí)現(xiàn)作者聲稱成功合成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)

  1. 2048 Game
  2. 2048-AI github
  3. An Exhaustive Explanation of Minimax, a Staple AI Algorithm
  4. Tic Tac Toe: Understanding the Minimax Algorithm
  5. CS 161 Recitation Notes - Minimax with Alpha Beta Pruning

原文鏈接：http://blog./articles/2048-ai-analysis.html

【編輯推薦】

  1. 數(shù)據(jù)結(jié)構(gòu)與算法的JavaScript實(shí)現(xiàn)及應(yīng)用:Stack/遞歸/漢諾
  2. 熱門游戲 2048 C++ 源代碼分享
  3. 李炎恢老師JavaScript第一季視頻教程(149集)
  4. 測(cè)試系列課程之軟件測(cè)試基礎(chǔ)(42集)
  5. 瘋狂LoadRunner全新視頻【小強(qiáng)軟件測(cè)試系列】(19集)
【責(zé)任編輯：林師授 TEL：（010）68476606】

    本站是提供個(gè)人知識(shí)管理的網(wǎng)絡(luò)存儲(chǔ)空間，所有內(nèi)容均由用戶發(fā)布，不代表本站觀點(diǎn)。請(qǐng)注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購(gòu)買等信息，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請(qǐng)點(diǎn)擊一鍵舉報(bào)。
    轉(zhuǎn)藏 分享 獻(xiàn)花（0）

    0條評(píng)論

    發(fā)表

    請(qǐng)遵守用戶 評(píng)論公約

    類似文章 更多