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 tasa de movimiento promedio de 6-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: 97% 8192: 76% 16384: 13% El puntaje mínimo en todas las carreras fue 27536; el puntaje máximo alcanzado fue 377792. El puntaje promedio es 157652. La IA nunca falló en obtener el mosaico de 2048 (por lo que nunca perdió el juego ni una sola vez en 100 juegos) .
Este juego tomó 14395 movimientos durante 37 minutos, o un promedio de 6.6 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 de tabla para movimiento y puntuación, 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 mi computadora portátil de 3 años ( núcleo)).
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.
El algoritmo de puntuación heurística es muy sencillo: los cuadrados abiertos cuentan para +20000, y para cada fila y columna, +20000 si su valor más grande está en el borde (en lugar de estar en los dos cuadrados medios). La antigua heurística se desempeña extremadamente bien por sí misma (generalmente llegando a 4096), pero con frecuencia muere después de que la pieza máxima termina en las 4 fichas del medio. Por lo tanto, la última heurística guía las piezas más grandes hacia los bordes, donde son más fáciles de combinar.
Que la IA logre el mosaico 16384 es un gran hito; Me sorprenderá saber si algún jugador humano ha alcanzado 16384 en el juego oficial (es decir, sin usar herramientas como savestates o deshacer). ¡Ser capaz de lograr este resultado completamente el 13% del tiempo me hace sentir optimista de que el mosaico 32768 se pueda lograr con algo de trabajo!
Puedes probar la IA por ti mismo. El código está disponible en https://github.com/nneonneo/2048-ai .
- ¿La inteligencia artificial está sobrevalorada?
- ¿Cómo pueden la ciencia y las técnicas modernas mejorar el rendimiento y la eficiencia de la señal de tráfico?
- ¿Es la singularidad realmente un peligro para la humanidad?
- ¿Cuál es la implicación del teorema de aproximación universal sobre la metodología de aprendizaje profundo?
- ¿Cómo podemos usar Hadoop para AI?
Fuente: ¿Cuál es el algoritmo óptimo para el juego, 2048?
Descargo de responsabilidad: no tomo crédito por esta respuesta. Solo estoy volviendo a publicar la respuesta.
