我最近偶然发现了2048游戏。通过在四个方向中的任何一个方向上移动类似的平铺，可以合并它们，以生成“更大”的平铺。每次移动后，一个新的平铺显示在随机的空位置，值为2或4。当所有的方块都被填满并且没有可以合并平铺的移动，或者你创建了一个值为2048的平铺时，游戏终止。
首先，我需要遵循一个明确的战略来实现目标。所以，我想为它写一个程序。
我当前的算法：
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个平铺。如果我这样做，所有其他平铺都会自动合并，策略似乎很好。
但是，当我实际使用这个算法时，在游戏结束之前，我只得到了大约4000分。AFAIK的最高分数略高于20000分，这比我目前的分数要大得多。有比上述更好的算法吗？
当前回答
我想我找到了一个非常有效的算法，因为我经常得分超过10000分，我个人最好的成绩是16000分左右。我的解决方案并不是要把最大的数字放在角落里，而是要把它放在最前排。
请参见以下代码：
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);
}
其他回答
这里已经有了这款游戏的AI实现。自述节选：
该算法是迭代加深深度优先alpha beta搜索。求值函数试图保持行和列的单调性（要么减少，要么增加），同时最小化网格上的平铺数量。
黑客新闻上也有关于这个算法的讨论，你可能会发现它很有用。
我是一个2048控制器的作者，它的得分比本主题中提到的任何其他程序都要高。github上提供了控制器的有效实现。在单独的回购中，还有用于训练控制器状态评估功能的代码。本文描述了训练方法。
控制器使用expectimax搜索，该搜索具有通过时间差学习（强化学习技术）的变体从零开始学习的状态评估函数（没有人类2048专业知识）。状态值函数使用n元组网络，它基本上是板上观察到的模式的加权线性函数。总共涉及超过10亿重量。
表演
1次移动/秒：609104（平均100局）
10次移动/秒：589355（平均300场）
3局（约1500步/秒）：511759（平均1000局）
10次移动/秒的平铺统计如下：
2048: 100%
4096: 100%
8192: 100%
16384: 97%
32768: 64%
32768,16384,8192,4096: 10%
（最后一行表示在板上同时具有给定的瓷砖）。
对于3层：
2048: 100%
4096: 100%
8192: 100%
16384: 96%
32768: 54%
32768,16384,8192,4096: 8%
然而，我从未观察到它获得65536平铺。
这不是对OP问题的直接回答，这是我迄今为止试图解决同一问题的更多东西（实验），并获得了一些结果和一些我想分享的观察结果，我很好奇我们能否从中获得一些进一步的见解。
我刚刚尝试了使用alpha beta修剪的minimax实现，搜索树深度截止值为3和5。我试图解决4x4网格的相同问题，作为edX课程ColumbiaX:CSMM101x人工智能（AI）的项目作业。
我应用了两个启发式评估函数的凸组合（尝试了不同的启发式权重），主要来自直觉和上面讨论的函数：
单调性可用的可用空间
在我的情况下，电脑玩家是完全随机的，但我仍然假设了对抗性设置，并将AI玩家代理实现为最大玩家。
我有4x4网格来玩游戏。
观察结果：
如果我给第一个启发式函数或第二个启发式函数分配了太多权重，那么AI玩家获得的分数都很低。我对启发式函数进行了许多可能的权重分配，并采用了凸组合，但很少有AI玩家能够得分2048。大多数时候，它要么停在1024或512。
我也尝试过拐角启发式，但出于某种原因，它会使结果更糟，凭直觉为什么？
此外，我尝试将搜索深度截止值从3增加到5（我不能再增加了，因为即使在修剪的情况下，搜索该空间也超过了允许的时间），并添加了一个启发式方法，它查看相邻平铺的值，如果它们可以合并，则会给出更多的点，但我仍然无法获得2048。
我认为使用Expectimax而不是minimax会更好，但我仍然希望只使用minimax来解决这个问题，并获得2048或4096等高分。我不确定我是否遗漏了什么。
以下动画显示了AI代理与计算机玩家玩游戏的最后几个步骤：
任何见解都将非常有用，提前感谢。（这是我博客文章的链接：https://sandipanweb.wordpress.com/2017/03/06/using-minimax-with-alpha-beta-pruning-and-heuristic-evaluation-to-solve-2048-game-with-computer/以及youtube视频：https://www.youtube.com/watch?v=VnVFilfZ0r4)
以下动画显示了游戏的最后几个步骤，其中AI玩家代理可以获得2048分，这一次还添加了绝对值启发式：
下图显示了玩家AI代理探索的游戏树，假设计算机是对手，只需一步：
我想我找到了一个非常有效的算法，因为我经常得分超过10000分，我个人最好的成绩是16000分左右。我的解决方案并不是要把最大的数字放在角落里，而是要把它放在最前排。
请参见以下代码：
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);
}
我的尝试与上面的其他解决方案一样使用expectimax，但没有比特板。Nneonneo的解决方案可以检查1000万次移动，大约深度为4，剩余6个平铺，可能移动4次（2*6*4）4。在我的情况下，这个深度需要很长时间来探索，我根据剩余的空闲平铺数调整expectimax搜索的深度：
depth = free > 7 ? 1 : (free > 4 ? 2 : 3)
板的得分通过自由瓷砖数量的平方和2D网格的点积的加权和计算，如下所示：
[[10,8,7,6.5],
[.5,.7,1,3],
[-.5,-1.5,-1.8,-2],
[-3.8,-3.7,-3.5,-3]]
这迫使从左上角的瓦片以蛇形的方式向下组织瓦片。
下面或github上的代码：
变量n＝4，M=新矩阵变换（n）；var ai=｛weights:[1，1]，深度：1｝；//默认情况下，depth=1，但我们会根据空闲平铺的数量对每个预测进行调整var蛇=[[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（函数（a）｛return a.map（Math.exp）｝）初始化（ai）函数运行（ai）{变量p；而（（p=预测（ai））！=空）{移动（p，ai）；}//console.log（ai.grid，maxValue（ai.ggrid））ai.maxValue=最大值（ai.grid）控制台日志（ai）}函数初始化（ai）{ai.grid=[]；对于（变量i=0；i<n；i++）{ai网格[i]=[]对于（变量j=0；j<n；j++）{ai.grid[i][j]=0；}}兰特（ai网格）兰特（ai网格）ai.steps=0；}函数move（p，ai）{//0:向上，1:向右，2:向下，3:向左var newgrid=mv（p，ai.grid）；if（！equal（newgrid，ai.grid））{//console.log（stats（newgrid，ai.grid））ai.grid=新网格；尝试{兰特（ai网格）ai.步骤++；}捕获（e）{控制台日志（“无房间”，e）}}}函数预测（ai）{var free=freeCells（ai.grid）；ai.depth=自由>7？1：（自由>4？2：3）；var-root={path:[]，prob:1，grid:ai.grid，childs:[]}；var x=expandMove（根，ai）//console.log（“叶数”，x）//console.log（“叶数2”，countLeaves（根））if（！root.childres.length）返回nullvar values=root.childres.map（expectimax）；var mx=最大值；return root.childrens[mx[1]].path[0]}函数countLeaves（节点）{变量x=0；if（！node.childres.length）返回1；for（node.childs的var n）x+=叶数（n）；返回x；}函数预期值（节点）{if（！node.childres.length）{返回node.score}其他{var values=node.childres.map（expectimax）；如果（node.prob）{//我们处于最大节点return Math.max.apply（空，值）}否则｛//我们处于随机节点var平均值=0；对于（var i=0；i<values.length；i++）avg+=节点.子项[i].prob*值[i]返回平均值/（values.length/2）}}}函数expandRandom（节点，ai）{变量x=0；对于（var i=0；i<node.grid.length；i++）对于（var j=0；j<node.grid.length；j++）if（！node.grid[i][j]）{var grid2=M.copy（node.grid），grid4=M.copy（node.grid）；网格2[i][j]=2；网格4[i][j]=4；var child2=｛grid:grid2，prob:.9，path：node.path，childs:[]｝；var child4=｛grid:grid4，prob:.1，path：node.path，childs:[]｝node.childres.push（child2）node.childres.push（child4）x+=expandMove（child2，ai）x+=expandMove（child4，ai）}返回x；}函数expandMove（node，ai）｛//node＝｛grid，path，score｝var isLeaf=真，x=0；如果（节点路径长度小于ai深度）{for（变量移动[0，1，2，3]）{var grid=mv（移动，node.grid）；if（！equal（grid，node.grid））{isLeaf=false；var child=｛grid:grid，path:node.path.contat（[move]），childs:[]｝node.childres.push（child）x+=expandRandom（子级，ai）}}}if（isLeaf）node.score=dot（ai.weights，stats（node.grid））return是Leaf？1:x；}var单元格=[]var table=document.querySelector（“table”）；对于（变量i=0；i<n；i++）{var tr=document.createElement（“tr”）；单元格[i]=[]；对于（变量j=0；j<n；j++）{cells[i][j]=document.createElement（“td”）；tr.appendChild（单元格[i][j]）}table.appendChild（tr）；}函数更新UI（ai）{cells.forEach（函数（a，i）{a.forEach（函数（el，j）{el.innerHTML=ai.grid[i][j]| |“”})});}更新UI（ai）；updateHint（预测（ai））；函数runAI（）{var p=预测（ai）；如果（p！=null&&ai.running）{移动（p，ai）；更新UI（ai）；updateHint（p）；requestAnimationFrame（runAI）；}}runai.onclick=函数（）{if（！ai.running）{this.innerHTML=“停止AI”；ai.running=真；runAI（）；}其他{this.innerHTML=“运行AI”；ai.running=false；updateHint（预测（ai））；}}函数updateHint（dir）{hintvalue.innerHTML=['↑', '→', '↓', '←'][目录]| |“”；}document.addEventListener（“keydown”，函数（事件）{if（！event.target.matches（'.r*'））返回；event.prpreventDefault（）；//避免滚动if（地图中的event.which）{移动（map[event.with]，ai）console.log（stats（ai.grid））更新UI（ai）；updateHint（预测（ai））；}})变量映射={38:0，//以上39:1，//右40:2，//向下37:3，//左};init.onclick=函数（）{初始化（ai）；更新UI（ai）；updateHint（预测（ai））；}函数统计信息（网格，previousGrid）{var free=freeCells（网格）；var c=dot2（网格，蛇）；返回[c，free*free]；}函数dist2（a，b）{//2D距离的平方返回Math.pow（a[0]-b[0]，2）+Math.pow（a[1]-b[1]，2）}功能点（a，b）{变量r=0；对于（var i=0；i<a.length；i++）r+=a[i]*b[i]；返回r}函数dot2（a，b）{变量r=0；对于（var i=0；i<a.length；i++）对于（变量j=0；j<a[0].length；j++）r+=a[i][j]*b[i][j]返回r；}函数积（a）{return a.reduce（函数（v，x）{返回v*x}, 1)}函数maxValue（网格）{return Math.max.apply（null，grid.map（函数（a）{return Math.max.apply（null，a）}));}无功能单元格（网格）{返回grid.reduce（函数（v，a）{返回v+a.reduce（函数（t，x）{返回t+（x==0）}, 0)}, 0)}函数max（arr）{//返回max的[value，index]var m=[-无限，空]；对于（变量i=0；i<arr.length；i++）{如果（arr[i]>m[0]）m=[arr[i]，i]；}返回m}函数min（arr）{//返回min的[value，index]var m=[无限，空]；对于（变量i=0；i<arr.length；i++）{如果（arr[i]<m[0]）m=[arr[i]，i]；}返回m}函数maxScore（节点）{变量最小值={分数：-无限，路径：[]};for（节点的var节点）{如果（node.score>min.score）min=节点；}
