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


Recientemente me encontré con el juego 2048. Fusiona fichas similares moviéndolas en cualquiera de las cuatro direcciones para crear fichas "más grandes". Después de cada movimiento, aparece una nueva ficha en una posición vacía al azar con un valor de cualquiera 2 o 4. El juego termina cuando todos los cuadros están llenos y no hay movimientos que puedan unir fichas, o creas un mosaico con un valor de 2048.

Primero, necesito seguir una estrategia bien definida para alcanzar el objetivo. Entonces, pensé en escribir un programa para eso.

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 punto, intentaré fusionar las teselas con valores 2 y 4, es decir, trato de tener 2 y 4 azulejos, lo mínimo posible. Si lo intento de esta manera, todas las demás fichas se fusionan automáticamente y la estrategia parece buena.

Pero, cuando realmente uso este algoritmo, solo obtengo alrededor de 4000 puntos antes de que el juego termine. 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?


1753
2018-03-12 05:37


origen


Respuestas:


Desarrollé una IA 2048 usando expectimax optimización, en lugar de la búsqueda minimax utilizada por el algoritmo de @ ovolve. La IA simplemente lleva a cabo la maximización de todos los movimientos posibles, seguido de la expectativa sobre todos los posibles desvíos de teselas (ponderados por la probabilidad de las fichas, es decir, 10% para 4 y 90% para 2). Hasta donde yo sé, no es posible podar 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

La IA en su configuración predeterminada (profundidad máxima de búsqueda de 8) toma entre 10 ms y 200 ms para ejecutar un movimiento, dependiendo de la complejidad de la posición de la placa. 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 está limitada a 6 movimientos, la inteligencia artificial puede ejecutar fácilmente más de 20 movimientos por segundo, lo que hace que algunos viendo 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 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 alcanzado fue 794076. El puntaje promedio es 387222. La IA nunca falló en obtener la ficha 2048 (por lo que nunca perdió el juego ni una vez en 100 juegos); de hecho, logró el 8192 azulejo al menos una vez en cada carrera!

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

32768 tile, score 794076

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 las teselas son nybbles, es decir, trozos de 4 bits). En una máquina de 64 bits, esto permite pasar toda la placa en un solo registro de máquina.

Las operaciones de cambio de bit 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 las 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" precalculada que describe cómo cada movimiento afecta 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 de tablas. Las tablas contienen puntajes heurísticos calculados en todas las filas / columnas posibles, y la puntuación resultante para una tabla es simplemente la suma de los valores de la tabla en cada fila y columna.

Esta representación de la junta, junto con el enfoque de búsqueda de tabla para movimiento y puntuación, permite que la inteligencia artificial busque una gran cantidad de estados de juego en un corto período de tiempo (más de 10.000.000 de estados de juego por segundo en un núcleo de mi portátil a mediados de 2011).

La búsqueda expectimax se codifica como una búsqueda recursiva que alterna pasos de "expectativa" (probando todas las ubicaciones y valores de spawn posibles y ponderando sus puntajes optimizados por la probabilidad de cada posibilidad) y pasos de "maximización" (probando todos los movimientos posibles) y seleccionando el que tenga el mejor puntaje). La búsqueda en árbol finaliza cuando ve una posición vista previamente (usando un tabla de transposición), cuando alcanza un límite de profundidad predefinido, o cuando alcanza un estado de placa 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 a 8 movimientos.

Heurística

Se usan 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 se combinan en una puntuación posicional, que determina qué tan "buena" es una posición dada de la junta. La búsqueda de optimización tendrá como objetivo maximizar el puntaje promedio de todas las posibles posiciones de la junta. La puntuación real, como se muestra en el juego, es no utilizado para calcular la puntuación de la placa, ya que está muy ponderado a favor de la fusión de las fichas (cuando la fusión diferida podría producir un gran beneficio).

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

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

Además, Petr también optimizó los pesos heurísticos utilizando una estrategia de "meta-optimización" (usando un algoritmo llamado CMA-ES), donde los pesos 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 en torno al 13% del tiempo hasta lograrlo más del 90% del tiempo, y el algoritmo comenzó a alcanzar 32768 en 1/3 del tiempo (mientras que el viejo heurístico nunca produjo una ficha 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 logre 32768 fichas en más de un tercio de sus juegos es un gran hito; Me sorprendería saber si algún jugador humano ha logrado 32768 en el juego oficial (es decir, sin usar herramientas como savestates o deshacer). ¡Creo que la loseta 65536 está al alcance!

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


1130
2018-03-19 07:22



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

Actualmente, el programa alcanza aproximadamente un 90% de índice de victorias en javascript en el navegador de mi computadora portátil, dado aproximadamente 100 milisegundos de tiempo de reflexión por movimiento, por lo que aunque no es perfecto (¡aún!) Funciona bastante bien.

Dado que el juego es un espacio de estado discreto, información perfecta, juego basado en turnos como ajedrez y damas, utilicé los mismos métodos que se ha demostrado que funcionan en esos juegos, es decir, minimax  buscar con poda alfa-beta. Como ya hay mucha información sobre ese algoritmo, hablaré sobre las dos heurísticas principales que uso en el 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 las teselas aumenten o disminuyan a lo largo de las direcciones izquierda / derecha y arriba / abajo. Esta heurística sola capta la intuición que muchos otros han mencionado, que las fichas de mayor valor deberían agruparse en una esquina. Por lo general, evitará que las fichas de menor valor se vuelvan huérfanas y mantendrá la pizarra muy organizada, con fichas más pequeñas que se acumularán y se llenarán en las fichas más grandes.

Aquí hay una captura de pantalla de una cuadrícula perfectamente monótona. Lo obtuve ejecutando el algoritmo con la función eval establecida para ignorar las otras heurísticas y solo considerar la monotonicidad.

A perfectly monotonic 2048 board

Suavidad

La heurística anterior por sí sola tiende a crear estructuras en las que las fichas adyacentes están disminuyendo en valor, pero, por supuesto, para fusionarse, las fichas adyacentes deben tener el mismo valor. Por lo tanto, la heurística de uniformidad simplemente mide la diferencia de valor entre las fichas vecinas, tratando de minimizar este conteo.

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 lisa, cortesía de esta excelente horquilla de parodia.

A perfectly smooth 2048 board

Azulejos gratis

Y, por último, hay una penalización por tener muy pocas fichas gratuitas, ya que las opciones pueden agotarse rápidamente cuando el tablero de juego se llena demasiado.

¡Y eso es! La búsqueda en el espacio del juego mientras se optimizan estos criterios produce un rendimiento notablemente bueno. Una ventaja de utilizar un enfoque generalizado como este en lugar de una estrategia de movimiento codificada explícitamente 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 la pared o esquina contra la que se está construyendo.

Editar:

Aquí hay una demostración del poder de este enfoque. Desactivé los valores de los mosaicos (por lo que seguí avanzando después de llegar a 2048) y aquí está el mejor resultado después de ocho ensayos.

4096

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


1224
2018-03-13 20:04



EDITAR: Este es un algoritmo ingenuo, que modela el proceso del pensamiento humano consciente, y obtiene resultados muy débiles en comparación con la IA que busca todas las posibilidades, ya que solo se ve un mosaico más adelante. Fue enviado temprano en el cronograma de respuesta.

¡He refinado el algoritmo y he derrotado al juego! Puede fallar debido a la simple mala suerte cerca del final (estás obligado a moverte hacia abajo, lo cual nunca debes hacer, y aparece un mosaico donde debe estar el más alto. Solo trata de mantener llena la fila superior, por lo que mover 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:

Ready to finish

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 otra vez y tratas de arreglarlo. Para fichas futuras, 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 esquina 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", 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í: model change

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 representar espacios prohibidos ...

Entonces presionará a la derecha, luego a la derecha otra vez, luego (a la derecha o arriba según donde haya creado el 4) luego procederá a completar la cadena hasta que llegue:

Chain completed

Entonces, 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 punto principal ha sido tomado. Es probable que falle, pero aún puede lograrlo:

Enter image description here

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 se gana de nuevo:

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

119
2018-03-12 16:05



Me interesé en la idea de una IA para este juego que contiene sin inteligencia codificada (es decir, sin heurística, funciones de puntuación, etc.). La IA debería "saber" solo las reglas del juego, y "descifrar" el juego Esto está en contraste con la mayoría de las IA (como las de este hilo) donde el juego es esencialmente una 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 siguiente movimiento para un tablero dado, la IA juega el juego en la memoria usando movimientos aleatorios hasta que el juego termine Esto se hace varias veces mientras se hace un seguimiento de la puntuación final del juego. Luego, el puntaje final promedio por movimiento inicial es calculado. El movimiento inicial con el puntaje final promedio más alto se elige como el siguiente movimiento.

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

Véalo en acción

El puntaje mejor logrado se muestra aquí:

best score

Un hecho interesante sobre este algoritmo es que aunque los juegos aleatorios son bastante malos, elegir el mejor (o el menos malo) movimiento conduce a un muy buen juego: un juego típico de IA puede alcanzar los 70000 puntos y durar 3000 movimientos, pero el los juegos de juegos aleatorios en memoria desde cualquier posición determinada producen un promedio de 340 puntos adicionales en aproximadamente 40 movimientos extra antes de morir. (Puede verlo 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 el algoritmo mejor puntaje final del juego al azar desde esa posición. En esencia, los valores rojos están "tirando" hacia arriba de los valores azules, ya que son la mejor estimación del algoritmo. Es interesante ver que la línea roja está apenas 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.

scoring graph

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

Buscando más tarde encontré que este algoritmo podría clasificarse como Búsqueda pura de árboles Monte Carlo algoritmo.

Implementación y Enlaces

Primero creé una versión de JavaScript que puede ser visto 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 @neneneo e implementé mi versión en C ++. Esta versión permite hasta 100000 ejecuciones por movimiento e incluso 1000000 si tiene la 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 que hay un límite para esta estrategia en alrededor de 80000 puntos con la ficha 4096 y todas las más pequeñas, muy cerca del logro de la ficha 8192. Aumentar el número de carreras de 100 a 100000 aumenta la posibilidades de llegar a este límite de puntuación (de 5% a 40%) pero sin superarlo.

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

Mejoras

Después de implementar este algoritmo, probé muchas mejoras, incluyendo el uso de los puntajes mínimo o máximo, o una combinación de min, max y avg. También traté de usar la profundidad: en lugar de intentar K se ejecuta por movimiento, intenté K movimientos por movimiento lista de una longitud determinada ("arriba, arriba, izquierda", por ejemplo) y seleccionando el primer movimiento de la lista de movimientos de mejor puntaje.

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 comentadas 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 la siguiente ficha más alta. 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 implementó la IA como un marcador, enganchando en los controles del juego. Esto le 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.


114
2018-05-25 09:25



Copio aquí el contenido de un publicar en mi blog


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

Score

Algoritmo

Algoritmo de puntuación heurística

La suposición en la que se basa mi algoritmo es bastante simple: si desea obtener una puntuación más alta, la tabla debe mantenerse lo más ordenada posible. En particular, la configuración óptima viene dada por un orden decreciente lineal y monotónico de los valores de los mosaicos. Esta intuición te dará también el límite superior para un valor de tesela: s donde n es la cantidad de fichas en el tablero.

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

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

enter image description here

Para imponer la ordenación de los mosaicos en un orden decreciente monotónico, el puntaje se calcula como la suma de los valores linealizados en el tablero multiplicados por los valores de una secuencia geométrica con una relación común r <1.

s

s

Varios caminos lineales podrían evaluarse a la vez, el puntaje final será el puntaje máximo de cualquier camino.

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 la minmax o Expectiminimax seguramente mejorará el algoritmo. Obviamente un más La regla de decisión sofisticada ralentizará el algoritmo y requerirá tiempo para su implementación. Intentaré una implementación de minimax en el futuro cercano. (Manténganse al tanto)

Punto de referencia

  • T1 - 121 pruebas - 8 rutas 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

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

En el caso de T2, cuatro pruebas en diez generan la baldosa 4096 con una puntuación promedio de s 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.


88
2018-03-26 22:13



Mi intento usa expectimax como otras soluciones anteriores, pero sin tablas de bits. La solución de Nneonneo puede controlar 10 millones de movimientos, que es aproximadamente una profundidad de 4 con 6 fichas a la izquierda y 4 movimientos posibles (2 * 6 * 4)4. En mi caso, esta profundidad lleva demasiado tiempo explorar, ajusto la profundidad de la búsqueda de expectimax de acuerdo con la cantidad de teselas disponibles:

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

Los puntajes de las tablas se calculan con la suma ponderada del cuadrado del número de teselas gratuitas y el producto de puntos de la grilla 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]]

lo que obliga a organizar los mosaicos descendentemente en una especie de serpiente desde el azulejo superior izquierdo.

Código debajo 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>


30
2018-03-03 05:35



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

Por favor mira 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);
}

25
2018-03-12 18:57