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

我是其他人在这个帖子中提到的AI程序的作者。你可以在中查看AI 行动 或阅读 资源。

目前，该程序在我的笔记本电脑上的浏览器中使用javascript运行大约90％的赢率，每次移动大约有100毫秒的思考时间，所以虽然不完美（但是！）它表现相当不错。

由于游戏是一个离散的状态空间，完美的信息，像国际象棋和棋子这样的回合制游戏，我使用的方法已被证明适用于那些游戏，即 极小  搜索 同 alpha-beta修剪。由于那里已经有很多关于那个算法的信息，我只想谈谈我在这个算法中使用的两个主要的启发式方法。 静态评估功能 并且正式化了其他人在这里表达的许多直觉。

单调性

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

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

顺利

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

黑客新闻的评论者给了 一个有趣的形式化 这个想法在图论方面。

这是一个完美平滑网格的截图，礼貌 这个优秀的模仿叉子。

免费瓷砖

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

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

编辑：

以下是这种方法的强大功能。我打开了瓷砖值（所以它在达到2048后继续运行），这是八次试验后的最佳结果。

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

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

我已经改进了算法并击败了游戏！它可能会因为接近末尾的简单坏运而失败（你被迫向下移动，你永远不应该这样做，而且你的最高点应该出现在你的最高位置。只是尽量保持顶行填充，所以向左移动不会打破模式），但基本上你最终有一个固定的部分和一个移动部分来玩。这是你的目标：

这是我默认选择的模型。

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

我开始对包含这个游戏的人工智能的想法感兴趣 没有硬编码的情报 （即没有启发式，评分功能等）。 AI应该 “知道” 只有游戏规则，和 “弄清楚” 游戏。这与大多数AI（如本线程中的那些）相反，其中游戏玩法基本上是由表示人类对游戏的理解的评分函数引导的强力。

AI算法

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

每次移动仅运行100次（即在记忆游戏中），AI在80％的时间内达到2048瓦，在50％的时间内达到4096瓦。使用10000次运行获得2048瓦100％，4096瓦的70％，以及8192瓦的约1％。

看到它在行动

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

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

此图表说明了这一点：蓝线显示每次移动后的董事会得分。红线表示算法 最好 该位置的随机结束比赛得分。从本质上讲，红色值是向上“拉”蓝色值，因为它们是算法的最佳猜测。有趣的是，红线在每个点的蓝线上方稍微高一点，但蓝线继续增加越来越多。

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

稍后搜索我发现这个算法可能被归类为a 纯蒙特卡罗树搜索 算法。

实施和链接

首先我创建了一个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的域独立性，这是可能的。一些变体是非常不同的，例如六角形克隆。

我在这里复制了一个内容 发布在我的博客上

我提出的解决方案非常简单，易于实现。虽然，它已达到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 ++中实现更高效的版本。

我尝试使用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]]

它迫使瓦片从左上方的瓦片中以一条蛇的形式下降。

代码如下或 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>

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

我是2048控制器的作者，该控制器的得分比该线程中提到的任何其他程序都要好。可以使用控制器的有效实现 github上。在 一个单独的回购 还有用于训练控制器状态评估功能的代码。训练方法在中描述 纸。

控制器使用expectimax搜索和状态评估功能，从头开始学习（没有人类2048专业知识）的变体 时差学习 （强化学习技巧）。状态值函数使用 n-tuple网络，这基本上是在电路板上观察到的模式的加权线性函数。它涉及的不仅仅是 10亿个重量， 总共。

性能

在1次/ s时： 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磁贴。

这个游戏已经有了一个AI实现： 这里。摘自README：

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

还有一个讨论 ycombinator 关于这个你可能觉得有用的算法。

算法

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)

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

注意：常量可以调整..