¿Cuál es el algoritmo óptimo para el juego 2048?

Soy el autor del programa de IA que otros han mencionado en este hilo. Puede ver la IA en la acción o leer la fuente .

Actualmente, el programa logra una tasa de ganancias del 90% que se ejecuta en javascript en el navegador de mi computadora portátil dado unos 100 milisegundos de tiempo de pensamiento por movimiento, así que aunque no es perfecto (¡todavía!) funciona bastante bien.

Dado que el juego es un espacio de estado discreto, información perfecta, juego por turnos como ajedrez y damas, usé los mismos métodos que se han demostrado que funcionan en esos juegos, a saber, minimax buscar con poda alfa-beta. Dado que ya hay mucha información sobre ese algoritmo por ahí, solo hablaré de las dos heurísticas principales que uso en la función de evaluación estática y que formalizan muchas de las intuiciones que otras personas han expresado aquí.

Monotonía

Esta heurística intenta asegurar que los valores de los mosaicos son todos ya sea aumentando o disminuyendo a lo largo de las direcciones izquierda/derecha y arriba/abajo. Esta heurística por sí sola captura la intuición que muchos otros han mencionado, de que los azulejos de mayor valor deben agruparse en una esquina. Por lo general, evitará que las fichas más pequeñas se queden huérfanas y mantendrá el tablero muy organizado, con fichas más pequeñas en cascada y llenándose en las fichas más grandes.

Aquí hay una captura de pantalla de una cuadrícula perfectamente monótona. Obtuve esto ejecutando el algoritmo con la función eval configurada para ignorar las otras heurísticas y solo considerar la monotonía.

Suavidad

La heurística anterior por sí sola tiende a crear estructuras en las que los mosaicos adyacentes están disminuyendo en valor, pero, por supuesto, para fusionarse, los mosaicos adyacentes deben tener el mismo valor. Por lo tanto, la heurística de suavidad solo mide la diferencia de valor entre los azulejos vecinos, tratando de minimizar este recuento.

Un comentarista en Hacker News dio una formalización interesante de esta idea en términos de teoría de grafos.

Aquí hay una captura de pantalla de una cuadrícula perfectamente lisa, cortesía de este excelente tenedor parodia.

Azulejos libres

Y finalmente, hay una penalización por tener muy pocas fichas libres, ya que las opciones pueden agotarse rápidamente cuando el tablero de juego se vuelve demasiado estrecho.

Y eso es todo! Buscar en el espacio de juego mientras optimiza estos criterios produce resultados notablemente buenos rendimiento. Una ventaja de usar un enfoque generalizado como este en lugar de una estrategia de movimiento explícitamente codificada es que el algoritmo a menudo puede encontrar soluciones interesantes e inesperadas. Si lo ves correr, a menudo hará movimientos sorprendentes pero efectivos, como cambiar de repente contra qué pared o esquina se está construyendo.

Editar:

Aquí hay una demostración del poder de este enfoque. Destapé los valores del azulejo (por lo que siguió adelante después de llegar a 2048) y aquí está el mejor resultado después de ocho pruebas.

Sí, es un 4096 junto a un 2048. = ) Eso significa que logró la esquiva ficha 2048 tres veces en el mismo tablero.

EDIT: Este es un algoritmo ingenuo, que modela el proceso de pensamiento consciente humano, y obtiene resultados muy débiles en comparación con la IA que busca todas las posibilidades, ya que solo mira un azulejo por delante. It was submitted early in the response timeline.

¡He refinado el algoritmo y superado el juego! Puede fallar debido a simple mala suerte cerca del final (se ve obligado a moverse hacia abajo, lo que nunca debe hacer, y aparece una ficha donde su más alto debe ser. Sólo trata de mantener la parte superior fila llena, por lo que mover a la izquierda no rompe el patrón), pero básicamente terminas teniendo una parte fija y una parte móvil para jugar. Este es su objetivo:

Este es el modelo que elegí por defecto.

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

La esquina elegida es arbitraria, básicamente nunca presiona una tecla (el movimiento prohibido), y si lo hace, presiona el contrario nuevamente e intenta arreglarlo. Para los azulejos futuros, el modelo siempre espera que el siguiente azulejo aleatorio sea un 2 y aparezca en el opuesto lado del modelo actual (mientras que la primera fila está incompleta, en la esquina inferior derecha, una vez que se completa la primera fila, en la esquina inferior izquierda).

Aquí va el algoritmo. Alrededor del 80% gana (parece que siempre es posible ganar con técnicas de IA más "profesionales", aunque no estoy seguro de esto.)

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

Algunos consejos sobre los pasos que faltan. Aquí:

El modelo ha cambiado debido a la suerte de estar más cerca del modelo esperado. El modelo es la IA tratando de lograr es

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

Y la cadena para llegar allí se ha convertido en:

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

Los O representan espacios prohibidos...

Así que presionará derecha, luego derecha de nuevo, luego (derecha o arriba dependiendo de dónde se haya creado el 4) luego procederá a completar la cadena hasta que obtenga:

Así que ahora el modelo y la cadena están de vuelta a:

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

Segundo puntero, ha tenido mala suerte y su lugar principal ha sido tomado. Es probable que falle, pero todavía puede lograrlo:

Aquí el modelo y la cadena son:

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

Cuando se las arregla para llegar a los 128 gana una fila entera se gana de nuevo:

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

Me interesé en la idea de una IA para este juego que contenga ninguna inteligencia codificada (es decir, ninguna heurística, funciones de puntuación, etc.). La IA debe "conocer" solo las reglas del juego, y "averiguar" el juego. Esto está en contraste con la mayoría de las AIS (como las de este hilo) donde el juego es esencialmente la fuerza bruta dirigida por una función de puntuación que representa la comprensión humana del juego.

Algoritmo de IA

Encontré un sencillo algoritmo de juego sorprendentemente bueno: Para determinar el siguiente movimiento de un tablero dado, la IA juega el juego en memoria usando movimientos aleatorios hasta que el juego haya terminado. Esto se hace varias veces mientras se realiza un seguimiento de la puntuación final del juego. Luego se calcula la puntuación final media por movimiento inicial. El movimiento inicial con la puntuación final promedio más alta se elige como el siguiente movimiento.

Con solo 100 corridas (es decir, en juegos de memoria) por movimiento, la IA logra el azulejo 2048 el 80% de las veces y el azulejo 4096 el 50% de las veces. Usando 10000 corridas se obtiene el azulejo 2048 100%, 70% para el azulejo 4096, y alrededor del 1% para el azulejo 8192.

Véalo en acción

La mejor puntuación obtenida se muestra aquí:

Un hecho interesante sobre este algoritmo es que, si bien los juegos de azar son bastante malos, elegir el mejor movimiento (o menos malo) conduce a un juego muy bueno: Un juego típico de IA puede alcanzar los 70000 puntos y durar 3000 movimientos, sin embargo, la las partidas de juego aleatorio en memoria desde cualquier posición dan un promedio de 340 puntos adicionales en aproximadamente 40 movimientos adicionales antes de morir. (Puede ver esto por sí mismo ejecutando la IA y abriendo la consola de depuración.)

Este gráfico ilustra este punto: La línea azul muestra la puntuación del tablero después de cada movimiento. La línea roja muestra la mejor puntuación del algoritmo de ejecución aleatoria desde esa posición. En esencia, los valores rojos están "tirando" de los valores azules hacia arriba hacia ellos, ya que son la mejor suposición del algoritmo. Es interesante ver que la línea roja está solo un poco por encima de la línea azul en cada punto, sin embargo, la línea azul continúa aumentando más y más.

Me parece bastante sorprendente que el algoritmo no necesite prever un buen juego para elegir los movimientos que lo producen.

Buscando más tarde encontré que este algoritmo podría clasificarse como un algoritmo de Búsqueda de Árbol Puro de Monte Carlo.

Aplicación y Enlaces

Primero creé una versión de JavaScript que puede ser vista en acción aquí. Esta versión puede ejecutar 100 de carreras en un tiempo decente. Abra la consola para obtener información adicional. (fuente)

Más tarde, para jugar un poco más usé @nneonneo infraestructura altamente optimizada e implementé mi versión en C++. Esta versión permite hasta 100000 carreras por movimiento e incluso 1000000 si tiene paciencia. Instrucciones de construcción proporcionadas. Se ejecuta en la consola y también tiene un control remoto para reproducir la versión web. (fuente)

Resultados

Sorprendentemente, aumentar el número de carreras no mejora drásticamente el juego. Parece haber un límite a esta estrategia en alrededor de 80000 puntos con el azulejo 4096 y todos los más pequeños, muy cerca de lograr el azulejo 8192. Aumentar el número de carreras de 100 a 100000 aumenta las probabilidades de llegar a este límite de puntuación (del 5% al 40%) pero no romperlo.

Ejecutando 10000 corridas con un aumento temporal a 1000000 cerca de posiciones críticas logró romper esta barrera menos del 1% de las veces logrando una puntuación máxima de 129892 y el azulejo 8192.

Mejoras

Después de implementar este algoritmo probé muchas mejoras, incluyendo el uso de las puntuaciones min o max,o una combinación de min,max y avg. También intenté usar la profundidad: En lugar de intentar K carreras por movimiento, intenté K movimientos por movimiento lista de una longitud dada ("arriba,arriba,izquierda", por ejemplo) y seleccionar el primer movimiento de la lista de movimientos con mejor puntuación.

Más tarde implementé un árbol de puntuación que tenía en cuenta la probabilidad condicional de poder jugar un movimiento después de una lista de movimientos dada.

Sin embargo, ninguna de estas ideas mostró ninguna ventaja real sobre la simple primera idea. Dejé el código para estas ideas comentado en el código C++.

Agregué un mecanismo de "Búsqueda profunda" que aumentó el número de ejecución temporalmente a 1000000 cuando cualquiera de las carreras logró alcanzar accidentalmente el siguiente azulejo más alto. Esto ofreció una mejora del tiempo.

Me interesaría saber si alguien tiene otras ideas de mejora que mantengan la independencia del dominio de la IA.

2048 Variantes y Clones

Solo por diversión, también he implementado la IA como un bookmarklet, conectándome a los controles del juego. Esto permite a la IA trabajar con el juego original y muchas de sus variantes.

Esto es posible debido a la naturaleza independiente del dominio de la IA. Algunas de las variantes son bastante distintas, como el clon hexagonal.

Copio aquí el contenido de un post en mi blog

La solución que propongo es muy simple y fácil de implementar. Aunque, ha alcanzado la puntuación de 131040. Se presentan varios puntos de referencia del rendimiento del algoritmo.

Algoritmo

Algoritmo de puntuación heurística

La suposición en la que se basa mi algoritmo es bastante simple: si desea lograr una puntuación más alta, el tablero debe mantenerse tan ordenado como posible. En particular, la configuración óptima está dada por un orden decreciente lineal y monótono de los valores del mosaico. Esta intuición le dará también el límite superior para un valor de azulejo: donde n es el número de azulejo en el tablero.

(Existe la posibilidad de alcanzar la ficha 131072 si la ficha 4 se genera aleatoriamente en lugar de la ficha 2 cuando sea necesario)

Dos formas posibles de organizar el tablero se muestran en las siguientes imágenes:

Para hacer cumplir la ordenación de las fichas en un orden decreciente monótono, la puntuación si se calcula como la suma de los valores linealizados en el tablero multiplicado por los valores de una secuencia geométrica con relación común r

Se pueden evaluar varias rutas lineales a la vez, la puntuación final será la puntuación máxima de cualquier ruta.

Regla de la decisión

La regla de decisión implementada no es del todo inteligente, se presenta el código en Python aquí:

@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);

Una implementación del minmax o el Expectiminimax seguramente mejorará el algoritmo. Obviamente un más la sofisticada regla de decisión ralentizará el algoritmo y requerirá algún tiempo para ser implementado.Intentaré una implementación de minimax en un futuro próximo. (estad atentos)

Punto de referencia

• Pruebas T1 - 121 - 8 rutas diferentes - r=0.125
• T2-122 tests-8-different paths-r = 0.25
• Pruebas T3 - 132-8-rutas diferentes - r = 0,5
• T4-211 tests-2-different paths-r = 0.125
• T5-274 tests-2-different paths-r = 0.25
• T6 - 211 tests - 2-different paths-r = 0.5

En el caso de T2, cuatro pruebas en diez generan la ficha 4096 con una puntuación media de 42000

Código

El código se puede encontrar en GiHub en el siguiente enlace: https://github.com/Nicola17/term2048-AI Se basa en term2048 y está escrito en Python. Implementaré una versión más eficiente en C++ tan pronto como sea posible.

Mi intento utiliza expectimax como otras soluciones anteriores, pero sin bitboards. La solución de Nneonneo puede comprobar 10millones de movimientos que es aproximadamente una profundidad de 4 con 6 fichas restantes y 4 movimientos posibles (2*6*4)⁴. En mi caso, esta profundidad toma demasiado tiempo para explorar, ajusto la profundidad de la búsqueda expectimax de acuerdo con el número de fichas libres que quedan:

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

Las puntuaciones de las tablas se calculan con la suma ponderada del cuadrado del número de fichas libres y el punto producto de la cuadrícula 2D con esto:

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

Que obliga a organizar las fichas descendentemente en una especie de serpiente desde la ficha superior izquierda.

Código siguiente o 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>

Soy el autor de un controlador 2048 que puntúa mejor que cualquier otro programa mencionado en este hilo. Una implementación eficiente del controlador está disponible en github. En un repo separado también está el código utilizado para entrenar la función de evaluación de estado del controlador. El método de entrenamiento se describe en el documento .

El controlador utiliza la búsqueda expectimax con una función de evaluación de estado aprendida desde cero (sin experiencia humana en 2048) por una variante de aprendizaje de diferencia temporal (una técnica de aprendizaje por refuerzo). La función state-value utiliza una red n-tupla, que es básicamente una función lineal ponderada de patrones observados en la placa. Involucró más de 1 mil millones de pesos, en total.

Rendimiento

A 1 movimiento/s: 609104 (100 promedio de juegos)

A 10 movimientos / s: 589355 (300 promedio de juegos)

En 3 capas (ca. 1500 movimientos / s): 511759 (1000 promedio de juegos)

Las estadísticas de fichas para 10 movimientos/s son las siguientes:

2048: 100%
4096: 100%
8192: 100%
16384: 97%
32768: 64%
32768,16384,8192,4096: 10%

(La última línea significa tener las fichas dadas al mismo tiempo en el tablero).

Para 3 capas:

2048: 100%
4096: 100%
8192: 100%
16384: 96%
32768: 54%
32768,16384,8192,4096: 8%

Sin embargo, nunca lo he observado obteniendo el azulejo 65536.

Creo que encontré un algoritmo que funciona bastante bien, ya que a menudo alcanzo puntuaciones superiores a 10000, mi mejor marca personal es de alrededor de 16000. Mi solución no tiene como objetivo mantener los números más grandes en una esquina, sino mantenerlo en la fila superior.

Por favor, consulte el siguiente código:

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

Ya hay una implementación de IA para este juego: aquí. Extracto de README:

El algoritmo es de profundización iterativa profundidad primera búsqueda alfa-beta. La función de evaluación intenta mantener las filas y columnas monótonas (ya sea todas decrecientes o crecientes) mientras minimiza el número de mosaicos en la cuadrícula.

También hay una discusión en ycombinator sobre este algoritmo que puede encontrar útil.

Algoritmo

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

    choose the maximum evaluation
}

Evaluación

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)

Detalles de la evaluación

128 (Constant)

Esta es una constante, utilizada como línea base y para otros usos como pruebas.

+ (Number of Spaces x 128)

Más espacios hace que el estado sea más flexible, multiplicamos por 128 (que es la mediana) ya que una cuadrícula llena de 128 caras es un estado óptimo imposible.

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

Aquí evaluamos las caras que tienen la posibilidad de llegar a fusionarse, evaluándolas hacia atrás, la baldosa 2 pasa a ser de valor 2048, mientras que la baldosa 2048 se evalúa 2.

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

Aquí todavía necesitamos verificar los valores apilados, pero de una manera menor que no interrumpa los parámetros de flexibilidad, por lo que tenemos la suma de { x en [4,44] }.

+ (Number of possible next moves x 256)

Un estado es más flexible si tiene más libertad de transiciones posibles.

+ (Number of aligned values x 2)

Esta es una comprobación simplificada de la posibilidad de tener fusiones dentro de ese estado, sin mirar hacia adelante.

Nota: Las constantes se pueden ajustar..

Esta no es una respuesta directa a la pregunta de OP, esto es más de las materias (experimentos) que he intentado hasta ahora para resolver el mismo problema y obtenido algunos resultados y tener algunas observaciones que quiero compartir, tengo curiosidad si podemos tener algunas ideas adicionales de esto.

Acabo de probar mi implementación minimax con poda alfa-beta con corte de profundidad de árbol de búsqueda en 3 y 5. Estaba tratando de resolver el mismo problema para una cuadrícula 4x4 como una asignación de proyecto para el curso edX ColumbiaX: CSMM.101x Inteligencia Artificial (IA).

Apliqué combinación convexa (probé diferentes pesos heurísticos) de un par de funciones de evaluación heurística, principalmente de la intuición y de las discutidas anteriormente:

1. Monotonía
2. Espacio Libre Disponible

En mi caso, el jugador de la computadora es completamente aleatorio, pero aún así asumí la configuración adversarial e implementé el agente AI player como el jugador máximo.

Tengo cuadrícula 4x4 para jugando el juego.

Observación:

Si asignamos demasiados pesos a la primera función heurística o a la segunda función heurística, ambos casos las puntuaciones que obtiene el jugador de IA son bajas. Jugué con muchas asignaciones de peso posibles a las funciones heurísticas y tomé una combinación convexa, pero muy rara vez el jugador de IA puede anotar 2048. La mayoría de las veces se detiene en 1024 o 512.

También probé la heurística de esquina, pero por alguna razón hace que los resultados peor aún, ¿alguna intuición por qué?

Además, traté de aumentar el corte de profundidad de búsqueda de 3 a 5 (no puedo aumentarlo más ya que buscar ese espacio excede el tiempo permitido incluso con la poda) y agregué una heurística más que mira los valores de las fichas adyacentes y da más puntos si son capaces de fusionarse, pero aún no puedo obtener 2048.

Creo que será mejor usar Expectimax en lugar de minimax, pero aún así quiero resolver este problema solo con minimax y obtener alta puntuaciones como 2048 o 4096. No estoy seguro de si me estoy perdiendo algo.

La siguiente animación muestra los últimos pasos del juego jugado por el agente de IA con el reproductor de computadora:

Cualquier información será realmente muy útil, gracias de antemano. (Este es el enlace de mi entrada de blog para el artículo: https://sandipanweb.wordpress.com/2017/03/06/using-minimax-with-alpha-beta-pruning-and-heuristic-evaluation-to-solve-2048-game-with-computer/)

La siguiente animación muestra los últimos pasos del juego jugado donde el agente de AI player pudo obtener 2048 puntuaciones, esta vez agregando también el valor heurístico absoluto:

Las siguientes figuras muestran el árbol del juego explorado por el agente de IA del jugador asumiendo el equipo como adversario para un solo paso:

Escribí un solucionador 2048 en Haskell, principalmente porque estoy aprendiendo este idioma en este momento.

Mi implementación del juego difiere ligeramente del juego real, en que una nueva ficha es siempre un '2' (en lugar de 90% 2 y 10% 4). Y que la nueva baldosa no es aleatoria, sino siempre la primera disponible desde la parte superior izquierda. Esta variante también se conoce como Det 2048.

Como consecuencia, este solucionador es determinista.

He utilizado un algoritmo exhaustivo que favorece azulejos vacíos. Se realiza bastante rápido para la profundidad 1-4, pero en la profundidad 5 se vuelve bastante lento a alrededor de 1 segundo por movimiento.

A continuación se muestra el código que implementa el algoritmo de resolución. La cuadrícula se representa como una matriz de enteros de 16 longitudes. Y la puntuación se hace simplemente contando el número de cuadrados vacíos.

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

Creo que es bastante exitoso por su simplicidad. El resultado al que llega al comenzar con una cuadrícula vacía y resolver en profundidad 5 es:

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

Game Over

El código fuente puede se puede encontrar aquí: https://github.com/popovitsj/2048-haskell

Este algoritmo no es óptimo para ganar el juego, pero es bastante óptimo en términos de rendimiento y cantidad de código necesario:

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

Muchas de las otras respuestas usan IA con búsquedas computacionalmente costosas de futuros posibles, heurística, aprendizaje y cosas por el estilo. Estos son impresionantes y probablemente el camino correcto a seguir, pero deseo aportar otra idea.

Modele el tipo de estrategia que usan los buenos jugadores del juego.

Por ejemplo:

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

Lea los cuadrados en el orden mostrado arriba hasta que el siguiente valor de cuadrados sea mayor que el actual. Esto presenta el problema de tratar de fusionar otra ficha del mismo valor en este cuadrado.

Para resolver este problema, hay 2 maneras de moverse que no quedan o peor arriba y examinar ambas posibilidades puede revelar inmediatamente más problemas, esto forma una lista de dependencias, cada problema requiere otro problema para ser resuelto primero. Creo que tengo esta cadena o en algunos casos árbol de dependencias internamente al decidir mi próximo movimiento, particularmente cuando está atascado.

Tile necesita fusionarse con neighbour pero es demasiado pequeño: Fusionar a otro vecino con este.

Azulejo más grande en el camino: Aumentar el valor de un azulejo circundante más pequeño.

Etc...

Todo el enfoque probablemente será más complicado que esto, pero no mucho más complicado. Podría ser esta sensación mecánica carente de puntajes, pesos, neuronas y búsquedas profundas de posibilidades. El árbol de posibilidades rairly incluso necesita ser lo suficientemente grande como para necesitar cualquier ramificación en absoluto.