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

  显示原文与译文双语对照的内容

最近我发现了游戏 2048 。 通过在四个方向中移动相似的瓷砖,使它的成为"较大"平铺,可以合并相似的瓷砖。 每次移动后,一个新的平铺出现在随机的空位置,值为 2 或者 4 。 时与一个值则终止这个游戏的所有系统上都填满,没有任何的动作也能将瓷砖,或者你创建一个 tile.

首先,我需要遵循一个明确定义的策略来达到目标。 所以,我想为它写一个程序。

我当前的算法:


while (!game_over) {
 for each possible move:
 count_no_of_merges_for_2-tiles and 4-tiles
 choose the move with large number of merges
}

我是在做什么,在任何时候,我会试着将瓷砖与值 24,也就是说,我试图拥有 2 和合并 4 瓦,尽可能最小。 如果我这样尝试的话,所有其他的瓦片都会自动合并,策略看起来很好。

但是,当我实际使用这个算法时,我只在游戏终止前绕过 4000点。 最大点) 就我所知是稍微多于 20,000点哪个,要远远大于我的目前的分数。 是否有比上更好的算法?

时间:

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

目前,实现该计划关于一个给定关于 100 90%赢了率在我的笔记本电脑上的浏览器提供了在浏览器中运行的每个举动,所以,尽管不完美( 还还还) 思考的时间毫秒以内它就会执行得还算不错 !

alpha-beta剪枝,由于这个游戏是一个离散状态空间,完全信息博弈,turn-based喜欢下国际象棋或者西洋跳棋,我使用同样的方法,这些方法已经被证明是可行的在那些游戏,即极大极小搜索. 既然已经有很多关于这个算法的信息,我将讨论我在静态评估函数中使用的两个主要启发,以及其他人在这里表示的许多直觉。

单调性

这个启发式的尝试试图确保瓷砖的值都是沿着左/右和向上/下方向递增或者递减。 在一个corner,这个试探一个人抓住了直觉一样,还有很多人提到的,那么更高价值砖应该 clustered. 在和充填成tiles,越大,它通常会与较小的瓷砖cascading.防止较小的尊贵瓷砖变得孤立和利益,董事会非常有组织的,

下面是一个非常单调的网格的截图。 我通过运行带有eval函数集的算法来获得这个结果,而忽略了其他启发式算法。

A perfectly monotonic 2048 board

平滑度

上述启发一个人倾向于创建结构,其中相邻板块正在下降值,但是当然为了合并中,相邻板块需要将相同的值。 因此,平滑度启发只是衡量相邻瓦片之间的值差异,试图最小化这个计数。

关于黑客新闻的评论给了一个有趣的形式化的关于图论的概念。

这里是个截屏,提供的一个完全光滑网格代码这个出色的港片叉

A perfectly smooth 2048 board

免费瓦片

最后,有一个大代价让闲的瓷砖,因为选项太少可以迅速地耗尽如果游戏面板太过局促。

就是这样在优化这些条件的同时搜索游戏空间会产生非常好的性能。 使用这种方法而不是显式编码的移动策略的一个优点是,该算法通常可以找到有趣的和意想不到的解决方案。 如果你看它运行,它常常会做出令人惊讶而有效的行动,像突然开关,它是墙或者角,则在于建立起对抗。

编辑:

这里展示了这种方法的威力。 我把瓷砖的值加了上限,这是经过八个试验后最好的结果。

4096

是,在一个 4096旁边是一个。 = ) 这意味着它在同一块板上实现了难以捉摸的2048次平铺。

:这是一个幼稚的算法,模仿人类有意识的思维过程,与搜索所有可能性的人工智能相比,结果非常微弱。 它在响应时间线的早期提交。

我改进了算法并击败了游戏 ! 它可能失败,由于简单的运气不佳关闭到结束( 你被迫下移,这你绝对不应该做的,和一个平铺位置出现你的最高的应该是。 带有已经填充,只需尽量保持最上面一行,所以向左移动并没有钱以能够将打破这种模式),但基本上,你最终会拥有一个固定部分和移动部来玩 这是你的目标:

Ready to finish

这是我默认选择的模型。


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

关于缺失步骤的几点指针。 这里: 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

我在博客中复制了帖子的内容


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

Score

算法

启发式评分算法

我的算法基于的假设非常简单: 如果你想获得更高的分数,棋盘必须尽可能保持整洁。 特别是,最佳设置是由平铺值的线性和单调递减顺序给出的。 这个直觉将给你一个平铺值的上限: s 其中n 是棋盘上的瓷砖数。

( 还有一个可能性,以到达 131072瓷砖如果 4 -tile是随机生成的,而不是该 2 -tile在需要时)

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

enter image description here

为了在单调递减顺序中强制平铺,将分数计算为棋盘上线性值的总和乘以具有共同比率的几何序列的值 R <1.

s

s

可以一次计算多个线性路径,最终得分将是任何路径的最大得分。

决策规则

实现的决策规则不太明智,这里给出了 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的实现肯定会改进算法。 显然一个更复杂的决策规则会降低算法的速度,它需要一些时间,implemented.I 会在不久的将来尝试一个极小的实现。 ( 保持调谐)

基准

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

enter image description hereenter image description hereenter image description hereenter image description here

一个平均得分of,在用例为时刻,四项考试成的生成 4096瓷砖 s 42000

代码

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

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

算法


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)

 

这是一个常量,用作base-line和其他用于测试的工具。


+ (Number of Spaces x 128)

更多的空间使得状态更加灵活,我们乘以 128 ( 这是中间的),因为一个充满 128面的网格是一个最佳的不可能状态。


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

在这里,我们评估有可能合并的面,通过计算 backwardly,平铺 2变为值 2048,而平铺 2048计算 2.


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

在这里,我们仍然需要查看是否有堆积,但另一方面,在输入一个更低的不中断的灵活性参数值,因此我们有 { x的总和在 [4,44] }.


+ (Number of possible next moves x 256)

如果状态具有更多可能的转换自由度,则状态更加灵活。


+ (Number of aligned values x 2)

这是一个简化的检查,它可以在这种状态下合并,而不需要 look-ahead 。

注意:常数可以调整。

这里游戏已经有一个AI实现: 这里的 。摘自自述文件:

算法是迭代深化深度优先alpha-beta搜索。 评估函数试图使行和列保持单调的( 要么全部减少要么增加),同时最小化网格上的瓦片数。

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

我在Haskell中写了一个 2048解算器,主要是因为我现在正在学习这种语言。

我的游戏实现与实际游戏略有不同,因为一个新的磁贴总是一个'2'( 而不是 90% 2和 10% 4 ) 。 新的瓷砖不是随机的,但总是第一个可用的。

因此,这个规划求解是确定性的。

我使用了一个穷举算法,它支持空瓦片。 在一个围绕 1二/move,它执行会很快对于深度 1 -4深度 5上,但它变得相当慢了,

下面是实现求解算法的代码。 网格表示为 16 -length数组的整数。 计分是通过计算空方块的数量来完成的。


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

我的尝试使用expectimax和上面的解决方案一样,但没有 bitboards 。 nneonneo的解可以看 10数百万移动时,为大约为与 6 4瓷砖向左移,4就可能的深度( 2*6*4 ) 4 在我的例子中,这个深度太长了,我根据剩余的可用瓦片数调整expectimax搜索深度:


depth = free> 7? 1 : (free> 4? 2 : 3)

得分做板,已经计算出的加权数的平方之和最小自由分幅和的点积 2 D 网格与这里:


[[10,8,7,6.5],
 [.5,.7,1,3],
 [-.5,-1.5,-1.8,-2],
 [-3.8,-3.7,-3.5,-3]]

哪种力量将瓷砖descendingly组织为从左上角平铺的蛇。

下面的代码或者 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>
...