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

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

Primero, 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 en cualquier momento, trataré de fusionar los mosaicos con valores 2y 4, es decir, trato de tener 2y 4mosaicos, lo mínimo posible. Si lo intento de esta manera, todos los otros mosaicos se fusionan automáticamente y la estrategia parece buena.

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

Desarrollé una IA 2048 usando la optimización de Waitimax , en lugar de la búsqueda de minimax utilizada por el algoritmo de @ ovolve. La IA simplemente realiza la maximización sobre todos los movimientos posibles, seguida de la expectativa sobre todos los engendros de fichas posibles (ponderado por la probabilidad de las fichas, es decir, 10% para un 4 y 90% para un 2). Hasta donde yo sé, no es posible podar la optimización de waitimax (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

La IA en su configuración predeterminada (profundidad de búsqueda máxima de 8) tarda entre 10 ms y 200 ms para ejecutar un movimiento, dependiendo de la complejidad de la posición del tablero. En las pruebas, la IA logra una velocidad de movimiento promedio de 5-10 movimientos por segundo en el transcurso de un juego completo. Si la profundidad de 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, ejecuté la IA 100 veces (conectado al juego del navegador a través del control remoto). Para cada mosaico, aquí están las proporciones de juegos en los que ese mosaico se logró al menos una vez:

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

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

Aquí está la captura de pantalla de la mejor ejecución:

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

Implementación

Mi enfoque codifica toda la placa (16 entradas) como un único 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 se pase toda la placa 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" calculada previamente 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 hacia la derecha).

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

Esta representación en el tablero, junto con el enfoque de búsqueda en la mesa para el movimiento y la puntuación, le permite a la IA buscar una gran cantidad de estados de juego en un corto período de tiempo (más de 10,000,000 estados de juego por segundo en un núcleo de mi 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" (probar todas las ubicaciones y valores posibles de baldosas y ponderar sus puntajes optimizados por la probabilidad de cada posibilidad) y los pasos de "maximización" (probar todos los movimientos posibles y seleccionando el que tenga la mejor puntuación). La búsqueda de árbol finaliza cuando ve una posición vista previamente (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" fichas en una fila desde la posición inicial). La profundidad de búsqueda típica es de 4-8 movimientos.

Heurística

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

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

Petr Morávek (@xificurk) tomó mi IA y agregó dos nuevas heurísticas. La primera heurística fue una penalización por tener filas y columnas no monótonas que aumentaron a medida que aumentaban los rangos, asegurando que las filas no monótonas de números pequeños no afectarían fuertemente el puntaje, pero las filas no monótonas de números grandes dañan sustancialmente el puntaje. La segunda heurística contaba el número de posibles fusiones (valores iguales adyacentes) además de los espacios abiertos. Estas dos heurísticas sirvieron para impulsar el algoritmo hacia tableros monótonos (que son más fáciles de fusionar) y hacia posiciones de tablero con muchas fusiones (alentándolo a alinear fusiones cuando sea posible para un mayor efecto).

Además, Petr también optimizó los pesos heurísticos usando una estrategia de "metaoptimizació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 el mosaico 16384 alrededor del 13% del tiempo a lograrlo más del 90% del tiempo, y el algoritmo comenzó a alcanzar 32768 en 1/3 del tiempo (mientras que la antigua heurística nunca produjo un mosaico 32768) .

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

Que la IA alcance el mosaico 32768 en más de un tercio de sus juegos es un gran hito; Me sorprenderá saber si algún jugador humano ha logrado 32768 en el juego oficial (es decir, sin usar herramientas como savestates o deshacer). ¡Creo que el mosaico 65536 está al alcance!

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

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

En la actualidad, el programa alcanza una tasa de ganancia del 90% en JavaScript en el navegador de mi computadora portátil, con aproximadamente 100 milisegundos de tiempo de reflexión por movimiento, por lo 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 el ajedrez y las damas, utilicé los mismos métodos que han demostrado funcionar en esos juegos, a saber, la búsqueda minimax con poda alfa-beta . Como ya hay mucha información sobre ese algoritmo, hablaré sobre 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í.

Monotonicidad

Esta heurística trata de garantizar que los valores de los mosaicos aumenten o disminuyan 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 las fichas de mayor valor deben agruparse en una esquina. Por lo general, evitará que las fichas de menor valor se queden huérfanas y mantendrá el tablero muy organizado, con las fichas más pequeñas en cascada y llenando 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 establecida para ignorar las otras heurísticas y solo considerar la monotonicidad.

Suavidad

Solo la heurística anterior tiende a crear estructuras en las que las fichas adyacentes están disminuyendo en valor, pero, por supuesto, para fusionarse, las fichas adyacentes deben ser del mismo valor. Por lo tanto, la heurística de suavidad solo mide la diferencia de valor entre las fichas vecinas, tratando de minimizar este recuento.

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

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

Azulejos Gratis

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! Buscar en el espacio del juego mientras optimiza 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 repentinamente contra qué pared o esquina se está construyendo.

Editar:

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

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

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

Algoritmo AI

Encontré un algoritmo de juego simple pero sorprendentemente bueno: para determinar el próximo movimiento para un tablero dado, la IA juega el juego en la memoria usando movimientos aleatorios hasta que el juego termina. Esto se hace varias veces mientras se realiza un seguimiento de la puntuación final del juego. Luego se calcula el puntaje final promedio por movimiento inicial . El movimiento inicial con el puntaje final promedio más alto se elige como el siguiente movimiento.

Con solo 100 carreras (es decir, en juegos de memoria) por movimiento, la IA logra el mosaico de 2048 el 80% de las veces y el 4096 el 50% de las veces. El uso de 10000 ejecuciones obtiene el mosaico 2048 100%, 70% para el mosaico 4096 y aproximadamente 1% para el mosaico 8192.

Véalo en acción

El mejor puntaje alcanzado se muestra aquí:

Un hecho interesante sobre este algoritmo es que, aunque los juegos aleatorios son bastante malos, elegir el mejor (o menos malo) movimiento lleva a un juego muy bueno: un juego de IA típico puede alcanzar los 70000 puntos y los últimos 3000 movimientos, pero el los juegos aleatorios en memoria desde cualquier posición dan un promedio de 340 puntos adicionales en aproximadamente 40 movimientos adicionales antes de morir. (Puede ver esto usted mismo ejecutando la IA y abriendo la consola de depuración).

Este gráfico ilustra este punto: la línea azul muestra el puntaje del tablero después de cada movimiento. La línea roja muestra la mejor puntuación final del juego aleatorio del algoritmo desde esa posición. En esencia, los valores rojos están "tirando" de los valores azules hacia ellos, ya que son la mejor suposición del algoritmo. Es interesante ver que la línea roja está 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.

Al buscar más tarde, encontré que este algoritmo podría clasificarse como un algoritmo puro de búsqueda de árboles de Monte Carlo .

Implementación y Enlaces

Primero creé una versión de JavaScript que se puede ver en acción aquí . Esta versión puede ejecutar cientos de ejecuciones en tiempo decente. Abra la consola para obtener información adicional. ( fuente )

Más tarde, para jugar un poco más, utilicé la infraestructura altamente optimizada de @nneonneo e implementé mi versión en C ++. Esta versión permite hasta 100000 carreras por movimiento e incluso 1000000 si tienes 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 para esta estrategia en alrededor de 80000 puntos con el mosaico 4096 y todos los más pequeños, muy cerca del logro del mosaico 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.

Correr 10000 carreras con un aumento temporal a 1000000 cerca de las posiciones críticas logró romper esta barrera menos del 1% de las veces, logrando un puntaje máximo de 129892 y la baldosa 8192.

Mejoras

Después de implementar este algoritmo, probé muchas mejoras, incluido el uso de las puntuaciones mínimas o máximas, o una combinación de mín., Máx. Y prom. También intenté usar la profundidad: en lugar de intentar K carreras por movimiento, probé K movimientos por lista de movimientos de una longitud determinada ("arriba, arriba, izquierda", por ejemplo) y seleccioné 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 determinada.

Sin embargo, ninguna de estas ideas mostró ninguna ventaja real sobre la primera idea simple. 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 ejecuciones logró alcanzar accidentalmente el siguiente mosaico más alto. Esto ofreció una mejora de tiempo.

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

2048 Variantes y clones

Solo por diversión, también he implementado la IA como un marcador , enganchándome a los controles del juego. Esto permite que la IA funcione 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.

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 un mosaico por delante. Fue presentado temprano en la línea de tiempo de respuesta.

¡He refinado el algoritmo y he ganado el juego! Puede fallar debido a la simple mala suerte cerca del final (se ve obligado a moverse hacia abajo, lo que nunca debe hacer, y aparece un mosaico donde debería estar el más alto. Solo trate de mantener la fila superior llena, por lo que moverse hacia la izquierda no romper 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 presionas una tecla (el movimiento prohibido), y si lo haces, presionas lo contrario nuevamente e intentas arreglarlo. Para futuros mosaicos, el modelo siempre espera que el próximo 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 de IA "profesionales", sin embargo, 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 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 Oespacios prohibidos representan ...

Entonces presionará hacia la derecha, luego hacia la derecha nuevamente, luego (hacia la derecha o hacia arriba según dónde se haya creado el 4) y 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 completa y se vuelve a ganar:

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

Copio aquí el contenido de una publicación en mi blog

La solución que propongo es muy simple y fácil de implementar. Sin embargo, ha alcanzado el puntaje 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 lo más ordenado posible. En particular, la configuración óptima viene dada por un orden decreciente lineal y monotónico 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 mosaico en el tablero.

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

En las siguientes imágenes se muestran dos formas posibles de organizar el tablero:

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

Se pueden 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 del todo 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á algún tiempo para implementarse. Probaré una implementación de minimax en el futuro cercano. (Manténganse al tanto)

Punto de referencia

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

En el caso de T2, cuatro pruebas en diez generan el mosaico 4096 con un puntaje promedio de 42000

Código

El código se puede encontrar en GiHub en el siguiente enlace: https://github.com/Nicola17/term2048-AI Está basado en term2048 y está escrito en Python. Implementaré una versión más eficiente en C ++ lo antes posible.

Mi intento usa expectimax como otras soluciones anteriores, pero sin bitboards. La solución de Nneonneo puede controlar 10 millones 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 explorarla, ajusto la profundidad de la búsqueda expectimax de acuerdo con el número de mosaicos libres restantes:

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

Los puntajes de los tableros se calculan con la suma ponderada del cuadrado del número de fichas 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 las fichas de forma descendente en una especie de serpiente desde la ficha superior izquierda.

código a continuación o en github :

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);
updateHint(predict(ai));

function runAI() {
	var p = predict(ai);
	if (p != null && ai.running) {
		move(p, ai);
		updateUI(ai);
		updateHint(p);
		requestAnimationFrame(runAI);
	}
}
runai.onclick = function() {
	if (!ai.running) {
		this.innerHTML = 'stop AI';
		ai.running = true;
		runAI();
	} else {
		this.innerHTML = 'run AI';
		ai.running = false;
		updateHint(predict(ai));
	}
}


function updateHint(dir) {
	hintvalue.innerHTML = ['↑', '→', '↓', '←'][dir] || '';
}

document.addEventListener("keydown", function(event) {
	if (!event.target.matches('.r *')) return;
	event.preventDefault(); // avoid scrolling
	if (event.which in map) {
		move(map[event.which], ai)
		console.log(stats(ai.grid))
		updateUI(ai);
		updateHint(predict(ai));
	}
})
var map = {
	38: 0, // Up
	39: 1, // Right
	40: 2, // Down
	37: 3, // Left
};
init.onclick = function() {
	initialize(ai);
	updateUI(ai);
	updateHint(predict(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 {
	font-family: Arial;
}
table, th, td {
	border: 1px solid black;
	margin: 0 auto;
	border-collapse: collapse;
}
td {
	width: 35px;
	height: 35px;
	text-align: center;
}
button {
	margin: 2px;
	padding: 3px 15px;
	color: rgba(0,0,0,.9);
}
.r {
	display: flex;
	align-items: center;
	justify-content: center;
	margin: .2em;
	position: relative;
}
#hintvalue {
	font-size: 1.4em;
	padding: 2px 8px;
	display: inline-flex;
	justify-content: center;
	width: 30px;
}

<table title="press arrow keys"></table>
<div class="r">
    <button id=init>init</button>
    <button id=runai>run AI</button>
    <span id="hintvalue" title="Best predicted move to do, use your arrow keys" tabindex="-1"></span>
</div>

Soy el autor de un controlador 2048 que obtiene mejores puntajes que cualquier otro programa mencionado en este hilo. Una implementación eficiente del controlador está disponible en github . 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 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) mediante 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-tupla , que es básicamente una función lineal ponderada de patrones observados en el tablero. Implicó más de mil millones de pesos , en total.

Actuación

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

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

A 3 capas (aprox. 1500 movimientos / s): 511759 (promedio de 1000 juegos)

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

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

Por favor vea el código a continuación:

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 la profundidad de profundización iterativa de la primera búsqueda alfa-beta. La función de evaluación intenta mantener las filas y columnas monótonas (disminuyendo o aumentando todas) mientras minimiza el número de mosaicos en la cuadrícula.

También hay una discusión en Hacker News sobre este algoritmo que puede resultarle ú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 evaluación

128 (Constant)

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

+ (Number of Spaces x 128)

Más espacios hacen 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 imposible óptimo.

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

Aquí evaluamos las caras que tienen la posibilidad de fusionarse, al evaluarlas hacia atrás, la casilla 2 adquiere el valor 2048, mientras que la casilla 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 posibles transiciones.

+ (Number of aligned values x 2)

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

Nota: Las constantes se pueden ajustar.

Esta no es una respuesta directa a la pregunta de OP, esta 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 si podemos tener algunas nuevas ideas de esto.

Acabo de probar mi implementación de minimax con poda alfa-beta con un corte de profundidad de árbol de búsqueda en 3 y 5. Estaba tratando de resolver el mismo problema para una cuadrícula de 4x4 como una asignación de proyecto para 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 por intuición y de las discutidas anteriormente:

1. Monotonicidad
2. Espacio libre disponible

En mi caso, el reproductor de la computadora es completamente aleatorio, pero aún 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, ambos casos los puntajes que obtiene el jugador de IA son bajos. Jugué con muchas asignaciones de peso posibles para las funciones heurísticas y tomo 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 esquina heurística, pero por alguna razón empeora los resultados, ¿alguna intuición por qué?

Además, traté de aumentar el límite 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 da más puntos si son fusionables, pero aún así 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 puntajes altos como 2048 o 4096. No estoy seguro de si me falta algo.

La animación a continuación muestra los últimos pasos del juego jugado por el agente de IA con el jugador de la computadora:

Cualquier idea será realmente muy útil, gracias de antemano. (Este es el enlace de mi publicación 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 / y el video de youtube: https://www.youtube.com/watch?v=VnVFilfZ0r4 )

La siguiente animación muestra los últimos pasos del juego jugado donde el agente de jugador de IA podría obtener 2048 puntajes, esta vez agregando también el valor absoluto heurístico:

Las siguientes figuras muestran el árbol del juego explorado por el agente de inteligencia artificial del jugador asumiendo que la computadora es adversaria en 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, ya que un nuevo mosaico siempre es un '2' (en lugar de 90% 2 y 10% 4). Y que el nuevo mosaico no es aleatorio, sino siempre el primero disponible desde la parte superior izquierda. Esta variante también se conoce como Det 2048 .

Como consecuencia, este solucionador es determinista.

Utilicé un algoritmo exhaustivo que favorece las fichas vacías. Funciona bastante rápido para la profundidad 1-4, pero en la profundidad 5 se vuelve bastante lento a aproximadamente 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 realiza 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 que alcanza al comenzar con una cuadrícula vacía y resolver en la 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 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úsqueda computacionalmente costosa de futuros posibles, heurística, aprendizaje y demás. 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 que se muestra arriba hasta que el siguiente valor de cuadrados sea mayor que el actual. Esto presenta el problema de intentar fusionar otro mosaico del mismo valor en este cuadrado.

Para resolver este problema, hay 2 formas de moverse que no se dejan o peor, y examinar ambas posibilidades puede revelar de inmediato más problemas, esto forma una lista de dependencias, cada problema requiere que otro problema se resuelva primero. Creo que tengo esta cadena o, en algunos casos, un árbol de dependencias internamente cuando decido mi próximo movimiento, particularmente cuando estoy atascado.

El mosaico necesita fusionarse con el vecino pero es demasiado pequeño: fusionar otro vecino con este.

Un mosaico más grande en el camino: aumenta el valor de un mosaico circundante más pequeño.

etc ...

Es probable que todo el enfoque sea más complicado que esto, pero no mucho más complicado. Podría ser tan mecánico en la sensación de falta de puntajes, pesos, neuronas y búsquedas profundas de posibilidades. El árbol de posibilidades rairly incluso debe ser lo suficientemente grande como para necesitar alguna ramificación.