¡IA para el juego Threes! por Sirvo LLC. Puedes conseguir el juego desde aquí: http://asherv.com/tres/
La construcción de esta IA fue la inspiración para mi IA 2048 posterior, y algunas de las ideas de la IA 2048 también se han respaldado en esta IA.
Si bien no he evaluado formalmente el rendimiento de esta IA (todavía), sé que ha alcanzado con éxito el mosaico 6144 varias veces, que es el mosaico más alto disponible en el juego. (Las fichas más altas son posibles, pero poco probables, debido a los fuertes efectos aleatorios). La puntuación máxima (al momento de escribir este artículo) es 775,524 puntos:
¡Esta IA es mucho más experimental que su hermana más nueva, la IA 2048, debido a la mayor complejidad de Threes! y porque no ha recibido tanto tiempo de desarrollo. Además, ¡Tres! En general, es un objetivo en movimiento, ya que los algoritmos de generación aleatoria de mosaicos se modifican ocasionalmente, lo que requiere cambios en la IA.
El algoritmo para esta IA ya se detalla esencialmente en esta respuesta de StackOverflow que describe mi IA 2048. En esencia, implementa una búsqueda de fuerza bruta altamente optimizada en el árbol del juego (todos los movimientos posibles, valores de generación de mosaicos y valores de mosaicos), utilizando la optimización expectimax para combinar los resultados y encontrar el "mejor" movimiento posible.
Esta IA de Tres es en realidad más sofisticada que la IA de 2048 en varios sentidos: en particular, tiene en cuenta el "mazo" de fichas próximas (el proceso bien documentado mediante el cual se seleccionan las fichas entrantes aleatorias) y maneja adecuadamente todas las posibles ubicaciones de generación de mosaicos en función de los movimientos que se realizan. En resumen: esta IA de Threes emula correctamente (hasta donde yo sé) cada detalle del juego Threes como parte del proceso de optimización expectimax.
La forma más sencilla de hacer funcionar la IA es clonar una de las ramas prebuilt/ correspondientes a su sistema operativo y procesador. Estas ramas tienen binarios prediseñados en el directorio bin/ .
Tenga en cuenta que el Python "predeterminado" en Windows es de 32 bits, mientras que el Python "predeterminado" en OS X y Linux es de 64 bits. Las compilaciones de 32 bits están etiquetadas como i386 mientras que las compilaciones de 64 bits están etiquetadas como x86_64 .
Si desea compilarlo usted mismo desde el código fuente (por ejemplo, si está realizando cambios), siga las instrucciones a continuación.
Ejecutar
./configure
make
en una terminal. Cualquier compilador de C++ relativamente reciente debería poder generar el resultado.
Tenga en cuenta que no realiza make install ; este programa debe ejecutarse desde este directorio.
Tiene algunas opciones, dependiendo de lo que haya instalado.
Pure Cygwin: siga las instrucciones anteriores de Unix/Linux/OS X. La DLL resultante solo se puede usar con programas Cygwin, por lo que para ejecutar la versión de control del navegador, debe usar Cygwin Python (no python.org Python). Para obtener instrucciones paso a paso, cortesía de Tamas Szell (@matukaa), consulte este documento.
Cygwin con MinGW: ejecutar
CXX=x86_64-w64-mingw32-g++ CXXFLAGS='-static-libstdc++ -static-libgcc -D_WINDLL -D_GNU_SOURCE=1' ./configure ; make
en un shell MinGW o Cygwin para construir. La DLL resultante se puede utilizar con programas que no sean Cygwin.
Visual Studio: abra un símbolo del sistema de Visual Studio, cd al directorio threes-ai y ejecute make-msvc.bat .
Necesitará Python 2.7, NumPy y PIL para ejecutar los programas de Python.
Ejecute bin/threes si desea ver la IA sola en acción.
Hay algunas versiones de Threes basadas en la web, pero quería que la IA jugara con la aplicación real. Entonces, creé un programa "asistente" para dispositivos Android, llamado android_assistant.py , que se comunica con el teléfono a través de ADB y realiza movimientos de forma completamente automática. Solo requiere permisos USB ADB (acceso estándar de desarrollador) y no requiere rooteo ni ninguna otra modificación del dispositivo o aplicación. Utiliza la utilidad screencap estándar de Android para obtener el estado (visible) del juego, calcula el movimiento óptimo y luego utiliza el subsistema de eventos de entrada de Linux para generar eventos de deslizamiento.
Para usar android_assistant.py , deberá configurar el subsistema OCR para su dispositivo. También tendrás que grabar los eventos de deslizamiento para reproducirlos. Actualmente, hay dos dispositivos configurados: el LG Nexus 5 y el OnePlus One (correspondientes a los teléfonos en los que lo he probado). Los parches son bienvenidos para agregar más teléfonos.
Para configurar el sistema OCR, debe agregar una entrada en ocr/devices.py correspondiente a su dispositivo. El nombre del modelo se puede obtener simplemente ejecutando android_assistant.py mientras está conectado al dispositivo (debería aparecer un error con el nombre del modelo esperado). Básicamente, necesitarás tomar una captura de pantalla del juego y derivar la posición del panel de "próximos mosaicos", así como la posición y el espaciado de la cuadrícula de mosaicos. (¡Esta parte probablemente podría necesitar más automatización y/o simplificación!)
Para grabar eventos, simplemente ejecute python -m android.inputemu --record up down left right y ejecute el gesto apropiado en su teléfono cuando se le solicite.
¡El asistente manual es un Tres de uso general! Asistente que funciona con cualquier implementación de Threes!. Le dices el tablero y el próximo conjunto de fichas, y el asistente calcula el mejor movimiento.
Ejecute manual_assistant.py para iniciar el asistente manual.
Tenga en cuenta que el asistente manual espera ver movimientos secuenciales. Si saltas adelante (haciendo movimientos sin el asistente), sal del asistente presionando Ctrl+C y comienza de nuevo. De lo contrario, podría recibir un mensaje de error como "situación imposible" si ingresa a un tablero que no es secuencial con el tablero anterior.
Al ingresar al siguiente tablero, puede usar espacios, nuevas líneas y/o comas para separar los mosaicos. Lea de izquierda a derecha y luego de arriba a abajo. Introduzca un cero para los espacios vacíos. Entrada de ejemplo:
Usando comas y nuevas líneas:
96,2,3,0
2,1,1,0
2,1,0,0
0,0,2,0
Usando comas solo:
96,2,3,0,2,1,1,0,2,1,0,0,0,0,2,0
Usando espacios:
96 2 3 0
2 1 1 0
2 1 0 0
0 0 2 0
También puedes ingresar un "delta" del tablero anterior. Especifique la fila o columna en la que se generó el nuevo mosaico y el valor del mosaico que se generó (puede omitir esto si solo hubo un posible nuevo mosaico en el último movimiento, por ejemplo, si era rojo o azul). También especifica el movimiento que hiciste si no fue el movimiento sugerido por la IA.
Las columnas y filas están numeradas de izquierda a derecha y de arriba a abajo: la columna 1 es la columna de la izquierda y la fila 1 es la fila superior.
Por ejemplo, si el tablero se desliza hacia arriba y pasa de
96 2 3 0
2 1 1 0
2 1 0 0
0 0 2 0
a
96 3 3 0
2 1 1 0
2 0 2 0
0 3 0 0
luego enviarías 2,3,up como tablero (en la segunda columna, se generó un 3). Si la IA hubiera recomendado el movimiento up , entonces simplemente podrías omitirlo y enviar 2,3 . Si se hubiera pronosticado que el próximo mosaico sería 3, podrías omitir el 3 y enviar solo 2 .
Al ingresar deltas, se ahorrará mucho tiempo. En la mayoría de los casos, solo necesita ingresar un número (la columna/fila que cambió).
Al ingresar al próximo mosaico, use uno de los siguientes formatos:
blue (1), red (2) o white (3+)1 , 2 , 3 , 3+ , 6+ , o por ejemplo 24,48,96 , 24 48 963+ significa que podría ser 3 o más; ¡Usa esto con Tres mayores! que no muestran un signo "más" en las fichas de bonificación6+ significa que es cualquier ficha de bonificación; use esto si el próximo mosaico es "+"24,48,96 significa que es uno de esos tres; ¡Usa esto con los Tres más nuevos! que le muestran opciones explícitas para el valor del mosaico de bonificación.
