首页 文章

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

提问于
浏览 次
1792

我最近偶然发现了游戏2048 . 您可以通过在四个方向中的任何一个方向上移动它们来合并相似的图块，以制作"bigger"图块 . 每次移动后，新的图块会出现在随机空位置，其值为 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分，远高于我目前的分数 . 是否有比上述更好的算法？

algorithm logic artificial-intelligence 2048

14 回答

  • 1227

    我在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

    回复于
  • 4

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

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

    关于这个算法的ycombinator也有讨论，你可能会发现它很有用 .

    回复于
  • 27

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

    我刚尝试使用alpha-beta修剪我的minimax实现，搜索树深度截止为3和5.我试图解决4x4网格的相同问题，作为 edX course ColumbiaX: CSMM.101x Artificial Intelligence (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/）

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

    下面的数字显示了玩家AI代理人探索的 game tree ，假设计算机只是一个步骤的对手：

    回复于
  • 8

    这种算法并不是获胜的最佳选择游戏，但它在性能和所需代码量方面是相当优化的：

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

    我是其他人在这个帖子中提到的AI程序的作者 . 您可以在action中查看AI或阅读source .

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

    由于游戏是一个离散的状态空间，完美的信息，基于回合制的游戏，如国际象棋和棋子，我使用了相同的方法，这些方法已被证明适用于那些游戏，即minimax search与alpha-beta pruning . 由于那里已经有很多关于该算法的信息，我将只讨论我在_170704中使用的两个主要启发式方法，并将其他人在此处表达的许多直觉形式化 .

    单调性

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

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

    A perfectly monotonic 2048 board

    平滑

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

    黑客新闻的评论者根据图论给出了这个想法 .

    这是一个完美平滑网格的截图，由this excellent parody fork提供 .

    A perfectly smooth 2048 board

    免费瓷砖

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

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

    编辑：

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

    4096

    是的，这是2048年的4096. =）这意味着它在同一块板上三次获得难以捉摸的2048瓦 .

    回复于
  • 121

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

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

    代码如下或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>
    回复于
  • 90

    我是2048控制器的作者，该控制器的得分比该线程中提到的任何其他程序都要好 . github上提供了控制器的高效实现 . 在a separate repo中，还有用于训练控制器状态评估函数的代码 . 训练方法在paper中描述 .

    控制器使用expectimax搜索，通过 temporal difference learning （强化学习技术）的变体从头学习（没有人类2048专业知识）的状态评估函数 . 状态值函数使用 n-tuple network ，它基本上是在电路板上观察到的模式的加权线性函数 . 它总共涉及 1 billion weights 以上 .

    表现

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

    回复于
  • 21

    我在这里复制post on my blog的内容

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

    Score

    算法

    Heuristic scoring algorithm

    我的算法所依据的假设相当简单：如果你想获得更高的分数，董事会必须保持尽可能整洁 . 特别地，最佳设置由瓦片值的线性和单调递减顺序给出 . 这种直觉还会给出瓦片值的上限：
    s
    其中n是棋盘上的瓦片数 .

    （如果需要随机生成4个图块而不是2个图块，则有可能到达131072图块）

    以下图像显示了组织电路板的两种可能方式：

    enter image description here

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

    s

    s

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

    Decision rule

    实现的决策规则不是很聪明，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

    enter image description here

    enter image description here

    enter image description here

    enter image description here

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

    代码

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

    回复于
  • 1161

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

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

    Ready to finish

    这是我默认选择的模型 .

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

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

    这是算法 . 大约80％的胜利（似乎总是可以通过更多“专业”人工智能技术获胜，但我不确定这一点 . ）

    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)
  }

    关于缺失步骤的一些指示 . 这里：
    model change

    由于更接近预期模型的运气，模型已经改变 . 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创建的位置）然后将继续完成链直到它得到：

    Chain completed

    所以现在模型和链回到：

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

    第二个指针，它运气不好，其主要位置已被采取 . 它可能会失败，但它仍然可以实现它：

    Enter image description here

    这里的模型和链是：

    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
    回复于
  • 31

    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)

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

    + (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)

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

    注意：常量可以调整..

    回复于
  • 9

    很多其他的答案使用人工智能与可能的未来，启发式，学习等计算昂贵的搜索 . 这些令人印象深刻，可能是正确的前进方向，但我希望提出另一个想法 .

    模拟游戏中优秀玩家使用的策略 .

    例如：

    13 14 15 16
12 11 10  9
 5  6  7  8
 4  3  2  1

    按上面显示的顺序读取方块，直到下一个方块值大于当前值 . 这提出了尝试将具有相同值的另一个图块合并到该正方形中的问题 .

    为了解决这个问题，他们有2种移动方式，不会留下或者更糟糕，并且检查这两种可能性可能会立即揭示更多问题，这形成了一系列依赖关系，每个问题都需要首先解决另一个问题 . 我认为在决定我的下一步行动时，尤其是当卡住时，我会在内部拥有这个链条或某些情况下依赖树 .

    瓷砖需要与邻居合并，但太小：与另一个邻居合并 .

    方式中较大的瓷砖：增加较小的周围瓷砖的值 .

    等等...

    整个方法可能会比这更复杂，但不会复杂得多 . 这种机械感可能缺乏分数，重量，神经元和对可能性的深入探索 . 可能性的树木甚至需要足够大才能需要任何分支 .

    回复于
  • 2

    我开始对这个包含 no hard-coded intelligence （即没有启发式，评分函数等）的游戏的AI的想法感兴趣 . AI应该只是游戏规则，而游戏则是"figure out" . 这与大多数AI（如本线程中的那些）相反，其中游戏玩法基本上是由表示人类对游戏的理解的评分函数引导的强力 .

    AI算法

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

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

    See it in action

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

    best score

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

    此图表说明了这一点：蓝线显示每次移动后的董事会得分 . 红线显示该算法从该位置开始的随机运行结束游戏得分 best . 从本质上讲，红色值是向上朝向它们的蓝色值，因为它们是有趣的，看到红线在每个点的蓝线上方稍微有点，但蓝线继续增加更多，更多 .

    scoring graph

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

    稍后搜索我发现该算法可能被归类为Pure Monte Carlo Tree Search算法 .

    实施和链接

    首先，我创建了一个JavaScript版本，可以是seen in action here . 这个版本可以在适当的时间运行100次运行 . 打开控制台以获取额外信息 . （source）

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

    结果

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

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

    改进

    实现此算法后，我尝试了许多改进，包括使用最小或最大分数，或min，max和avg的组合 . 我也试过使用深度：我没有尝试每次移动K次运行，而是尝试了每次移动的K个移动列表（"up,up,left"，例子）并选择最佳得分移动列表的第一步 .

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

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

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

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

    2048变种和克隆

    只是为了好玩，我也是implemented the AI as a bookmarklet，挂钩游戏的控件 . 这允许AI与原始游戏和 many of its variants 一起使用 .

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

    回复于
  • 119

    我开发了一个使用expectimax优化的2048 AI，而不是@ovolve 's algorithm. The AI simply performs maximization over all possible moves, followed by expectation over all possible tile spawns (weighted by the probability of the tiles, i.e. 10% for a 4 and 90% for a 2). As far as I' m意识到的minimax搜索，不可能修剪expectimax优化（除了删除非常不可能的分支），因此使用的算法是经过精心优化的蛮力搜索 .

    表现

    默认配置中的AI（最大搜索深度为8）需要10ms到200ms才能执行移动，具体取决于电路板位置的复杂程度 . 在测试中，AI在整个游戏过程中实现了每秒5-10次移动的平均移动速度 . 如果搜索深度限制为6次移动，则AI可以轻松地每秒执行20次移动，这样可以实现一些interesting watching .

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

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

    所有运行的最低分数是124024;达到的最高分为794076.中位数为387222. AI从未获得2048牌（因此在100场比赛中它甚至没有输过一场比赛）;实际上，它在每次运行中至少实现了一次 8192 tile！

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

    32768 tile, score 794076

    这场比赛在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搜索本身被编码为递归搜索，它在"expectation"步之间交替（测试所有可能的瓦片生成位置和值，并根据每种可能性的概率对其优化得分进行加权），以及"maximization"步骤（测试所有可能的移动并选择一个步骤）得分最高） . 树搜索在看到先前看到的位置（使用transposition table），达到预定义的深度限制时，或者当它达到极不可能的板状态时终止（例如，通过连续获得6个"4"瓦片达到它）从起始位置） . 典型的搜索深度为4-8个移动 .

    启发式

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

    最初，我使用了两个非常简单的启发式方法，为空心方块和边缘上的大值赋予“奖励” . 这些启发式表演很好，经常达到16384但从未达到32768 .

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

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

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

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

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

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

    回复于
  • 26

    我认为我发现了一种效果很好的算法，因为我经常达到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);
}
    回复于

相关问题