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




trucos de 2048 juego (10)

Copio aquí el contenido de una publicación 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 de los rendimientos del algoritmo.

Algoritmo

Algoritmo heurístico de puntuación

El supuesto en el que se basa mi algoritmo es bastante simple: si desea obtener una puntuación más alta, el tablero debe mantenerse lo más ordenado posible. En particular, la configuración óptima viene dada por un orden decreciente lineal y monótono de los valores de mosaico. Esta intuición le dará también el límite superior para un valor de mosaico: donde n es el número de fichas 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 imponer la ordenación de los mosaicos en un orden decreciente monótono, la puntuación se calcula como la suma de los valores linealizados en el tablero multiplicada por los valores de una secuencia geométrica con una relación común r <1.

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

Regla de decisión

La regla de decisión implementada no es muy inteligente, el código en Python se presenta 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 de minmax o Expectiminimax seguramente mejorará el algoritmo. Obviamente, una regla de decisión más sofisticada ralentizará el algoritmo y requerirá algo de tiempo para ser implementada. Intentaré una implementación minimax en un futuro cercano. (Manténganse al tanto)

Punto de referencia

  • T1 - 121 pruebas - 8 rutas diferentes - r = 0.125
  • T2 - 122 pruebas - 8 rutas diferentes - r = 0.25
  • T3 - 132 pruebas - 8 caminos diferentes - r = 0.5
  • T4 - 211 pruebas - 2 rutas diferentes - r = 0.125
  • T5 - 274 pruebas - 2 rutas diferentes - r = 0,25
  • T6 - 211 pruebas - 2 rutas diferentes - r = 0.5

En el caso de T2, cuatro pruebas en diez generan la cuadrícula 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 ++ lo antes posible.

Recientemente me he topado con el juego 2048 . Combina mosaicos similares moviéndolos en cualquiera de las cuatro direcciones para hacer mosaicos "más grandes". Después de cada movimiento, aparece una nueva ficha en una posición vacía aleatoria con un valor de 2 o 4 . El juego termina cuando todas las casillas están llenas y no hay movimientos que puedan combinar fichas, o si creas una ficha con un valor de 2048 .

Uno, necesito seguir una estrategia bien definida para alcanzar la meta. Entonces, pensé en escribir un programa para ello.

Mi algoritmo actual:

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
}

Lo que estoy haciendo es que, en cualquier momento, intentaré fusionar los mosaicos con los valores 2 y 4 , es decir, intentaré tener 2 y 4 mosaicos, lo mínimo posible. Si lo intento de esta manera, todas las demás fichas se fusionaron automáticamente y la estrategia parece buena.

Pero cuando realmente utilizo este algoritmo, solo obtengo unos 4000 puntos antes de que termine el juego. Los puntos máximos de AFAIK son un poco más de 20,000 puntos, lo cual es mucho más grande que mi puntaje actual. ¿Hay un algoritmo mejor que el anterior?


Desarrollé una IA 2048 utilizando la optimización expectimax , en lugar de la búsqueda minimax utilizada por el algoritmo de @ovolve. La IA simplemente realiza la maximización de todos los movimientos posibles, seguida de la expectativa sobre todos los posibles engendros de fichas (ponderada por la probabilidad de las fichas, es decir, 10% para un 4 y 90% para un 2). Por lo que sé, no es posible eliminar la optimización expectimax (excepto para eliminar ramas que son extremadamente improbables), por lo que el algoritmo utilizado es una búsqueda de fuerza bruta cuidadosamente optimizada.

Actuación

El AI en su configuración predeterminada (profundidad de búsqueda máxima de 8) toma de 10 ms a 200 ms para ejecutar un movimiento, dependiendo de la complejidad de la posición de la placa. En las pruebas, la IA alcanza una tasa de movimiento promedio de 5-10 movimientos por segundo a lo largo de todo un juego. Si la profundidad de la búsqueda se limita a 6 movimientos, la IA puede ejecutar fácilmente más de 20 movimientos por segundo, lo que lo convierte en una observación interesante .

Para evaluar el rendimiento de la puntuación de la IA, corrí la AI 100 veces (conectado al juego del navegador a través del control remoto). Para cada ficha, aquí están las proporciones de juegos en los que se logró esa ficha al menos una vez:

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

El puntaje mínimo en todas las carreras fue 124024; el puntaje máximo obtenido fue 794076. El puntaje promedio es 387222. La IA nunca falló en obtener la casilla 2048 (por lo que nunca perdió el juego ni una sola vez en 100 juegos); de hecho, ¡logró la ficha 8192 al menos una vez en cada carrera!

Aquí está la captura de pantalla de la mejor carrera:

Este juego tomó 27830 movimientos en 96 minutos, o un promedio de 4.8 movimientos por segundo.

Implementación

Mi enfoque codifica toda la placa (16 entradas) como un solo entero de 64 bits (donde los mosaicos son los nybbles, es decir, fragmentos de 4 bits). En una máquina de 64 bits, esto permite que toda la placa se transmita en un solo registro de máquina.

Las operaciones de desplazamiento de bits se utilizan para extraer filas y columnas individuales. Una sola fila o columna es una cantidad de 16 bits, por lo que una tabla de tamaño 65536 puede codificar transformaciones que operan en una sola fila o columna. Por ejemplo, los movimientos se implementan como 4 búsquedas en una "tabla de efectos de movimiento" precomputada que describe cómo cada movimiento afecta a una sola fila o columna (por ejemplo, la tabla "mover a la derecha" contiene la entrada "1122 -> 0023" que describe cómo la fila [2,2,4,4] se convierte en la fila [0,0,4,8] cuando se mueve a la derecha).

La puntuación también se realiza mediante la búsqueda de tablas. Las tablas contienen puntuaciones heurísticas calculadas en todas las filas / columnas posibles, y la puntuación resultante para un tablero es simplemente la suma de los valores de la tabla en cada fila y columna.

Esta representación del tablero, junto con el enfoque de búsqueda de tablas para el movimiento y la puntuación, permite a la IA buscar en un gran número de estados de juego en un corto período de tiempo (más de 10,000,000 de estados de juego por segundo en una computadora portátil de mediados de 2011).

La búsqueda expectimax en sí misma se codifica como una búsqueda recursiva que alterna entre los pasos de "expectativa" (probando todas las ubicaciones y valores posibles de losas de azulejos, y ponderando sus puntajes optimizados por la probabilidad de cada posibilidad), y los pasos de "maximización" (probando todos los movimientos posibles y seleccionando el que tenga la mejor puntuación). La búsqueda de árbol termina cuando ve una posición vista anteriormente (usando una tabla de transposición ), cuando alcanza un límite de profundidad predefinido, o cuando alcanza un estado de tablero que es altamente improbable (por ejemplo, se alcanzó al obtener 6 "4" mosaicos en una fila desde la posición inicial). La profundidad de búsqueda típica es de 4-8 movimientos.

Heurísticas

Se utilizan varias heurísticas para dirigir el algoritmo de optimización hacia posiciones favorables. La elección precisa de la heurística tiene un gran efecto en el rendimiento del algoritmo. Las diversas heurísticas se ponderan y combinan en una puntuación posicional, que determina qué tan "buena" es la posición de un tablero determinado. La búsqueda de optimización tendrá como objetivo maximizar la puntuación promedio de todas las posiciones posibles de la junta. El puntaje real, como lo muestra el juego, no se usa para calcular el puntaje del tablero, ya que está muy ponderado en favor de la combinación de fichas (cuando la fusión retrasada puede producir un gran beneficio).

Inicialmente, utilicé dos heurísticas muy simples, otorgando "bonos" para los cuadrados abiertos y por tener valores grandes en el borde. Estas heurísticas funcionaron bastante bien, alcanzando con frecuencia 16384 pero nunca llegando a 32768.

Petr Morávek (@xificurk) tomó mi AI y agregó dos nuevas heurísticas. La primera heurística fue una penalización por tener filas y columnas no monotónicas que aumentaron a medida que aumentaban los rangos, asegurando que las filas no monotónicas de números pequeños no afectaran fuertemente la puntuación, pero las filas no monotónicas de grandes números afectaron sustancialmente la puntuación. La segunda heurística contó el número de fusiones potenciales (valores iguales adyacentes) además de los espacios abiertos. Estas dos heurísticas sirvieron para empujar el algoritmo hacia tableros monotónicos (que son más fáciles de fusionar), y hacia posiciones de tableros con muchas combinaciones (alentándolo a alinear las combinaciones donde sea posible para un mayor efecto).

Además, Petr también optimizó los pesos heurísticos usando una estrategia de "meta-optimización" (usando un algoritmo llamado CMA-ES ), donde los pesos mismos se ajustaron para obtener el puntaje promedio más alto posible.

El efecto de estos cambios es extremadamente significativo. El algoritmo pasó de lograr la baldosa 16384 alrededor del 13% del tiempo a lograrla más del 90% del tiempo, y el algoritmo comenzó a alcanzar 32768 en 1/3 del tiempo (mientras que las antiguas heurísticas nunca produjeron una baldosa 32768) .

Creo que todavía hay margen de mejora en las heurísticas. Este algoritmo definitivamente aún no es "óptimo", pero siento que se está acercando bastante.

Que la IA logre la ficha 32768 en más de un tercio de sus juegos es un hito enorme; Me sorprendería saber si algún jugador humano ha logrado 32768 en el juego oficial (es decir, sin utilizar herramientas como salvaciones o deshacer). Creo que la baldosa 65536 está a nuestro alcance!

Puedes probar la IA por ti mismo. El código está disponible en https://github.com/nneonneo/2048-ai .


Mi intento usa expectimax como otras soluciones anteriores, pero sin bitboards. La solución de Nneonneo puede verificar 10 millones de movimientos, que es aproximadamente una profundidad de 4 con 6 fichas restantes y 4 movimientos posibles (2 * 6 * 4) 4 . En mi caso, esta profundidad lleva 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 los tableros se calculan con la suma ponderada del cuadrado del número de mosaicos libres y el producto de puntos 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 los azulejos de forma descendente en una especie de serpiente desde el azulejo superior izquierdo.

Código abajo 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 del programa de IA que otros han mencionado en este hilo. Puedes ver la IA en action o leer la source .

Actualmente, el programa logra una tasa de ganancia de aproximadamente el 90% 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, juegos por turnos como el ajedrez y las damas, utilicé los mismos métodos que se ha demostrado que funcionan en esos juegos, es decir, la search minimax con poda alfa-beta . Como ya hay mucha información sobre ese algoritmo, solo hablaré de las dos heurísticas principales que utilizo en la función de evaluación estática y que formalizan muchas de las intuiciones que otras personas han expresado aquí.

Monotonicidad

Esta heurística trata de asegurar que los valores de los mosaicos aumenten o disminuyan en las direcciones izquierda / derecha y arriba / abajo. Esta heurística por sí sola captura la intuición que muchos otros han mencionado, que las teselas de mayor valor deben agruparse en una esquina. Por lo general, evitará que las baldosas de menor valor se queden huérfanas y mantendrá la tabla muy organizada, con las baldosas más pequeñas en cascada y rellenándose en las baldosas más grandes.

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

Suavidad

Solo la heurística anterior 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 las baldosas vecinas, intentando minimizar este conteo.

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

Aquí hay una captura de pantalla de una cuadrícula perfectamente suave, cortesía de este excelente tenedor de 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! La búsqueda en el espacio del juego mientras se optimizan estos criterios produce un rendimiento notablemente bueno. 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é muro o esquina se está acumulando.

Editar:

Aquí hay una demostración del poder de este enfoque. Yo destapé los valores de los azulejos (por lo que continuó después de alcanzar 2048) y este es el mejor resultado después de ocho intentos.

Sí, eso es un 4096 junto con un 2048. =) Eso significa que logró el eludivo azulejo 2048 tres veces en el mismo tablero.


EDITAR: 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 una ficha hacia adelante. Se presentó temprano en la línea de tiempo de respuesta.

¡He refinado el algoritmo y derrotado al juego! Puede fallar debido a una mala mala suerte cerca del final (se ve obligado a moverse hacia abajo, lo que nunca debe hacer, y aparece una ficha donde debería estar la más alta. Simplemente intente mantener la fila superior llena, por lo que moverla a la izquierda no es suficiente). rompe el patrón), pero básicamente terminas teniendo una parte fija y una parte móvil para jugar. Este es tu 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 lo contrario nuevamente e intenta arreglarlo. Para los mosaicos futuros, el modelo siempre espera que el siguiente mosaico aleatorio sea un 2 y aparezca en el lado opuesto al modelo actual (mientras que la primera fila está incompleta, en la esquina inferior derecha, una vez que se completa la primera fila, en la parte inferior izquierda) esquina).

Aquí va el algoritmo. Alrededor del 80% gana (parece que siempre es posible ganar con más técnicas "profesionales" de inteligencia artificial, 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)
  }

Unos pocos 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 que la IA está 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 ...

Por lo tanto, presionará a la derecha, luego a la derecha nuevamente, luego (a la 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 vuelven a:

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

Segundo puntero, ha tenido mala suerte y se ha tomado su lugar principal. Es probable que falle, pero aún puede lograrlo:

Aquí el modelo y la cadena es:

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

Cuando logra alcanzar 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

Creo que encontré un algoritmo que funciona bastante bien, ya que a menudo llego a más de 10000 puntos. Mi mejor marca personal es de 16 000. Mi solución no apunta a mantener los números más grandes en una esquina, sino a mantenerlos 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);
}

Esta no es una respuesta directa a la pregunta de OP, esto es más de las cosas (experimentos) que intenté hasta ahora para resolver el mismo problema y obtuve algunos resultados y tengo algunas observaciones que quiero compartir. Tengo curiosidad de poder tener algunas. más perspectivas de esto.

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

Apliqué una 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 mencionadas anteriormente:

  1. Monotonicidad
  2. Espacio libre disponible

En mi caso, el jugador de la computadora es completamente aleatorio, pero aun así asumí configuraciones adversas e implementé el agente del jugador AI como el jugador máximo.

Tengo cuadrícula 4x4 para jugar el juego.

Observación:

Si asigno demasiados pesos a la primera función heurística o la segunda función heurística, los dos casos en los que el jugador de IA obtiene las puntuaciones son bajas. Jugué con muchas posibles asignaciones de peso a las funciones heurísticas y tomé una combinación convexa, pero muy raramente 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 la esquina, pero por alguna razón empeora los resultados, ¿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 la búsqueda de ese espacio excede el tiempo permitido incluso con la poda) y agregué una heurística más que analiza los valores de los mosaicos adyacentes y proporciona más puntos si son capaces de fusionarse, pero aún no puedo obtener 2048.

Creo que sería mejor usar Expectimax en lugar de minimax, pero aún así quiero resolver este problema solo con minimax y obtener puntuaciones altas 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 AI con el jugador de la computadora:

Cualquier información será realmente muy útil, gracias de antemano. (Este es el enlace de mi 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 jugador de AI podría obtener 2048 puntuaciones, esta vez agregando la heurística de valor absoluto también:

Las siguientes figuras muestran el árbol de juego explorado por el agente de AI del jugador que asume la computadora como adversario por un solo paso:


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

Soy el autor de un controlador 2048 que obtiene mejores calificaciones que cualquier otro programa mencionado en este hilo. Una implementación eficiente del controlador está disponible en github.com/aszczepanski/2048 . En un repositorio 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 paper .

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

Actuación

A 1 movimientos / s: 609104 (100 juegos en promedio)

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

En 3 capas (aprox. 1500 movimientos / s): 511759 (1000 juegos en promedio)

Las estadísticas de mosaico 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 los mosaicos dados 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.


Ya hay una implementación de AI para este juego: here . Extracto de README:

El algoritmo es la profundización iterativa de la primera búsqueda alfa-beta. La función de evaluación trata de mantener las filas y columnas monotónicas (ya sea que disminuyan o aumenten) al tiempo que minimiza el número de mosaicos en la cuadrícula.

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





2048