algorithm - tecnica - tips para el 2048

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

Question

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?

Answer 1

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.

Answer 2

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 .

Answer 3

Me interesé en la idea de una IA para este juego que no contiene inteligencia codificada (es decir, no heurística, funciones de puntuación, etc.). La IA debe "saber" solo las reglas del juego, y "resolver" el juego. Esto contrasta 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 de IA

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 termina. Esto se hace varias veces mientras se realiza un seguimiento de la puntuación final del juego. Luego se calcula la puntuación final promedio por movimiento inicial . El movimiento inicial con la puntuación final promedio más alta se elige como el siguiente movimiento.

Con solo 100 carreras (es decir, en juegos de memoria) por movimiento, la IA alcanza el 20% de las baldosas 2048 de las veces y la baldosa 4096 el 50% de las veces. El uso de 10000 carreras obtiene el azulejo 2048 100%, el 70% para 4096 azulejos, y aproximadamente el 1% para el azulejo 8192.

Verlo en acción

La mejor puntuación obtenida se muestra aquí:

Un dato interesante acerca de este algoritmo es que, si bien los juegos aleatorios son bastante malos, elegir el mejor (o el menos malo) movimiento conduce a un juego muy bueno: un juego de IA típico puede alcanzar los 70000 puntos y los últimos 3000 movimientos. Los juegos aleatorios en memoria de cualquier posición dan un promedio de 340 puntos adicionales en aproximadamente 40 movimientos adicionales antes de morir. (Puedes ver esto por ti mismo ejecutando AI y abriendo la consola de depuración).

Este gráfico ilustra este punto: la línea azul muestra la puntuación del tablero después de cada movimiento. La línea roja muestra la mejor puntuación del juego final de ejecución aleatoria 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 estimación del algoritmo. Es interesante ver que la línea roja está solo un poquito por encima de la línea azul en cada punto, pero la línea azul sigue aumentando más y más.

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

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

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. ( source )

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 tiene la paciencia. Instrucciones de construcción proporcionadas. Se ejecuta en la consola y también tiene un control remoto para jugar la versión web. ( source )

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 baldosa 4096 y todas las más pequeñas, muy cerca de lograr la ficha 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 de romperlo.

La carrera de 10000 carreras con un aumento temporal a 1000000 posiciones casi críticas logró romper esta barrera en menos del 1% de las veces, logrando una puntuación máxima de 129892 y la ficha 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 mínimo, máximo y promedio. 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 seleccionando 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 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 alguna 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 bookmarklet , conectándome a los controles del juego. Esto permite a la IA trabajar con el juego original y muchas de sus variantes .

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

Answer 4

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) ⁴ . 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>

Answer 5

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.

Answer 6

Algoritmo

while(!game_over)
{
for each possible move:
evaluate next state
choose the maximum evaluation
}

Evaluación

Evaluation =
128 (Constant)
+ (Number of Spaces x 128)
+ Sum of faces adjacent to a space { (1/face) x 4096 }
+ Sum of other faces { log(face) x 4 }
+ (Number of possible next moves x 256)
+ (Number of aligned values x 2)

Detalles de la evaluación

128 (Constant)

Esta es una constante, utilizada como línea de base y para otros usos como 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 rellena con 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, evaluándolas al revés, la baldosa 2 se convierte en un valor de 2048, mientras que la baldosa 2048 se evalúa 2.

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

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

+ (Number of possible next moves x 256)

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

+ (Number of aligned values x 2)

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

Nota: Las constantes pueden ser ajustadas ..

Answer 7

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

Answer 8

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

Answer 9

Escribí un solucionador de 2048 en Haskell, principalmente porque estoy aprendiendo este idioma ahora mismo.

Mi implementación del juego difiere ligeramente del juego real, en que una nueva ficha es siempre un ''2'' (en lugar de 90% 2 y 10% 4). Y que 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 los azulejos vacíos. Se realiza con bastante rapidez para la profundidad 1-4, pero en la profundidad 5 se vuelve bastante lenta en alrededor de 1 segundo por movimiento.

A continuación se muestra el código que implementa el algoritmo de resolución. La cuadrícula se representa como una matriz de enteros de 16 longitudes. Y la puntuación se 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 a 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

Answer 10

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:

Answer 11

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

Answer 12

Muchas de las otras respuestas utilizan la inteligencia artificial con la búsqueda computacionalmente costosa de posibles futuros, heurísticas, aprendizaje y demás. Estos son impresionantes y probablemente la forma correcta de avanzar, pero deseo contribuir con otra idea.

Modela 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 los cuadrados sea mayor que el actual. Esto presenta el problema de tratar de fusionar otra casilla del mismo valor en este cuadrado.

Para resolver este problema, hay dos formas de moverse que no quedan o, lo que es peor, y el examen de ambas posibilidades puede revelar inmediatamente más problemas, esto forma una lista de dependencias, cada problema requiere que se resuelva primero otro problema. 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 debe fusionarse con el vecino, pero es demasiado pequeño: fusione otro vecino con este.

Azulejo más grande en el camino: aumentar el valor de un azulejo 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 esta sensación mecánica que carece de puntuaciones, pesos, neuronas y búsquedas profundas de posibilidades. El árbol de posibilidades raras veces tiene que ser lo suficientemente grande como para necesitar cualquier ramificación.

Answer 13

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.

Answer 14

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.