2048游戏的最佳算法是什么？

Question

我最近偶然发现了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的最高分数略高于20,000分,远高于我目前的分数.有比上面更好的算法吗？

Answer 1

我是其他人在这个帖子中提到的AI程序的作者.您可以查看AI 实际操作或阅读源代码.

目前,该程序在我的笔记本电脑上的浏览器中以javascript运行大约90%的赢率,每次移动大约有100毫秒的思考时间,所以虽然不完美(还是!)但它的表现相当不错.

由于游戏是一个离散的状态空间,完美的信息,基于回合制的游戏,如国际象棋和棋子,我使用了相同的方法,这些方法已被证明适用于那些游戏,即使用alpha-beta修剪的minimax 搜索.由于那里已经有很多关于该算法的信息,我将简单地讨论我在静态评估函数中使用的两个主要启发式方法,并且描述了其他人在此处表达的许多直觉.

单调性

该启发式尝试确保瓦片的值沿左/右和上/下方向都增加或减少.这种启发式捕获了许多其他人提到的直觉,即更高价值的瓷砖应该聚集在一个角落里.它通常会阻止较小的有价值的瓷砖变得孤立,并使电路板非常有条理,较小的瓷砖层叠并填充到较大的瓷砖中.

这是完美单调网格的屏幕截图.我通过运行算法并使用eval函数设置来忽略其他启发式算法并且仅考虑单调性来获得此结果.

顺利

上述启发式单独倾向于创建其中相邻瓦片的值减小的结构,但是当然为了合并,相邻瓦片需要是相同的值.因此,平滑度启发式测量仅测量相邻图块之间的值差异,尝试最小化此计数.

一位关于黑客新闻的评论者用图论对这个想法进行了有趣的形式化.

这是一个非常流畅的网格的截图,由这个优秀的模仿叉子提供.

免费瓷砖

最后,由于游戏牌太过狭窄,选项很快就会耗尽,因此免费牌位太少会受到惩罚.

就是这样!在优化这些标准的同时搜索游戏空间会产生非常好的性能.使用这样的通用方法而不是明确编码的移动策略的一个优点是该算法通常可以找到有趣且意想不到的解决方案.如果你观看它的运行,它往往会产生令人惊讶但有效的动作,比如突然切换它所构建的墙壁或角落.

编辑:

这是对这种方法的力量的演示.我打开了瓷砖值(所以它在达到2048后继续运行),这是8次试验后的最佳结果.

是的,这是2096年的4096. =)这意味着它在同一块板上实现了三次难以捉摸的2048瓦片.

Answer 2

我使用expectimax优化开发了2048 AI ,而不是@ ovolve算法使用的minimax搜索.AI简单地对所有可能的移动执行最大化,然后对所有可能的瓦片生成进行预期(通过瓦片的概率加权,即4的10%和2的90%).据我所知,不可能修剪expectimax优化(除了删除非常不可能的分支),因此使用的算法是经过仔细优化的强力搜索.

性能

默认配置中的AI(最大搜索深度为8)需要10ms到200ms才能执行移动,具体取决于电路板位置的复杂程度.在测试中,AI在整个游戏过程中实现了每秒5-10次移动的平均移动速度.如果搜索深度限制为6次移动,AI可以轻松地每秒执行20次以上移动,这使得观看有趣.

为了评估AI的得分表现,我运行了100次AI(通过遥控器连接到浏览器游戏).对于每个图块,以下是至少一次实现该图块的游戏比例:

2048: 100%
4096: 100%
8192: 100%
16384: 94%
32768: 36%

所有运行的最低分数是124024; 获得的最高分为794076.中位数为387222. AI从未获得2048牌(因此在100场比赛中它甚至没有输过一场比赛); 事实上,它在每次运行中至少实现了8192个瓷砖!

这是最佳运行的屏幕截图:

这场比赛在96分钟内完成了27830次移动,平均每秒移动4.8次.

履行

我的方法将整个板(16个条目)编码为单个64位整数(其中tile是nybbles,即4位块).在64位计算机上,这使得整个电路板可以在一个机器寄存器中传递.

位移操作用于提取单个行和列.单个行或列是16位数量,因此大小为65536的表可以编码对单个行或列进行操作的转换.例如,移动被实现为4个查找到预先计算的"移动效果表",其描述每个移动如何影响单个行或列(例如,"向右移动"表包含条目"1122 - > 0023",描述如何row [2,2,4,4]在向右移动时变为行[0,0,4,8].

使用表查找也可以完成评分.这些表包含在所有可能的行/列上计算的启发式分数,并且板的结果分数只是每行和每列的表值的总和.

该板表示以及用于移动和评分的表查找方法允许AI在短时间内搜索大量游戏状态(在我2011年中期的笔记本电脑的一个核心上每秒超过10,000,000个游戏状态).

expectimax搜索本身被编码为递归搜索,其在"期望"步骤(测试所有可能的瓦片生成位置和值,并通过每种可能性的概率加权其优化得分)和"最大化"步骤(测试所有可能的移动)之间交替.并选择得分最高的那个).树搜索在看到先前看到的位置(使用转置表),达到预定义的深度限制时,或者当它达到极不可能的板状态时(例如,通过获得6"4"瓦片达到)终止从起始位置开始连续).典型的搜索深度为4-8个移动.

启发式

使用几种启发法将优化算法指向有利位置.启发式的精确选择对算法的性能有很大影响.各种启发式方法被加权并组合成位置分数,该分数确定给定的板位置的"好"程度.然后,优化搜索将旨在最大化所有可能的董事会职位的平均分数.如游戏所示,实际得分不用于计算董事会得分,因为它的权重太大而有利于合并磁贴(当延迟合并可能产生很大的好处时).

最初,我使用了两个非常简单的启发式方法,为空心方块和边缘上的大值赋予"奖励".这些启发式表现相当不错,经常达到16384但从未达到32768.

PetrMorávek(@xificurk)接受了我的AI并添加了两个新的启发式方法.第一种启发式方法是对非单调行和列进行惩罚,随着等级的增加而增加,确保非单调的小数行不会对分数产生强烈影响,但非单调的大数行会大大损害分数.除了开放空间之外,第二个启发式算法计算了潜在合并的数量(相邻的相等值).这两种启发式方法有助于将算法推向单调板(更容易合并),并朝向具有大量合并的板位置(鼓励它在可能的情况下对齐合并以获得更大的效果).

此外,Petr还使用"元优化"策略(使用称为CMA-ES的算法)优化启发式权重,其中权重本身被调整以获得尽可能高的平均分数.

这些变化的影响非常显着.该算法从大约13%的时间实现16384瓦片到90%以上的时间实现它,并且算法在1/3的时间内开始达到32768(而旧的启发式方法从未生成32768瓦片) .

我相信启发式方法仍有改进的余地.这个算法肯定还不是"最优",但我觉得它已经非常接近了.

人工智能在超过三分之一的游戏中实现32768瓦片是一个巨大的里程碑; 如果任何人类玩家在官方游戏中获得32768(即不使用像savestates或撤消等工具),我会感到惊讶.我认为65536瓷砖是触手可及的!

你可以亲自试试AI.该代码可在https://github.com/nneonneo/2048-ai获得.

Answer 3

我对这个游戏的AI想法感兴趣,这个游戏不包含硬编码智能(即没有启发式,评分功能等).AI应该"只知道"游戏规则,并"弄清楚"游戏玩法.这与大多数AI(如本线程中的那些)形成鲜明对比,其中游戏玩法基本上是由表示人类对游戏的理解的评分函数引导的蛮力.

AI算法

我发现了一个简单但令人惊讶的好玩法:为了确定给定棋盘的下一步动作,AI使用随机动作在游戏中玩游戏,直到游戏结束.这样做了几次,同时跟踪最终比赛得分.然后计算每次开始移动的平均最终得分.选择具有最高平均最终得分的起始移动作为下一步行动.

每次移动仅运行100次(即在记忆游戏中),AI在80%的时间内达到2048瓦,在50%的时间内达到4096瓦.使用10000次运行获得2048瓦100%,4096瓦的70%,以及8192瓦的约1%.

看到它在行动

获得的最佳成绩如下所示:

关于这个算法的一个有趣的事实是,虽然随机游戏不足为奇,但选择最好的(或最不好的)移动会带来非常好的游戏玩法:典型的AI游戏可以达到70000点并持续3000次移动,但是来自任何给定位置的记忆内随机游戏在死亡前的大约40次额外移动中平均产生340个额外点.(您可以通过运行AI并打开调试控制台来自行查看.)

此图表说明了这一点:蓝线显示每次移动后的董事会得分.红线显示该算法从该位置获得的最佳随机游戏结束分数.本质上,红色值将蓝色值"向上"拉向它们,因为它们是算法的最佳猜测.有趣的是,红线在每个点的蓝线上方稍微高一点,但蓝线继续增加越来越多.

我觉得非常令人惊讶的是,该算法并不需要实际预见好游戏才能选择产生它的动作.

稍后搜索我发现该算法可能被归类为纯蒙特卡罗树搜索算法.

实施和链接

首先,我创建了一个JavaScript版本,可以在这里看到.这个版本可以在适当的时间内运行100次.打开控制台以获取额外信息.(来源)

后来,为了更多地使用@nneonneo高度优化的基础架构并在C++中实现我的版本.如果你有耐心,这个版本允许每次移动最多100000次运行甚至1000000次运行.提供建筑说明.它在控制台中运行,并且还具有远程控制以播放Web版本.(来源)

结果

令人惊讶的是,增加跑步次数并没有大幅提升比赛效果.这个策略似乎有一个限制,大约80000点,4096瓦和所有较小的瓦,非常接近实现8192瓦.将运行次数从100增加到100000会增加达到此分数限制的几率(从5%到40%),但不能突破它.

在关键位置附近运行10000次运行并暂时增加到1000000,设法打破此障碍,不到1%的时间达到最大分数129892和8192瓦.

改进

实现此算法后,我尝试了许多改进,包括使用最小或最大分数,或min,max和avg的组合.我也试过使用深度:我没有尝试每次移动K次,而是尝试了每次移动的K个移动列表(例如"向上,向上,向左")并选择最佳得分移动列表的第一步.

后来我实施了一个评分树,该树考虑了在给定移动列表之后能够进行移动的条件概率.

然而,这些想法都没有比简单的第一个想法显示出任何真正的优势.我把这些想法的代码留在了C++代码中.

我确实添加了一个"深度搜索"机制,当任何一次运行意外到达下一个最高的磁贴时,它会暂时将运行次数增加到1000000.这提供了时间的改善.

我很想知道是否有人有其他改进想法来保持AI的域独立性.

2048变种和克隆

只是为了好玩,我还将AI作为书签实现,挂钩游戏的控件.这允许AI与原始游戏及其许多变体一起使用.

由于AI的域独立性,这是可能的.一些变体是非常不同的,例如六角形克隆.

Answer 4

编辑:这是一个天真的算法,对人类有意识的思维过程进行建模,与人工智能相比,搜索所有可能性的结果非常微弱,因为它只能看到前方的一个区块.它是在响应时间表的早期提交的.

我已经改进了算法并击败了游戏!它可能会因为接近末尾的简单运气而失败(你被迫向下移动,你永远不应该这样做,并且一个瓷砖出现在你应该最高的地方.只是试着保持顶行填充,所以向左移动不会打破模式),但基本上你最终有一个固定的部分和一个移动部分来玩.这是你的目标:

这是我默认选择的模型.

1024 512 256 128
  8   16  32  64
  4   2   x   x
  x   x   x   x

选择的角落是任意的,你基本上从不按一个键(禁止移动),如果你这样做,你再次按相反的方法并尝试修复它.对于将来的图块,模型总是希望下一个随机图块为2,并显示在当前模型的另一侧(第一行不完整,右下角,第一行完成后,左下角)角).

这是算法.大约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)
  }

关于缺失步骤的一些指示.这里:

由于靠近预期模型的运气,模型已经改变.AI试图实现的模型是

 512 256 128  x
  X   X   x   x
  X   X   x   x
  x   x   x   x

到达那里的链条已成为:

 512 256  64  O
  8   16  32  O
  4   x   x   x
  x   x   x   x

该O代表禁止的空间...

所以它会向右按,然后向右按,然后(向右或向上取决于4创建的位置)然后将继续完成链直到它得到:

所以现在模型和链回到:

 512 256 128  64
  4   8  16   32
  X   X   x   x
  x   x   x   x

第二个指针,它已经运气不好,其主要地点已被采取.它可能会失败,但它仍然可以实现它:

这里的模型和链是:

  O 1024 512 256
  O   O   O  128
  8  16   32  64
  4   x   x   x

当它设法达到128时,它会再次获得一整行:

  O 1024 512 256
  x   x  128 128
  x   x   x   x
  x   x   x   x

Answer 5

我在这里复制了我博客上帖子的内容

我提出的解决方案非常简单,易于实现.虽然,它已达到131040的分数.提出了算法性能的几个基准.

算法

启发式评分算法

我的算法所基于的假设相当简单:如果你想获得更高的分数,董事会必须保持尽可能整洁.特别地,最佳设置由瓦片值的线性和单调递减顺序给出.这种直觉也会给你一个tile值的上限: 其中n是电路板上的瓷砖数量.

(如果需要随机生成4个图块而不是2个图块,则有可能到达131072图块)

组织电路板的两种可能方式如下图所示:

为了以单调递减顺序强制执行瓦片的排序,将得分si计算为板上线性化值的总和乘以具有公共比率r <1的几何序列的值.

可以一次评估几个线性路径,最终得分将是任何路径的最高得分.

决策规则

实现的决策规则不是很聪明,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的实现肯定会改进算法.显然,更复杂的决策规则会降低算法速度,并且需要一些时间来实现.我将在不久的将来尝试实现minimax.(敬请关注)

基准

• T1 - 121测试 - 8种不同的路径 - r = 0.125
• T2 - 122测试 - 8个不同的路径 - r = 0.25
• T3 - 132测试 - 8种不同的路径 - r = 0.5
• T4 - 211测试 - 2个不同的路径 - r = 0.125
• T5 - 274次测试 - 2种不同的路径 - r = 0.25
• T6 - 211测试 - 2个不同的路径 - r = 0.5

在T2的情况下,十个中的四个测试产生4096个平铺,平均得分为 42000

码

代码可以在GiHub上的以下链接中找到:https://github.com/Nicola17/term2048-AI 它基于term2048,它是用Python编写的.我将尽快在C++中实现更高效的版本.

Answer 6

我尝试使用expectimax像上面的其他解决方案,但没有位板.Nneonneo的解决方案可以检查1000万次移动,大约深度为4,剩下6个瓷砖,4个移动可能(2*6*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上的代码:

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);
updateHint(predict(ai));

function runAI() {
	var p = predict(ai);
	if (p != null && ai.running) {
		move(p, ai);
		updateUI(ai);
		updateHint(p);
		requestAnimationFrame(runAI);
	}
}
runai.onclick = function() {
	if (!ai.running) {
		this.innerHTML = 'stop AI';
		ai.running = true;
		runAI();
	} else {
		this.innerHTML = 'run AI';
		ai.running = false;
		updateHint(predict(ai));
	}
}


function updateHint(dir) {
	hintvalue.innerHTML = ['?', '?', '?', '?'][dir] || '';
}

document.addEventListener("keydown", function(event) {
	if (!event.target.matches('.r *')) return;
	event.preventDefault(); // avoid scrolling
	if (event.which in map) {
		move(map[event.which], ai)
		console.log(stats(ai.grid))
		updateUI(ai);
		updateHint(predict(ai));
	}
})
var map = {
	38: 0, // Up
	39: 1, // Right
	40: 2, // Down
	37: 3, // Left
};
init.onclick = function() {
	initialize(ai);
	updateUI(ai);
	updateHint(predict(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 {
	font-family: Arial;
}
table, th, td {
	border: 1px solid black;
	margin: 0 auto;
	border-collapse: collapse;
}
td {
	width: 35px;
	height: 35px;
	text-align: center;
}
button {
	margin: 2px;
	padding: 3px 15px;
	color: rgba(0,0,0,.9);
}
.r {
	display: flex;
	align-items: center;
	justify-content: center;
	margin: .2em;
	position: relative;
}
#hintvalue {
	font-size: 1.4em;
	padding: 2px 8px;
	display: inline-flex;
	justify-content: center;
	width: 30px;
}

<table title="press arrow keys"></table>
<div class="r">
    <button id=init>init</button>
    <button id=runai>run AI</button>
    <span id="hintvalue" title="Best predicted move to do, use your arrow keys" tabindex="-1"></span>
</div>

Answer 7

我是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磁贴.

Answer 8

我认为我找到了一个效果很好的算法,因为我经常达到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);
}

Answer 9

已经有一个AI实现这个游戏在这里.摘自README:

该算法是迭代加深深度的第一个alpha-beta搜索.评估函数尝试使行和列保持单调(全部减少或增加),同时最小化网格上的图块数量.

还有一篇关于黑客新闻的讨论,你可能会觉得这个算法很有用.

Answer 10

算法

while(!game_over)
{
    for each possible move:
        evaluate next state

    choose the maximum 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)

评估细节

128 (Constant)

这是一个常量,用作基线和其他用途,如测试.

+ (Number of Spaces x 128)

更多的空间使状态更灵活,我们乘以128(这是中位数),因为填充128个面的网格是最佳的不可能状态.

+ Sum of faces adjacent to a space { (1/face) x 4096 }

在这里,我们评估有可能进行合并的面部,通过向后评估它们,图块2变为值2048,而图块2048被评估为2.

+ Sum of other faces { log(face) x 4 }

在这里,我们仍然需要检查堆栈值,但是以较小的方式不会中断灵活性参数,因此我们得到{x in [4,44]}的总和.

+ (Number of possible next moves x 256)

如果一个州有更多的可能过渡自由,那么它就更灵活.

+ (Number of aligned values x 2)

这是对在该状态下进行合并的可能性的简化检查,而不进行预测.

注意:常量可以调整..

Answer 11

这不是OP问题的直接答案,这是我迄今为止尝试解决相同问题并获得一些结果并且有一些我想分享的观察的更多东西(实验),我很好奇我们是否可以拥有一些进一步的见解.

我刚尝试使用alpha-beta修剪我的minimax实现,搜索树深度截止分别为3和5.我试图为4x4网格解决同样的问题作为edX课程的项目任务ColumbiaX:CSMM.101x人工智能( AI).

我应用了几个启发式评估函数的凸组合(尝试了不同的启发式权重),主要来自直觉和上面讨论的:

1. 单调性
2. 可用空间

在我的情况下,计算机播放器是完全随机的,但我仍然假设对抗设置并将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-与电脑游戏/和youtube视频:https://www.youtube.com/watch？v = VnVFilfZ0r4)

下面的动画显示了游戏的最后几个步骤,其中AI玩家代理可以获得2048分,这次添加绝对值启发式:

下图显示了玩家AI代理人探索的游戏树,假设计算机只是一个步骤的对手:

Answer 12

我在Haskell写了一个2048求解器,主要是因为我现在正在学习这门语言.

我对游戏的实现与实际游戏略有不同,因为新的牌总是'2'(而不是90%2和10%4).并且新的图块不是随机的,但始终是左上角的第一个可用图块.这种变体也称为Det 2048.

因此,这个解算器是确定性的.

我使用了一种有利于空瓷砖的详尽算法.对于深度1-4,它执行得相当快,但是在深度5上,每次移动大约1秒时变得相当慢.

下面是实现求解算法的代码.网格表示为16个长度的整数数组.简单地通过计算空方格的数量来完成评分.

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] ]

我认为它的简单性非常成功.从空网格开始并在深度5处求解时达到的结果是:

Move 4006
[2,64,16,4]
[16,4096,128,512]
[2048,64,1024,16]
[2,4,16,2]

Game Over

源代码可以在这里找到:https://github.com/popovitsj/2048-haskell

Answer 13

这种算法不是赢得游戏的最佳选择,但在性能和所需代码量方面它是相当优化的:

  if(can move neither right, up or down)
    direction = left
  else
  {
    do
    {
      direction = random from (right, down, up)
    }
    while(can not move in "direction")
  }