algorithm - vari - 什么是2048年游戏的最佳算法?




2048算法 (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)

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

我最近偶然发现了2048的比赛。 通过在四个方向中的任何一个方向移动它们来合并类似的瓷砖以制作“更大”的瓷砖。 每次移动后,一个新的贴图出现在随机空位上,值为24 。 当所有方块都被填满并且没有可以合并方块的移动时,游戏就会终止,或者您创建一个值为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
}

我所做的是在任何时候,我会尝试将瓦片与值24合并,也就是说,尽量使用24瓦片。 如果我以这种方式尝试,所有其他瓷砖都会自动合并,并且策略看起来不错。

但是,当我实际使用这种算法时,在游戏结束之前我只能获得4000点左右。 AFAIK的最大分数略高于20,000点,比我目前的分数要大得多。 有没有比上述更好的算法?


编辑:这是一个天真的算法,建模人类有意识的思维过程,并得到非常薄弱的​​结果相比,人工智能,搜索所有可能性,因为它只看起来前面一块。 它在响应时间表早期提交。

我已经完善了算法并打败了游戏! 它可能会失败,因为接近尾声的简单运气不好(你不得不向下移动,这是你永远不应该做的,并且一个贴片会出现在你的最高位置),只要保持最上面一行被填满,向左移动不会打破模式),但基本上你最终有一个固定的部分和移动部分玩。 这是你的目标:

这是我默认选择的模型。

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

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


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.


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

我使用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.人工智能从来没有失败过2048平铺(所以它从未在100场比赛中输过一次)。 实际上,它在每次运行中至少实现了8192个瓦片!

以下是最佳运行的截图:

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

履行

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

位移操作用于提取单独的行和列。 单行或列是16位数量,因此65536大小的表可以编码在单个行或列上操作的转换。 例如,移动被执行为4次查找到预先计算的“移动效果表”中,该表格描述每个移动如何影响单个行或列(例如,“移动右侧”表包含条目“1122 - > 0023”当移动到右侧时,行[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(即不使用诸如投票或撤消等工具)。 我认为65536瓦片是可及的!

你可以尝试自己的AI。 该代码可在https://github.com/nneonneo/2048-ai


我在这里复制我的博客上的一篇文章的内容

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

算法

启发式评分算法

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

(如果4-tile是随机生成的而不是2-tile在需要的时候有可能达到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的4096个瓦片 42000

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


我是其他人在此主题中提到的AI程序的作者。 您可以查看正在使用的AI或读取source

目前,该程序在我的笔记本电脑上的浏览器中获得了约90%的JavaScript胜率,并且每次移动的思考时间大约为100毫秒,所以虽然不完美(但!),但它表现相当不错。

由于游戏是一个离散的状态空间,完美的信息,像国际象棋和跳棋这样的基于回合的游戏,我使用了已被证明可以在这些游戏上运行的相同方法,即使用alpha-beta修剪进行 minimax search 。 由于已经有很多关于该算法的信息,所以我将仅讨论我在静态评估函数中使用的两种主要启发式,并将其他人在这里表达的许多直觉形式化。

单调性

这种启发式方法试图确保瓷砖的值沿着左/右和上/下方向都增加或减小。 单独的这种启发式捕捉许多其他人提到的直觉,认为更高价值的瓷砖应该聚集在一个角落。 它通常会防止价值较小的瓷砖变得孤立,并保持电路板非常有组织,而较小的瓷砖层叠并填充到较大的瓷砖中。

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

顺利

单独的上述启发式方法倾向于创建相邻的瓷砖价值降低的结构,但当然为了合并,相邻的瓷砖需要具有相同的价值。 因此,平滑启发式只是测量相邻区块之间的值差异,试图将此计数最小化。

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

这是一个完美平滑的网格截图,由这个优秀的模仿分岔提供

免费瓷砖

最后,免费磁贴太少会导致惩罚,因为当游戏板变得太狭窄时,选项可能会很快耗尽。

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

编辑:

这是这种方法的强大功能的演示。 我打开瓦片值(因此在达到2048之后保持不变),这是八次试验后的最佳结果。

是的,这是4096和2048一样。=)这意味着它在同一块电路板上实现了难以捉摸的2048瓦。


我的尝试使用expectimax像上面的其他解决方案,但没有位面板。 Nneonneo的解决方案可以检查1000万次移动,大约有4个移动深度,剩下6个移动块,并且可以移动4个移动(2 * 6 * 4) 4 。 在我的情况下,这个深度需要很长的时间去探索,我根据剩余的剩余砖块的数量调整了最后搜索的深度:

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>





2048