利用演算法解決2048游戲
在 http://stackoverflow.com/questions/22342854/what-is-the-optimal-algorithm-for-the-game-2048/22389702#22389702 上有很多大牛提出了自己的解決方法。
ovolve 使用了 a-b剪枝，這是典型的用在博弈上的演算法，比如：之前的中國象棋就是用了這個方法。
Nicola Pezzotti 的特點在于貢獻了一個很簡易的計算局面整潔度的演算法.....
問題是上面的都是 js 語言撰寫的，對于我來說很難理解，并且很難進行評估。
個人感覺演算法本身不難，困難的是如何理解他們使用的資料結構，更具體來說困難度在于如何進行局面評估的演算法（這個問題中，需要對盤面順序程度和整體分數進行評估）。
最終，目光落在 nneonneo 的演算法上。他使用了 bit-map 的技術，能夠充分利用空間：每一個格子從 0-15 ，對應著 2^0 - 2^15 ，整個局面用64位即可表示。這樣做大大
降低了傳遞引數之類的耗時，客觀上節省了時間。此外，還使用陣列直接存放了行列的分數，評估行列分數直接讓陣列值相加即可，這是非常經典的空間換時間的做法。
他的程式可以在他的 git上下載到 https://github.com/nneonneo/2048-ai ，我這里也存了一份可以在 vs2008下編譯通過的
nneonneo
我的程式完全仿照了他的程式，只是沒有實作他用來剪枝的泛型 typedef std::map trans_table_t; 因為我使用的 Delphi 2010 沒有對應的功能，
在我的 I5 2450 上，一步大約需要2s左右。
呃，csdn有字數限制......
程式可以在 http://www.lab-z.com/2048ai/ 看到
后面會進行的改進：
1.使用整數代替程式中的single進行局面分數的評估。
2.實作nneonneo的剪枝演算法，計劃使用HouSisong大牛的DGL泛型庫 http://blog.csdn.net/housisong/article/category/152693
uj5u.com熱心網友回復：
接分，不用謝。uj5u.com熱心網友回復：
在我的i3上，用nneonneo的代碼，windows+cygwin，步驟消耗時間從0.07~4.65s之間不等。我已經算到了這里：
1320
1232
cb54
ed86
uj5u.com熱心網友回復：
不知何為2048游戲。uj5u.com熱心網友回復：
好的演算法能提高不少性能呢。開發2048是有挑戰性，我只會玩，嘿嘿
uj5u.com熱心網友回復：
為什么看不到你寫的？uj5u.com熱心網友回復：
2048益智游戲，贊 。轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/93154.html
標籤：語言基礎/算法/系統設計