什么是2048年游戏的最佳algorithm？
我最近偶然发现了2048年的比赛。 通过在四个方向中的任何一个方向移动它们来合并类似的瓷砖，以制作“更大”的瓷砖。 在每次移动之后，随机出现一个新的图块，其值为2或4 。 当所有的方块都被填满并且没有可以合并方块的移动时，游戏就会终止，或者你创build一个值为2048的方块。
一，我需要遵循一个明确的策略来实现目标。 所以，我想为它写一个程序。
我目前的algorithm：
while (!game_over) { for each possible move: count_no_of_merges_for_2-tiles and 4-tiles choose the move with a large number of merges }
我所做的是在任何时候，我会尝试将瓦片与值2和4合并，即尽可能最小化2和4瓦片。 如果我以这种方式尝试，所有其他瓷砖自动合并，战略似乎不错。
但是，当我实际使用这个algorithm时，在游戏结束之前我只能得到4000点左右。 AFAIK的最大分数略高于20,000分，比我现在的分数还要大。 有没有比上述更好的algorithm？
我使用expectimax优化来开发一个2048 AI，而不是使用@ ovolvealgorithm的minimaxsearch。 AI简单地执行所有可能的移动的最大化，随后是对所有可能的瓦片产生的预期（由瓦片的概率加权，即，对于4的10％和对于2的90％）。 据我所知，不可能修剪expectimax优化（除去删除极不可能的分支除外），所以使用的algorithm是一个仔细优化的蛮力search。
性能
AI的默认configuration（最大search深度为8）需要10ms到200ms的任意位置来执行移动，具体取决于电路板位置的复杂程度。 在testing中，AI在整个游戏过程中平均每秒移动5-10次。 如果search深度仅限于6次移动，AI可以很容易地每秒执行20次以上的移动，这使得一些有趣的观看 。
为了评估AI的分数performance，我跑了AI100次（通过遥控器连接到浏览器游戏）。 对于每个瓦片，这里是至less一次获得该瓦片的游戏的比例：
2048: 100% 4096: 100% 8192: 100% 16384: 94% 32768: 36%
全部最低分是124024; 最高分是794076.中位数是387222. AI从来没有获得过2048分（所以它从来没有在100场比赛中输过一次）。 事实上，它在每一次运行中至less实现了8192个瓦片！
下面是最佳运行的截图：
这场比赛用了96分钟27830次，平均每秒4.8次。
履行
我的方法是将整个板（16项）编码为一个64位整数（其中tile是nybbles，即4位块）。 在一个64位的机器上，这使得整个电路板可以在一个机器寄存器中传递。
位移操作用于提取单独的行和列。 一行或一列是一个16位的数量，所以一个大小为65536的表可以编码在单个行或列上操作的转换。 例如，移动被执行为4次查find预先计算的“移动效果表”中，该移动效果表描述每个移动如何影响单个行或列（例如，“右移”表包含条目“1122 – > 0023”行[2,2,4,4]在右移时变成行[0,0,4,8]）。
评分也使用表查找。 这些表包含在所有可能的行/列上计算的启发式分数，并且板的最终得分仅仅是每个行和列的表值的总和。
这种棋盘performanceforms，以及移动和得分的表格查找方法，使AI能够在短时间内search到大量的游戏状态（在我2011年中的笔记本电脑的一个核心上每秒超过10,000,000个游戏状态）。
expectimaxsearch本身被编码为recursionsearch，在“期望”步骤之间交替（testing所有可能的tile产生位置和值，并且根据每个可能性的概率来加权它们的优化分数）和“最大化”步骤（testing所有可能的移动并select最好的分数）。 树search在看到先前看到的位置（使用换位表 ）时，当它达到预定义的深度限制时，或者当它达到非常不可能的板状态时终止（例如，通过获得6“4”块从起始位置开始连续）。 典型的search深度是4-8步。
启发式
几种启发式algorithm被用来将优化algorithm引向有利的位置。 启发式的精确select对algorithm的性能有很大的影响。 各种启发式algorithm被加权并合并成位置分数，这决定了给定棋盘位置的“好”程度。 然后优化search将旨在最大化所有可能的董事会职位的平均分数。 如游戏所示，实际得分并不用于计算董事会得分，因为它的权重过大，有利于合并切片（当延迟合并可能产生大的收益时）。
最初，我使用了两个非常简单的启发式方法，为空心方块授予“奖金”，并在边缘设置较大的值。 这些启发式performance相当不错，经常达到16384，但从未达到32768。
PetrMorávek（@ xificurk）带走了我的AI，并添加了两个新的启发式。 第一个启发式是非单调的行和列随着行列增加而增加的惩罚，确保非单调的小数行不会强烈地影响分数，但非单调的大数行大大伤害了分数。 第二个启发式algorithm除了开放空间之外，还计算了潜在合并的数量（相邻的相等值）。 这两种启发式algorithm将algorithm推向了单调板（更容易合并），并且朝着具有大量合并的板位置（鼓励它在可能的情况下调整合并以获得更好的效果）。
此外，Petr还使用“元优化”策略（使用称为CMA-ES的algorithm）优化了启发式权重，其中权重本身进行了调整，以获得尽可能高的平均分数。
这些变化的影响是非常重要的。 algorithm从大约13％的时间实现了16384个瓦片到超过90％的时间达到了该algorithm，并且该algorithm在1/3的时间内开始达到32768（而旧的启发式algorithm从未产生32768个瓦片） 。
我相信启发式方法还有待改进。 这个algorithm肯定还不是“最优”的，但是我觉得它变得非常接近。
人工智能超过三分之一的游戏达到32768平方米是一个巨大的里程碑。 如果任何人类玩家在正式游戏中获得了32768（即不使用投资或撤销的工具），我会惊讶的发现。 我认为65536瓦片是可及的！
你可以尝试自己的AI。 该代码可在https://github.com/nneonneo/2048-ai 。
我是其他人在这个线程中提到的AI程序的作者。 您可以查看AI的行动或阅读来源 。
目前，我的笔记本电脑在浏览器中的javascript运行速度达到了90％左右，每次移动的思考时间大约为100毫秒，所以虽然不够完美（还不算完美），但performance相当不错。
由于游戏是一个离散的状态空间，完美的信息，象棋和棋子这样的基于回合的游戏，我使用了已经被certificate在这些游戏上运行的相同的方法，即使用alpha-beta修剪的 极小极大 search 。 既然已经有很多关于这个algorithm的信息了，那么我只想谈谈我在静态评估函数中使用的两个主要的启发式，以及其他人在这里expression的许多直觉。
单调性
该启发式尝试确保瓦片的值沿着左/右和上/下方向全部增加或减小。 单独的这种启发式方法捕捉了很多人提到的直觉，认为更高价值的瓷砖应该聚集在一个angular落里。 它通常会防止价值较小的瓷砖成为孤儿，并保持电路板的组织性，使较小的瓷砖层叠并填充到较大的瓷砖中。
这是一个完美的单调网格截图。 我通过运行带有eval函数的algorithm来获得这个结果，忽略其他启发式，只考虑单调性。
顺利
单独的上述启发式倾向于创造相邻的瓷砖价值下降的结构，但是当然为了合并，相邻的瓷砖需要是相同的价值。 因此，光滑启发式只是测量相邻瓷砖之间的价值差异，试图最小化这个数量。
“黑客新闻”的一位评论者用图论的方法对这个想法进行了有趣的forms化 。
这是一个非常平滑的网格截图，由这个优秀的模仿叉子礼貌。
免费瓷砖
最后，有一个罚款免费瓷砖太less，因为选项可以很快跑出来，当游戏板太狭窄。
而就是这样！ 在优化这些标准的同时search游戏空间，可以获得非常好的性能。 使用这种通用方法而不是明确编码的移动策略的一个优点是该algorithm经常可以find有趣和意想不到的解决scheme。 如果你看它运行，它往往会令人惊讶，但有效的举动，如突然改变它正在build设的墙壁或angular落。
编辑：
以下是这种方法的功效演示。 我打开瓦片值（所以它继续到达2048后），这是八次审判后的最好结果。
是的，这是一个4096旁边的2048. =）这意味着它在同一块板子上三次实现了难以捉摸的2048瓦片。
编辑：这是一个天真的algorithm，build模人类有意识的思维过程，并得到非常薄弱的结果相比，人工智能，search所有的可能性，因为它只看起来前面一块。 它是在响应时间表早期提交的。
我已经完善了algorithm，打败了游戏！ 它可能会失败，因为接近尾声的简单运气不好（你不得不向下移动，这是你永远不应该做的，并且一个贴图会出现在你的最高位置），只要保持顶行被填满，向左移动不会打破模式），但基本上你最终有一个固定的部分和一个移动部分玩。 这是你的目标：
这是我默认select的模式。
1024 512 256 128 8 16 32 64 4 2 xx xxxx
所选的angular落是任意的，你基本上从来不会按一个键（禁止的移动），如果你这样做，你再次按相反，并尝试修复它。 对于未来的贴图，模型总是期望下一个随机贴图是2，并出现在当前模型的反面（而第一行是不完整的，在右下angular，一旦第一行完成，在左下angularangular）。
这里是algorithm。 大约80％的胜利（似乎总是有可能用更多的“专业”AI技术获胜，但我不确定这一点。）
initiateModel(); while(!game_over) { checkCornerChosen(); // Unimplemented, but it might be an improvement to change the reference point for each 3 possible move: evaluateResult() execute move with best score if no move is available, execute forbidden move and undo, recalculateModel() } evaluateResult() { calculatesBestCurrentModel() calculates distance to chosen model stores result } calculateBestCurrentModel() { (according to the current highest tile acheived and their distribution) }
几个关于缺less步骤的指针。 这里： 
由于接近预期模型的运气，模型已经发生了变化。 AI试图实现的模型是
512 256 128 x XX xx XX xx xxxx
而到那里的连锁已成为：
512 256 64 O 8 16 32 O 4 xxx xxxx
O代表禁止空间…
所以它会右键，然后右键，然后（右或顶取决于4创build的地方），然后将继续完成链，直到它得到：
那么现在模型和链条又回到了：
512 256 128 64 4 8 16 32 XX xx xxxx
第二个指针，运气不好，主要的位置已经被占用。 它很可能会失败，但它仍然可以实现：
这里的模型和链是：
O 1024 512 256 OOO 128 8 16 32 64 4 xxx
当它设法达到128时，它又获得了一整行：
O 1024 512 256 xx 128 128 xxxx xxxx
我对这个不包含硬编码智能 （即没有启发式，评分函数等）的AI的想法感兴趣。 人工智能应该只“知道”游戏规则，并“弄清”游戏玩法。 这与大多数AI（比如这个线程中的AI）形成了鲜明的对比，在这种情况下，游戏本质上是一种代表人类对游戏理解的评分函数。
AIalgorithm
我发现了一个简单但令人惊讶的优秀演奏algorithm：为了确定给定演奏板的下一步动作，AI使用随机动作直到最后演奏游戏。 这是做了很多次，同时跟踪最终得分。 然后计算每个出发点的平均最终分数。 下一步是select平均得分最高的开局。
AI每次移动100次，AI达到时间的20％，时间的80％，4096次，达到50％。 使用10000次运行可获得2048个瓦片100％，4096个瓦片的70％，以及8192个瓦片的约1％。
看到它的行动
最佳实现分数如下所示：
关于这个algorithm的一个有趣的事实是，虽然随机播放游戏（不出所料）相当糟糕，但是select最好的（或者最不好的）移动会导致非常好的游戏玩法：一个典型的AI游戏可以达到70000点和最后的3000点移动，然而从任意位置随机播放的平均得分为340加分，而在临死之前只有40个额外的移动。 （您可以通过运行AI并打开debugging控制台来查看。
这张图说明了这一点：蓝线显示了每次移动后的棋盘得分。 红线显示algorithm从该位置随机运行的最终得分。 实质上，红色值是将蓝色值“向上拉”，因为它们是algorithm的最佳猜测。 看到红线在每一点上方的蓝线上方都是一点点，而蓝线却越来越多，这是很有趣的。
我发现这个algorithm并不需要真正预见好的游戏以便select产生它的动作，这让我感到非常惊讶。
后来search，我发现这个algorithm可能被归类为一个纯蒙特卡洛树searchalgorithm。
实施和链接
首先我创build了一个可以在这里看到的JavaScript版本。 这个版本可以运行100年的体面的时间。 打开控制台获取更多信息。 （ 来源 ）
后来，为了发挥更多我使用@nneonneo高度优化的基础设施，并在C ++中实现我的版本。 这个版本允许每次移动100000次，如果你有耐心，甚至1000000次。 提供build筑指导。 它在控制台中运行，也有一个遥控器来播放网页版本。 （ 来源 ）
结果
令人惊讶的是，增加跑步次数并不会大大提高游戏的效率。 这个策略似乎有一个限制，大约在80000点，4096瓦和所有的小瓦，非常接近实现8192瓦。 将运行次数从100次增加到100000次，增加了达到此分数限制的可能性 （从5％到40％），但没有突破它。
在临界位置附近临时增加100万次运行10000次，设法打破这个屏障的时间不到1％，达到最高分129892次和8192次。
改进
实现这个algorithm后，我尝试了许多改进，包括使用min或max分数，或min，max和avg的组合。 我也尝试过使用深度：而不是尝试每次移动K次运行，我尝试了给定长度的K个移动列表 （例如“向上，向上，向左”），并select最佳得分移动列表的第一个移动。
后来，我实现了一个评分树，考虑了在给定的移动列表之后能够进行移动的条件概率。
然而，这些想法都没有显示出简单的第一个想法的真正优势。 我将这些想法的代码留在了C ++代码中。
我确实增加了一个“深度search”机制，当运行中的任何一个跑到偶然到达的下一个最高的区块时，就会暂时将运行数增加到100万。 这提供了一个时间的改善。
我有兴趣听听有没有人有其他的改进思路来保持AI的领域独立性。
2048变体和克隆
为了好玩，我也将AI作为一个小书签来实现 ，并将其挂在游戏的控件上。 这使得AI可以与原始游戏及其许多变体一起工作 。
由于AI的领域独立性质，这是可能的。 一些变体是非常不同的，例如六angular形克隆。
我在这里复制我的博客上的一篇文章的内容
我提出的解决scheme非常简单，易于实现。 虽然它已经达到了131040的分数。给出了algorithm性能的几个基准。
algorithm
启发式评分algorithm
我的algorithm所基于的假设是相当简单的：如果你想获得更高的分数，董事会必须保持尽可能的整洁。 特别地，最优设置由瓦片值的线性和单调递减顺序给出。 这个直觉会给你一个瓦片值的上限： 其中n是棋盘上的瓦片数量。
（如果4-tile是随机生成的而不是2-tile，则有可能达到131072）
以下图片显示了两种可能的组织电路板的方法：
为了以单调递减顺序执行瓦片的sorting，计算得分si作为板上的线性化值的总和乘以具有公共比率r <1的几何序列的值。
几个线性path可以一次进行评估，最终得分将是任何path的最高分数。
决策规则
实现的决策规则不是很聪明，Python中的代码如下所示：
@staticmethod def nextMove(board,recursion_depth=3): m,s = AI.nextMoveRecur(board,recursion_depth,recursion_depth) return m @staticmethod def nextMoveRecur(board,depth,maxDepth,base=0.9): bestScore = -1. bestMove = 0 for m in range(1,5): if(board.validMove(m)): newBoard = copy.deepcopy(board) newBoard.move(m,add_tile=True) score = AI.evaluate(newBoard) if depth != 0: my_m,my_s = AI.nextMoveRecur(newBoard,depth-1,maxDepth) score += my_s*pow(base,maxDepth-depth+1) if(score > bestScore): bestMove = m bestScore = score return (bestMove,bestScore);
Minmax或Expectiminimax的实现将肯定会改进algorithm。 很显然，一个更复杂的决策规则会减慢algorithm的速度，需要一些时间来实现。我将在不久的将来尝试minimax的实现。 （敬请关注）
基准
- T1 – 121testing – 8个不同的path – r = 0.125
- T2 – 122testing – 8个不同的path – r = 0.25
- T3 – 132testing – 8个不同的path – r = 0.5
- T4 – 211testing – 两种不同的path – r = 0.125
- T5 – 274testing – 2个不同的path – r = 0.25
- T6 – 211testing – 2个不同的path – r = 0.5
在T2的情况下，十个中的四个testing产生平均分数为4096的4096个瓦片 42000
码
代码可以在GiHub的以下链接find： https ： //github.com/Nicola17/term2048-AI它是基于term2048 ，它是用Python编写的。 我将尽快在C ++中实现更高效的版本。
我尝试使用expectimax像上面的其他解决scheme，但没有bitboards。 Nneonneo的解决scheme可以检查1000左右的移动，大概是4的深度，剩下6个棋子，可以移动4个棋子（2 * 6 * 4） 4 。 在我的情况下，这个深度需要很长的时间来探索，我根据剩余的剩余砖块的数量来调整最后search的深度：
depth = free > 7 ? 1 : (free > 4 ? 2 : 3)
计算棋盘的得分，用免费拼块数量的平方和二维网格的点积的加权和来计算：
[[10,8,7,6.5], [.5,.7,1,3], [-.5,-1.5,-1.8,-2], [-3.8,-3.7,-3.5,-3]]
这些力量从左上方的瓦片中以蛇的forms递减地组织瓦片。
下面的代码或jsbin ：
var n = 4, M = new MatrixTransform(n); var ai = {weights: [1, 1], depth: 1}; // depth=1 by default, but we adjust it on every prediction according to the number of free tiles var snake= [[10,8,7,6.5], [.5,.7,1,3], [-.5,-1.5,-1.8,-2], [-3.8,-3.7,-3.5,-3]] snake=snake.map(function(a){return a.map(Math.exp)}) initialize(ai) function run(ai) { var p; while ((p = predict(ai)) != null) { move(p, ai); } //console.log(ai.grid , maxValue(ai.grid)) ai.maxValue = maxValue(ai.grid) console.log(ai) } function initialize(ai) { ai.grid = []; for (var i = 0; i < n; i++) { ai.grid[i] = [] for (var j = 0; j < n; j++) { ai.grid[i][j] = 0; } } rand(ai.grid) rand(ai.grid) ai.steps = 0; } function move(p, ai) { //0:up, 1:right, 2:down, 3:left var newgrid = mv(p, ai.grid); if (!equal(newgrid, ai.grid)) { //console.log(stats(newgrid, ai.grid)) ai.grid = newgrid; try { rand(ai.grid) ai.steps++; } catch (e) { console.log('no room', e) } } } function predict(ai) { var free = freeCells(ai.grid); ai.depth = free > 7 ? 1 : (free > 4 ? 2 : 3); var root = {path: [],prob: 1,grid: ai.grid,children: []}; var x = expandMove(root, ai) //console.log("number of leaves", x) //console.log("number of leaves2", countLeaves(root)) if (!root.children.length) return null var values = root.children.map(expectimax); var mx = max(values); return root.children[mx[1]].path[0] } function countLeaves(node) { var x = 0; if (!node.children.length) return 1; for (var n of node.children) x += countLeaves(n); return x; } function expectimax(node) { if (!node.children.length) { return node.score } else { var values = node.children.map(expectimax); if (node.prob) { //we are at a max node return Math.max.apply(null, values) } else { // we are at a random node var avg = 0; for (var i = 0; i < values.length; i++) avg += node.children[i].prob * values[i] return avg / (values.length / 2) } } } function expandRandom(node, ai) { var x = 0; for (var i = 0; i < node.grid.length; i++) for (var j = 0; j < node.grid.length; j++) if (!node.grid[i][j]) { var grid2 = M.copy(node.grid), grid4 = M.copy(node.grid); grid2[i][j] = 2; grid4[i][j] = 4; var child2 = {grid: grid2,prob: .9,path: node.path,children: []}; var child4 = {grid: grid4,prob: .1,path: node.path,children: []} node.children.push(child2) node.children.push(child4) x += expandMove(child2, ai) x += expandMove(child4, ai) } return x; } function expandMove(node, ai) { // node={grid,path,score} var isLeaf = true, x = 0; if (node.path.length < ai.depth) { for (var move of[0, 1, 2, 3]) { var grid = mv(move, node.grid); if (!equal(grid, node.grid)) { isLeaf = false; var child = {grid: grid,path: node.path.concat([move]),children: []} node.children.push(child) x += expandRandom(child, ai) } } } if (isLeaf) node.score = dot(ai.weights, stats(node.grid)) return isLeaf ? 1 : x; } var cells = [] var table = document.querySelector("table"); for (var i = 0; i < n; i++) { var tr = document.createElement("tr"); cells[i] = []; for (var j = 0; j < n; j++) { cells[i][j] = document.createElement("td"); tr.appendChild(cells[i][j]) } table.appendChild(tr); } function updateUI(ai) { cells.forEach(function(a, i) { a.forEach(function(el, j) { el.innerHTML = ai.grid[i][j] || '' }) }); } updateUI(ai) function runAI() { var p = predict(ai); if (p != null && ai.running) { move(p, ai) updateUI(ai) requestAnimationFrame(runAI) } } runai.onclick = function() { if (!ai.running) { this.innerHTML = 'stop AI'; ai.running = true; runAI(); } else { this.innerHTML = 'run AI'; ai.running = false; } } hint.onclick = function() { hintvalue.innerHTML = ['up', 'right', 'down', 'left'][predict(ai)] } document.addEventListener("keydown", function(event) { if (event.which in map) { move(map[event.which], ai) console.log(stats(ai.grid)) updateUI(ai) } }) var map = { 38: 0, // Up 39: 1, // Right 40: 2, // Down 37: 3, // Left }; init.onclick = function() { initialize(ai); updateUI(ai) } function stats(grid, previousGrid) { var free = freeCells(grid); var c = dot2(grid, snake); return [c, free * free]; } function dist2(a, b) { //squared 2D distance return Math.pow(a[0] - b[0], 2) + Math.pow(a[1] - b[1], 2) } function dot(a, b) { var r = 0; for (var i = 0; i < a.length; i++) r += a[i] * b[i]; return r } function dot2(a, b) { var r = 0; for (var i = 0; i < a.length; i++) for (var j = 0; j < a[0].length; j++) r += a[i][j] * b[i][j] return r; } function product(a) { return a.reduce(function(v, x) { return v * x }, 1) } function maxValue(grid) { return Math.max.apply(null, grid.map(function(a) { return Math.max.apply(null, a) })); } function freeCells(grid) { return grid.reduce(function(v, a) { return v + a.reduce(function(t, x) { return t + (x == 0) }, 0) }, 0) } function max(arr) { // return [value, index] of the max var m = [-Infinity, null]; for (var i = 0; i < arr.length; i++) { if (arr[i] > m[0]) m = [arr[i], i]; } return m } function min(arr) { // return [value, index] of the min var m = [Infinity, null]; for (var i = 0; i < arr.length; i++) { if (arr[i] < m[0]) m = [arr[i], i]; } return m } function maxScore(nodes) { var min = { score: -Infinity, path: [] }; for (var node of nodes) { if (node.score > min.score) min = node; } return min; } function mv(k, grid) { var tgrid = M.itransform(k, grid); for (var i = 0; i < tgrid.length; i++) { var a = tgrid[i]; for (var j = 0, jj = 0; j < a.length; j++) if (a[j]) a[jj++] = (j < a.length - 1 && a[j] == a[j + 1]) ? 2 * a[j++] : a[j] for (; jj < a.length; jj++) a[jj] = 0; } return M.transform(k, tgrid); } function rand(grid) { var r = Math.floor(Math.random() * freeCells(grid)), _r = 0; for (var i = 0; i < grid.length; i++) { for (var j = 0; j < grid.length; j++) { if (!grid[i][j]) { if (_r == r) { grid[i][j] = Math.random() < .9 ? 2 : 4 } _r++; } } } } function equal(grid1, grid2) { for (var i = 0; i < grid1.length; i++) for (var j = 0; j < grid1.length; j++) if (grid1[i][j] != grid2[i][j]) return false; return true; } function conv44valid(a, b) { var r = 0; for (var i = 0; i < 4; i++) for (var j = 0; j < 4; j++) r += a[i][j] * b[3 - i][3 - j] return r } function MatrixTransform(n) { var g = [], ig = []; for (var i = 0; i < n; i++) { g[i] = []; ig[i] = []; for (var j = 0; j < n; j++) { g[i][j] = [[j, i],[i, n-1-j],[j, n-1-i],[i, j]]; // transformation matrix in the 4 directions g[i][j] = [up, right, down, left] ig[i][j] = [[j, i],[i, n-1-j],[n-1-j, i],[i, j]]; // the inverse tranformations } } this.transform = function(k, grid) { return this.transformer(k, grid, g) } this.itransform = function(k, grid) { // inverse transform return this.transformer(k, grid, ig) } this.transformer = function(k, grid, mat) { var newgrid = []; for (var i = 0; i < grid.length; i++) { newgrid[i] = []; for (var j = 0; j < grid.length; j++) newgrid[i][j] = grid[mat[i][j][k][0]][mat[i][j][k][1]]; } return newgrid; } this.copy = function(grid) { return this.transform(3, grid) } }
body { text-align: center } table, th, td { border: 1px solid black; margin: 5px auto; } td { width: 35px; height: 35px; text-align: center; }
<table></table> <button id=init>init</button><button id=runai>run AI</button><button id=hint>hint</button><span id=hintvalue></span>
I think I found an algorithm which works quite well, as I often reach scores over 10000, my personal best being around 16000. My solution does not aim at keeping biggest numbers in a corner, but to keep it in the top row.
Please see the code below:
while( !game_over ) { move_direction=up; if( !move_is_possible(up) ) { if( move_is_possible(right) && move_is_possible(left) ){ if( number_of_empty_cells_after_moves(left,up) > number_of_empty_cells_after_moves(right,up) ) move_direction = left; else move_direction = right; } else if ( move_is_possible(left) ){ move_direction = left; } else if ( move_is_possible(right) ){ move_direction = right; } else { move_direction = down; } } do_move(move_direction); }
I am the author of a 2048 controller that scores better than any other program mentioned in this thread. An efficient implementation of the controller is available on github . In a separate repo there is also the code used for training the controller's state evaluation function. The training method is described in the paper .
The controller uses expectimax search with a state evaluation function learned from scratch (without human 2048 expertise) by a variant of temporal difference learning (a reinforcement learning technique). The state-value function uses an n-tuple network , which is basically a weighted linear function of patterns observed on the board. It involved more than 1 billion weights , in total.
性能
At 1 moves/s: 609104 (100 games average)
At 10 moves/s: 589355 (300 games average)
At 3-ply (ca. 1500 moves/s): 511759 (1000 games average)
The tile statistics for 10 moves/s are as follows:
2048: 100% 4096: 100% 8192: 100% 16384: 97% 32768: 64% 32768,16384,8192,4096: 10%
(The last line means having the given tiles at the same time on the board).
For 3-ply:
2048: 100% 4096: 100% 8192: 100% 16384: 96% 32768: 54% 32768,16384,8192,4096: 8%
However, I have never observed it obtaining the 65536 tile.
There is already an AI implementation for this game: here . Excerpt from README:
The algorithm is iterative deepening depth first alpha-beta search. The evaluation function tries to keep the rows and columns monotonic (either all decreasing or increasing) while minimizing the number of tiles on the grid.
There is also a discussion on ycombinator about this algorithm that you may find useful.
algorithm
while(!game_over) { for each possible move: evaluate next state choose the maximum evaluation }
Evaluation
Evaluation = 128 (Constant) + (Number of Spaces x 128) + Sum of faces adjacent to a space { (1/face) x 4096 } + Sum of other faces { log(face) x 4 } + (Number of possible next moves x 256) + (Number of aligned values x 2)
Evaluation Details
128 (Constant)
This is a constant, used as a base-line and for other uses like testing.
+ (Number of Spaces x 128)
More spaces makes the state more flexible, we multiply by 128 (which is the median) since a grid filled with 128 faces is an optimal impossible state.
+ Sum of faces adjacent to a space { (1/face) x 4096 }
Here we evaluate faces that have the possibility to getting to merge, by evaluating them backwardly, tile 2 become of value 2048, while tile 2048 is evaluated 2.
+ Sum of other faces { log(face) x 4 }
In here we still need to check for stacked values, but in a lesser way that doesn't interrupt the flexibility parameters, so we have the sum of { x in [4,44] }.
+ (Number of possible next moves x 256)
A state is more flexible if it has more freedom of possible transitions.
+ (Number of aligned values x 2)
This is a simplified check of the possibility of having merges within that state, without making a look-ahead.
Note: The constants can be tweaked..
I wrote a 2048 solver in Haskell, mainly because I'm learning this language right now.
My implementation of the game slightly differs from the actual game, in that a new tile is always a '2' (rather than 90% 2 and 10% 4). And that the new tile is not random, but always the first available one from the top left. This variant is also known as Det 2048 .
As a consequence, this solver is deterministic.
I used an exhaustive algorithm that favours empty tiles. It performs pretty quickly for depth 1-4, but on depth 5 it gets rather slow at a around 1 second per move.
Below is the code implementing the solving algorithm. The grid is represented as a 16-length array of Integers. And scoring is done simply by counting the number of empty squares.
bestMove :: Int -> [Int] -> Int bestMove depth grid = maxTuple [ (gridValue depth (takeTurn x grid), x) | x <- [0..3], takeTurn x grid /= [] ] gridValue :: Int -> [Int] -> Int gridValue _ [] = -1 gridValue 0 grid = length $ filter (==0) grid -- <= SCORING gridValue depth grid = maxInList [ gridValue (depth-1) (takeTurn x grid) | x <- [0..3] ]
I thinks it's quite successful for its simplicity. The result it reaches when starting with an empty grid and solving at depth 5 is:
Move 4006 [2,64,16,4] [16,4096,128,512] [2048,64,1024,16] [2,4,16,2] Game Over
Source code can be found here: https://github.com/popovitsj/2048-haskell
This is not a direct answer to OP's question, this is more of the stuffs (experiments) I tried so far to solve the same problem and obtained some results and have some observations that I want to share, I am curious if we can have some further insights from this.
I just tried my minimax implementation with alpha-beta pruning with search-tree depth cutoff at 3 and 5. I was trying to solve the same problem for a 4×4 grid as a project assignment for the edX course ColumbiaX: CSMM.101x Artificial Intelligence (AI) .
I applied convex combination (tried different heuristic weights) of couple of heuristic evaluation functions, mainly from intuition and from the ones discussed above:
- Monotonicity
- Free Space Available
In my case, the computer player is completely random, but still i assumed adversarial settings and implemented the AI player agent as the max player.
I have 4×4 grid for playing the game.
Observation:
If I assign too much weights to the first heuristic function or the second heuristic function, both the cases the scores the AI player gets are low. I played with many possible weight assignments to the heuristic functions and take a convex combination, but very rarely the AI player is able to score 2048. Most of the times it either stops at 1024 or 512.
I also tried the corner heuristic, but for some reason it makes the results worse, any intuition why?
Also, I tried to increase the search depth cut-off from 3 to 5 (I can't increase it more since searching that space exceeds allowed time even with pruning) and added one more heuristic that looks at the values of adjacent tiles and gives more points if they are merge-able, but still I am not able to get 2048.
I think it will be better to use Expectimax instead of minimax, but still I want to solve this problem with minimax only and obtain high scores such as 2048 or 4096. I am not sure whether I am missing anything.
Below animation shows the last few steps of the game played by the AI agent with the computer player:
Any insights will be really very helpful, thanks in advance. (This is the link of my blog post for the article: https://sandipanweb.wordpress.com/2017/03/06/using-minimax-with-alpha-beta-pruning-and-heuristic-evaluation-to-solve-2048-game-with-computer/ )
The following animation shows the last few steps of the game played where the AI player agent could get 2048 scores, this time adding the absolute value heuristic too:
The following figures show the game tree explored by the player AI agent assuming the computer as adversary for just a single step:
This algorithm is not optimal for winning the game, but it is fairly optimal in terms of performance and amount of code needed:
if(can move neither right, up or down) direction = left else { do { direction = random from (right, down, up) } while(can not move in "direction") }
Many of the other answers use AI with computationally expensive searching of possible futures, or are a sort of artificial mind that can learn, and the such, these are very impressive and probably the correct way forward, but I wish to contribute another idea.
Model the sort of strategy that good players of the game use.
例如：
13 14 15 16 12 11 10 9 5 6 7 8 4 3 2 1
Read the squares in the order shown above until the next squares value is greater the current one, then try to merge another tile of the same value into this square.
To resolve this problem their are 2 ways to move that arn't left or worse up and examining both possibilities may emmidatly reveal more problems, this forms a list of dependancies, each problem requiring another problem to be solved first. I think I have this chain or sometimes tree of dependancies Internally when deciding my next move, particularly when stuck.
Tile needs merging with neighbour but is too small: Merge another neighbour with this one.
Larger tile in the way: Increase the value of a smaller surrounding tile.
等等…
The whole aproach will likely be complicated than this, and even as I write it seems to contain too much hidden issues behind implementing every part of the strategy, but could perhaps be this mechanical in feel, without scores, weights, neurones and deep searches of possibilities.
