La primera parte (análisis de código) está aquí: https://habr.com/post/420725/ .

Algoritmo

Descripción

El algoritmo realiza continuamente los siguientes pasos:

1. Él espera hasta que se cree un nuevo tetrimino.
2. Comprueba el tipo del tetrimino recién creado, el tipo del siguiente tetrimino (figura en el campo de vista previa) y el contenido del campo de juego.
3. Explora todas las formas posibles de agregar dos tetriminos al campo de juego y evalúa cada probabilidad.
4. Mueve el tetrimino recién creado para que coincida con la ubicación de la mejor probabilidad detectada.

Cada uno de estos pasos se describe en detalle a continuación.

Bloquear búsqueda

Considere una versión simplificada de Tetris, en la que las formas no caen automáticamente. La única forma de bajar la figura es bajando suavemente. Una vez eliminados los tiempos del juego, podemos describir completamente el estado del tetrimino activo por su posición y orientación. La figura tiene un lugar conocido de creación inicial, y las siguientes operaciones se utilizan para convertir de un estado a otro:

• Un paso abajo
• Un paso a la izquierda
• Mueve un paso hacia la derecha
• Gire un paso en sentido antihorario
• Rotación en sentido horario

Estas operaciones son aplicables solo cuando los cuadrados del tetrimino resultante corresponden a celdas vacías del campo de juego. Cuando es imposible avanzar un paso hacia abajo, el estado se considera bloqueado. Sin embargo, dado que simplificamos Tetris y la espera para el bloqueo es esencialmente infinita, el estado bloqueado puede transformarse aún más mediante otras operaciones mediante el deslizamiento y el desplazamiento.

Se pueden encontrar muchos estados bloqueados con una secuencia mínima de operaciones que los crean mediante la búsqueda de amplitud primero (BFS). Como se indica a continuación, utiliza una cola para almacenar resultados intermedios.

1. Hacemos cola en el estado en la creación.
2. Deducimos el estado de la cola.
3. Obtenemos los siguientes estados utilizando la operación de conversión.
4. Si no hay movimiento hacia abajo entre ellos, entonces el estado que se elimina de la cola se bloquea.
5. Hacemos cola en estados posteriores que aún no hemos visitado.
6. Si la cola no está vacía, repita desde el paso 2.

El programa representa cada estado como un objeto con los siguientes campos:

{ x, y, rotation, visited, predecessor }

En el proceso de preparación, el programa crea una matriz tridimensional de objetos de estado (20 filas × 10 columnas × 4 vueltas), inicializando x , y rotation consecuencia.

El campo visited se marca cuando el estado está en cola. En BFS, esto es válido porque cada estado posterior aumenta la longitud total de la ruta en 1. Es decir, al aumentar la longitud de la ruta es imposible crear un estado posterior que deba insertarse en otro lugar que no sea el final de la cola para mantener el orden.

El campo predecessor indica el objeto de estado del que se deriva el estado actual. Se establece cuando el estado está en cola. El estado de creación no tiene estados anteriores.

El conjunto de estados bloqueados detectados durante la búsqueda está determinado por el tipo de tetrimino y los bloques llenos en el campo de juego. La secuencia de los movimientos que los generaron se puede aclarar (en el orden inverso) siguiendo los enlaces anteriores al estado de creación. Cuando la constante PLAY_FAST se establece en true al comienzo del programa, omite por completo los estados anteriores al colocar directamente tetrimino en el campo y bloquearlo.

Una matriz tridimensional de objetos de estado, una cola y BFS se empaquetan en una clase. Tiene un método de búsqueda que recibe el campo de juego (matriz bidimensional), el tipo de tetrimino y el oyente. Cada vez que se detecta un estado bloqueado, el campo de juego se actualiza agregando tetrimino a la ubicación adecuada. Luego, el campo de juego modificado junto con la información sobre los cambios se transmite al oyente para su procesamiento. Después de que el oyente completa el retorno, se restaura el campo de juego.

El oyente se usa para combinar varias operaciones de búsqueda en una cadena, lo que permite encontrar todas las formas posibles de agregar dos (o más) tetriminos al campo de juego. El primer motor de búsqueda de la cadena ejecuta BFS solo una vez. Sin embargo, el segundo motor de búsqueda ejecuta BFS cada vez que la primera búsqueda detecta un estado bloqueado. Y así sucesivamente, si hay otros motores de búsqueda en la cadena.

El oyente del último motor de búsqueda evalúa el campo de juego modificado. Cuando encuentra el campo de juego mejor de lo que se ha investigado anteriormente, escribe el objeto usado del estado bloqueado, que en este momento utiliza el primer motor de búsqueda de la cadena. Dado que el primer motor de búsqueda ejecuta BFS solo una vez, los campos predecessor de sus objetos de estado siguen siendo válidos hasta la finalización de todo el proceso de búsqueda. Es decir, el último oyente esencialmente graba el camino a lo largo del cual debe ir el primer tetrimino para llegar a la mejor configuración del campo de juego como resultado.

Función de evaluación

La función de puntuación asigna un valor al campo de juego modificado: una suma ponderada de varios parámetros de influencia. La función de evaluación utilizada en este caso se basa en la función desarrollada por Islam Al-Ashi . Utiliza los siguientes parámetros:

• Número total de filas borradas : este es el número total de filas que se borrarán mediante la adición de dos tetriminos.
• Altura total de bloqueo : la altura de bloqueo es la altura sobre el piso del campo de juego en el que la figura está bloqueada. Esta es la distancia vertical que caería una figura bloqueada si elimina todos los otros cuadrados ocupados del campo de juego y mantiene la orientación de la figura. La altura total de bloqueo es la suma de las alturas de bloqueo de los dos tetriminos.
• El número total de celdas de “pozo” : una celda de pozo es una celda vacía ubicada sobre todas las celdas ocupadas en una columna, de modo que sus vecinos izquierdo y derecho son celdas ocupadas; Al determinar los pozos, las paredes del campo de juego se consideran celdas ocupadas. La idea es que un pozo es una estructura abierta en la parte superior, cerrada en la parte inferior y rodeada de paredes a ambos lados. La probabilidad de espacios intermitentes en las paredes del pozo significa que las células del pozo no necesariamente ocurren en un montón continuo dentro de una columna.
• Número total de agujeros en las columnas : el agujero en la columna es una celda vacía ubicada inmediatamente debajo de la celda ocupada. El género del campo de juego no se compara con la celda superior. No hay agujeros en las columnas vacías.
• Número total de transiciones en columnas : una transición en columnas es una celda vacía adyacente a una celda ocupada (o viceversa) dentro de una sola columna. La combinación del bloque de columnas ocupado más alto con un espacio vacío encima no se considera una transición. Del mismo modo, el piso del campo de juego tampoco se compara con la celda que está sobre él. Por lo tanto, no hay transiciones en una columna completamente vacía.
• Número total de transiciones en filas : una transición en filas es una celda vacía adyacente a una celda ocupada (o viceversa) dentro de la misma fila. Las celdas vacías cerca de las paredes del campo de juego se consideran transiciones. La cantidad total se calcula para todas las líneas del campo de juego. Sin embargo, las líneas completamente vacías no se tienen en cuenta en el número total de transiciones.

El-Ashi sugirió que se pueden encontrar pesos útiles utilizando el algoritmo de optimización de enjambre de partículas (PSO), que mejora iterativamente el conjunto de soluciones al simular el comportamiento del enjambre observado en la naturaleza. En nuestro caso, cada solución es un vector de peso, y la aptitud de la opción está determinada por el juego en Tetris; Este es el número total de tetriminos durante el cual sobrevivió hasta el final del juego.

Estas ideas se aplican en la versión de Java que se describe a continuación; se ejecuta fuera de FCEUX y se puede configurar para un juego no gráfico en memoria que se ejecuta a una velocidad mucho mayor. Después de preparar el PSO, me sorprendió ver que el algoritmo no avanza más después de la iteración inicial. Después de esta iteración, varias variantes de soluciones generadas aleatoriamente ya jugaron bastante bien. Durante varios días, el tamaño de este conjunto disminuyó hasta que solo quedó una opción. Aquí están los valores para esta solución:

Parámetro	Peso
Número total de filas despejadas	1.000000000000000
Altura total de bloqueo	12.885008263218383
Número total de células de pozo	15.842707182438396
El número total de agujeros en las columnas.	26.894496507795950
El número total de transiciones en columnas.	27.616914062397015
Saltos de línea totales	30.185110719279040

El campo de juego se estimó multiplicando los parámetros por sus respectivos pesos y sumando los resultados. Cuanto menor sea el valor, mejor será la solución. Como todos los parámetros y pesos tienen valores positivos, todos los parámetros perjudican la evaluación general; cada uno de ellos debe ser minimizado. También significa que la mejor puntuación es 0.

Dado que estos pesos se seleccionaron aleatoriamente, el rango de valores adecuados puede ser muy amplio. Este conjunto particular de números y la importancia relativa estimada de cada parámetro pueden no ser relevantes. Sin embargo, será interesante observarlos de cerca.

El parámetro menos dañino es el número total de filas borradas. El hecho de que esta opción sea perjudicial es contraintuitivo. Pero el objetivo principal de la IA es la supervivencia. No se esfuerza por la mayoría de los puntos. En cambio, juega de forma conservadora, generalmente limpiando las filas de una en una. Para obtener Doble, Triple o Tetris, debes hacer crecer un montón que vaya en contra del objetivo a largo plazo.

El siguiente en la lista es la altura total de bloqueo. Se puede minimizar bajando el tetrimino lo más cerca posible del piso. Esta es una estrategia simple que contribuye a largo plazo a la supervivencia y, a corto plazo, al embalaje de calidad de las piezas.

El peso asignado al número total de celdas de pozos parece un poco sorprendente, porque los jugadores experimentados generalmente construyen pozos profundos intencionalmente para recolectar varios Tetris (combinaciones de cuatro líneas) en una fila. Pero como se mencionó anteriormente, este es un juego arriesgado, contrario al objetivo principal: la supervivencia. Además, el número de pozos es un indicador de la "rugosidad" de la pila. Un cierto nivel de desigualdad es beneficioso al colocar ciertas figuras o combinaciones de figuras. Pero la alta rugosidad provoca daños en el embalaje hermético.

El número total de agujeros en las columnas es aproximadamente la mitad del número total de transiciones en las columnas. Estos parámetros se pueden combinar y colapsar en un parámetro relacionado común, obteniendo un parámetro más extenso y más dañino: el número total de transiciones.

Las áreas densamente pobladas tienen un pequeño número de transiciones en todas las direcciones. Por lo tanto, la estrategia principal, impulsada por la inteligencia artificial, se puede describir brevemente de la siguiente manera: empacar las piezas lo más cerca posible entre sí.

Otras opciones

Aquí hay una lista de algunos parámetros más con los que experimenté durante el desarrollo de la IA:

• Altura del montón : los bloques ocupados pueden colgar sobre celdas vacías, creando protuberancias y agujeros; sin embargo, no es posible bloquear bloques ocupados sobre líneas completamente vacías. Por lo tanto, la altura del montón es el número de filas que contienen al menos un bloque ocupado.
• Número total de columnas ocupadas : es el número de columnas que contienen al menos una celda ocupada.
• Número total de celdas ocupadas : el número de celdas ocupadas en el campo de juego.
• Número total de áreas conectadas : el algoritmo de relleno se usa aquí para calcular el número de áreas conectadas continuamente. Además de encontrar "islas" ocupadas, descubre agujeros que se extienden a lo largo de ambos ejes.
• Dispersión de altura de columna : esta es una medida estadística de la variación en las alturas de columna. Es un indicador de rugosidad de la superficie.
• Valor de adaptación total : calcula el valor de adaptación del montón para la siguiente figura desconocida. Cuenta el número total de formas en que se pueden agregar 7 tipos de formas al campo de juego sin la aparición de nuevos agujeros. Para un conteo preciso, se requerirá el uso repetido de BFS. Pero para un cálculo aproximado, el árbol de búsqueda se puede truncar mucho.
• Calificación promedio para la siguiente figura : este parámetro profundiza la búsqueda al analizar todas las posibilidades para la siguiente figura desconocida. Utiliza otros parámetros para separar la ubicación de cada tipo de figura, y luego devuelve el promedio de 7 calificaciones. Para cada ubicación de la figura, se requiere BFS.
• Juego simulado promedio : el parámetro simula una serie de juegos en Tetris, seleccionando piezas usando su propio generador de números pseudoaleatorios y usando AI para trabajar con ellos. Al final de cada juego, el campo de juego se evalúa utilizando otros parámetros. Se devuelve el valor promedio para todos los lotes.

Todos los parámetros se pueden personalizar agregando factores personalizados. Por ejemplo, en lugar de simplemente calcular las filas borradas, puede asignar sus propios pesos para Single, Double, Triple y Tetris, simulando un sistema de puntos. Si la limpieza simultánea de varias filas perjudica el objetivo a largo plazo de la supervivencia, a las filas individuales se les puede asignar un peso negativo, mientras que otras pueden ser positivas.

Otro factor útil es el valor de compensación. Por ejemplo, una superficie perfectamente plana de un montón tiene una dispersión de alturas de columna de 0. Pero una superficie perfectamente plana no se adapta a S y Z, así como a otras combinaciones de formas. Por lo tanto, al restar la constante, la varianza debe centrarse alrededor de la rugosidad óptima.

Los parámetros ajustados y sesgados se pueden elevar hasta cierto punto para que antes de calcular la suma ponderada puedan escalar logarítmicamente o exponencialmente. Todas estas probabilidades pueden considerarse como pesos adicionales que pueden optimizarse potencialmente por métodos como PSO.

Muchos de los parámetros dan una idea de qué tan bien el montón puede manejar piezas adicionales, por ejemplo, aquellas que se ocupan de la rugosidad de la superficie, pero la "Cantidad total de adaptación", "Calificación promedio de la siguiente figura" y "Juego simulado promedio" evalúan el campo de juego modificado insertando figuras que no están incluidas en las dos conocidas. En el estudio de figuras posteriores, debido a la rápida eliminación de la serie, la cantidad de conocimiento adicional obtenido disminuye con la profundidad. Esto significa que el curso pasado de la fiesta no es tan importante, y el curso de la fiesta en el futuro distante tampoco es muy importante. De hecho, si una secuencia corta de figuras se establece aleatoriamente de forma incorrecta, entonces la IA restaura rápidamente el juego, usando las siguientes figuras para borrar las filas afectadas. La determinación del valor óptimo para el análisis de las cifras posteriores requiere más investigación.

Otro aspecto de la utilidad de un parámetro es el costo computacional. Los costos aumentan enormemente porque se llama a la función de evaluación para cada posible colocación de dos figuras. Dado que la IA debe poder jugar Tetris en tiempo real, los factores de costo que proporcionan información valiosa se pueden intercambiar por técnicas más aproximadas que se ejecutan más rápido.

Entrenamiento de IA

Hay secuencias patológicas que pueden conducir a Game Over, independientemente de la estrategia. El ejemplo más simple es la secuencia interminable de tetrimino S y Z, que, como se muestra en la animación, rápidamente lleva a la IA a perder.


Dado que lleva días ejecutar la variante AI antes de completar varios lotes y calcular el promedio, no es práctico usar la duración promedio del lote como una métrica de control de PSO. En cambio, puede aumentar la complejidad del juego con una velocidad controlada al aumentar la frecuencia de S y Z, lo que con el tiempo conducirá a la creación alternativa de solo este par de figuras.

Intenté usar este método de enseñanza, pero descubrí que enseñar IA para trabajar con S y Z frecuentes en realidad daña la capacidad de hacer frente a formas aleatorias distribuidas uniformemente.

En un método alternativo inspirado en el juego B-Type, la métrica de PSO controla la frecuencia de la limpieza de filas. El campo de juego es un diagrama de 10 líneas de bloques de basura aleatorios, y cada vez que se borra la línea, aparece una nueva línea de basura debajo, restaurando la altura del montón. Dado que el campo de juego tiene un ancho de 10 columnas, y cada tetrimino consta de 4 cuadrados, en promedio, la IA debe despejar una fila cada 2.5 tetrimino. Y para deshacerse de la basura, debe hacerlo aún más rápido.

Desafortunadamente, esta técnica tampoco mejoró el rendimiento. Una razón probable es que los agujeros de basura aleatorios no coinciden exactamente con las cadenas con las que la IA trata en el juego real. Además, limpiar la fila es un objetivo a corto plazo; la limpieza de hileras codiciosas no necesariamente mejora la supervivencia a largo plazo. De vez en cuando, no se deben tocar las filas para procesar ciertas combinaciones de figuras posteriores.

Colin Fei sugirió un enfoque diferente en su página web. Creó histogramas que muestran el porcentaje de formas que están bloqueadas en cada fila durante los lotes de prueba. Curiosamente, todos los histogramas se ven casi idénticos independientemente del número de figuras creadas. En base a esto, sugirió que puede usar una imagen aproximada de la función para cualquier lote de prueba al evaluar la expectativa estadística de bloquear una figura en la línea de creación, obteniendo así el tiempo durante el cual la IA jugará hasta el final del juego. Decidí explorar esta posibilidad.

A continuación se muestra un mapa de calor de muchos lotes de prueba, en total que contienen 2,039,900,000 tetrimino. Cada celda se colorea según el porcentaje de formas encerradas en ella. Para mejorar el contraste visual, se selecciona una paleta no lineal. El mapa fue creado al normalizar los valores de las celdas dividiéndolos entre el porcentaje máximo de celdas y luego anunciando a la potencia de 0.19 (ver "corrección gamma" ).

Color Porcentaje ■ 0.00000000 ■ 0.00000315 ■ 0.00024227 ■ 0.00307038 ■ 0.01860818 ■ 0.07527774 ■ 0.23582574 ■ 0.61928352 ■ 1.42923040 ■ 2.98867416 ■ 5.78182519

Las rayas naranja oscuro y rojo en las líneas 17 y 18 significan que la gran mayoría de las figuras terminan allí. El tono verde pálido desde abajo es una consecuencia de la geometría de las figuras: solo 4 de los 7 tipos de tetrimino pueden aparecer en la línea inferior. Las esquinas inferiores son negras porque es imposible llegar allí.

El color a lo largo de cada línea es casi uniforme, y esto sugiere que las formas se distribuyen horizontalmente de manera uniforme. Se pueden explicar brechas leves observando los histogramas de tipos individuales de formas:

T

J

Z

O

S

L

Yo

T resulta ser el tipo más universal: su histograma es más uniforme que todos los demás. Anomalías en el histograma J: el resultado de la influencia de las paredes; solo Jr y Jl pueden estar en las columnas laterales, lo que hace que AI use las columnas 1 y 9 con más frecuencia para compensar. Lo mismo se aplica a L. Los histogramas Z y S se ven aproximadamente iguales, lo que enfatiza el desequilibrio debido al hecho de que Zv y Sv No son imágenes especulares perfectas el uno del otro. El Tipo O está limitado a un campo de juego de 19 × 9, y parece que es más probable que AI use O en los lados que en el centro. Tetrimino I se desplaza hacia la derecha, porque su punto de partida se encuentra allí; por lo tanto, el bloqueo en la columna 1 es raro.

La tabla muestra el porcentaje de cifras que están bloqueadas en cada fila.

Cadena	Porcentaje
0 0	0.0000000000
1	0.0000000000
2	0.0000004902
3	0.0000026472
4 4	0.0000066180
5 5	0.0000172557
6 6	0.0000512280
7 7	0.0001759400
8	0.0006681210
9 9	0.0023187901
10	0.0077928820
11	0.0259672043
12	0.0866187068
13	0.2901315751
14	0.9771663807
15	3.3000408353
16	10.6989059268
17	28.5687976371
18 años	50.0335706162
19	6.0077671454

Aquí hay un gráfico de los valores:


Si la línea 19 no se tiene en cuenta, el gráfico muestra un crecimiento exponencial.

La siguiente es una lista de las proporciones del número de formas bloqueadas en filas adyacentes.

Cadena A / Cadena B	Ratio (%)
1/2	0.00
2/3	18,52
3/4	40,00
4/5	38,35
5/6	33,68
6/7	29/12
7/8	26,33
8/9	28,81
9/10	29,76
10/11	30/01
11/12	29,98
13/12	29,85
13/14	29,69
14/15	29,61
15/16	30,84
16/17	37,45
17/18	57,10
18/19	832.81

Las líneas 16–19tienen en cuenta las figuras que interactúan con el piso del campo de juego, por lo que pueden descartarse. En filas, la 0–5selección es demasiado pequeña para ser significativa. Las razones restantes, pares 6 / 7–14 / 15, son casi idénticas; su valor promedio es 29.24%. Esto significa que la probabilidad de que el montón crezca en una línea es aproximadamente la misma independientemente de la altura del montón. Esto es lógico, porque las reglas de Tetris limitan la interacción en la parte superior del montón cuando está muy empaquetado.

El siguiente gráfico muestra el registro del ₁₀ por ciento de las cifras en las líneas 6–15.


Está cerca de una línea perfectamente recta con un coeficiente de determinación cercano a 1 . La fórmula derivada de la regresión lineal que se muestra arriba nos da la intersección con el eje Y, suponiendo que el porcentaje de formas en la fila 0 es aproximadamente 10 ^−7.459 %. El inverso de este valor nos da una expectativa estadística de 2,877,688,349 tetrimino o 1,151,175,340 filas hasta el final del juego.

Esto nos hace entender que log ₁₀el porcentaje de figuras en cada línea permanece lineal hasta la línea 0. Sin embargo, cuando el montón casi alcanza el techo del campo de juego, la libertad de movimiento se limita a tal punto que se viola esta propiedad. Además, bloquear una pieza en la línea 0 no significa necesariamente que el juego haya terminado; aún puede guardarse si hay un lugar para crear nuevas figuras.

Otra forma de evaluar la fuerza de la IA es medir el número promedio de formas creadas entre la limpieza completa del campo de juego. La limpieza completa se puede obtener con solo 5 tetriminos. Por ejemplo, entre otras posibilidades, esto se puede lograr con cinco figuras O dispuestas en el piso del campo de juego. En general, dado que cada tetrimino consta de 4 cuadrados y el ancho del campo de juego es de 10 cuadrados, el número de figuras creadas entre la limpieza completa debe ser un múltiplo de 5 ( desde4 × 5n = 2 × 10n ).

Mi IA tiene un número promedio de formas creadas entre limpiezas de campo completo de 1,181, un número bastante pequeño. Dado que una limpieza completa es como reiniciar un juego, un lote completo puede verse como una serie extremadamente larga de reinicios del juego, seguido de un avance rápido al final del juego. Al igual que la secuencia de alternativas descrita anteriormente SZ, las secuencias patológicas que conducen al final del juego suelen ser muy cortas.

El siguiente histograma muestra la probabilidad (en porcentaje) de que la IA logre una limpieza completa del campo después del número especificado de figuras creadas.


El orden de grados en la fórmula anterior determina la tasa de disminución y, presumiblemente, la fuerza de la IA. Según esta fórmula, aproximadamente el 0,4%, o aproximadamente 1 de cada 253 juegos que comienzan con un campo de juego vacío, termina con una limpieza completa en solo 5 tetriminos.

En contraste con lo que sugirió Faye, las constantes en las aproximaciones lineales y exponenciales requieren un tamaño de muestra muy grande para que R ²se acercó a 1, por lo que este método no es aplicable para PSO. Sin embargo, las constantes obtenidas con lotes largos se pueden utilizar para optimizar la función de aproximación que crea posibles valores constantes para lotes cortos. En una especie de bucle de retroalimentación de desarrollo, la función de aproximación optimizada se puede usar en el PSO, lo que mejora la IA, que a su vez se puede usar para calcular nuevas constantes, sirviendo como criterios de referencia para la función de aproximación.

Versión Java

Sobre el programa

Para los desarrolladores que no están familiarizados con Lua, agregué un puerto Java AI al archivo zip de origen . Las clases son una traducción casi línea por línea de objetos Lua basados ​​en cierres .

Paquetes

El código se divide en dos paquetes:

• tetris.ai contiene clases e interfaces de IA.
• tetris.gui crea un modelo gráfico del campo de juego.

Clases e interfaces AI

Una clase con el nombre apropiado Tetriminosdescribe tetrimino. Se usa de manera similar enumy contiene constantes para todos los tipos de tetrimino:

 public static final int NONE = -1; public static final int T = 0; public static final int J = 1; public static final int Z = 2; public static final int O = 3; public static final int S = 4; public static final int L = 5; public static final int I = 6; 

NONEsignifica valor no asignado. Se utiliza para celdas vacías del campo de juego.

También Tetriminoscontiene dos modelos de la tabla de orientación. PATTERNS- esta es una matriz entera de 4 dimensiones (tipo × rotación × cuadrado × coordenadas) que contiene las coordenadas relativas de los cuadrados; las líneas están dispuestas de modo que en cada tipo la orientación de creación de forma sea la primera ORIENTATIONSEs otro modelo, una matriz bidimensional (tipo × rotación) de objetos Orientation. Cada uno Orientationcontiene las coordenadas del cuadrado como una matriz de objetos Point. También tiene campos que describen el rango de posiciones permitidas para la orientación correspondiente.

 public class Orientation { public Point[] squares = new Point[4]; public int minX; public int maxX; public int maxY; ... } 

 public class Point { public int x; public int y; ... } 

La rotación de Tetrimino (el segundo índice en ambas tablas de orientación) se usa en objetos Stateque BFS manipula.

 public class State { public int x; public int y; public int rotation; public int visited; public State predecessor; public State next; ... } 

x, yy rotationjuntos describan la posición y orientación de la figura. Dado que el tipo Tetrimino permanece constante desde el momento de la creación hasta el bloqueo, un campo para él es opcional.

La clase Searcherque contiene el algoritmo BFS crea un conjunto completo de todos los objetos posibles Statecuando se crea:

 private void createStates() { states = new State[AI.PLAYFIELD_HEIGHT][AI.PLAYFIELD_WIDTH][4]; for(int y = 0; y < AI.PLAYFIELD_HEIGHT; y++) { for(int x = 0; x < AI.PLAYFIELD_WIDTH; x++) { for(int rotation = 0; rotation < 4; rotation++) { states[y][x][rotation] = new State(x, y, rotation); } } } } 

Aunque Java tiene una rica API de colecciones, Searchercontiene su propia implementación de la cola. La clase Queueutiliza State.nextpara unir objetos Stateen una lista vinculada. Como todos los objetos Stateestán predefinidos, y cada uno Statese puede agregar a la cola no más de una vez, la cola puede funcionar en su lugar, lo que elimina la necesidad de objetos contenedores temporales innecesarios utilizados en implementaciones de cola comunes.

El "corazón" de BFS es el método que se muestra a continuación search.

 public boolean search(int[][] playfield, int tetriminoType, int id) { int maxRotation = Tetriminos.ORIENTATIONS[tetriminoType].length - 1; int mark = globalMark++; if (!addChild(playfield, tetriminoType, mark, null, 5, 0, 0)) { return false; } while(queue.isNotEmpty()) { State state = queue.dequeue(); if (maxRotation != 0) { addChild(playfield, tetriminoType, mark, state, state.x, state.y, state.rotation == 0 ? maxRotation : state.rotation - 1); if (maxRotation != 1) { addChild(playfield, tetriminoType, mark, state, state.x, state.y, state.rotation == maxRotation ? 0 : state.rotation + 1); } } addChild(playfield, tetriminoType, mark, state, state.x - 1, state.y, state.rotation); addChild(playfield, tetriminoType, mark, state, state.x + 1, state.y, state.rotation); if (!addChild(playfield, tetriminoType, mark, state, state.x, state.y + 1, state.rotation)) { lockTetrimino(playfield, tetriminoType, id, state); } } return true; } 

Genera una cola con el estado del tetrimino creado, y luego recupera secuencialmente los elementos secundarios de los estados que se eliminan de la cola, y los agrega de nuevo a la cola cuando aparecen en el campo de juego.

Un searchcampo de juego que contiene una combinación de celdas ocupadas y vacías, el tipo Tetrimino creado y un identificador arbitrario se pasa al método . Durante la ejecución del BFS, se llama a un oyente cada vez que se detecta una posición de bloqueo.

 public interface ISearchListener { public void handleResult(int[][] playfield, int tetriminoType, int id, State state); } 

El oyente recibe un campo de juego modificado que contiene un tetrimino bloqueado en su lugar. El tipo de Tetrimino creado y un identificador arbitrario también se transmiten. El último parámetro es Stateen el que tetrimino está bloqueado. Siguiendo la cadena de enlaces State.predecessor, puede restaurar todo el camino hasta Statecrear una forma.

State.visitedpodría implementarse como boolean; pero con todas las instalaciones necesarias para resolver antes de buscar Statepara el alivio visitedde false. En cambio, hice un visitedvalor en intcomparación con un contador, incrementando con cada llamada.

MétodoaddChildpre-colas estados posteriores. El estado posterior debe estar dentro del campo y estar ubicado en 4 celdas vacías del campo de juego. Además, el estado posterior no debe ser visitado State. Si la posición es válida, addChildvuelve trueincluso si el estado posterior no se pudo poner en cola porque ya se ha visitado.

El método searchusa el addChildvalor de retorno para determinar si se puede crear una forma. Si no se puede crear la figura, el montón ha llegado a la cima y la búsqueda ya no se puede realizar; Por lo tanto, vuelve false.

RetornableaddChildTambién se está estudiando la importancia de la posibilidad de bajar un paso más. Si esto no se puede hacer, entonces el estado actual es la posición de bloqueo y comienza la llamada lockTetrimino. El método lockTetriminocambia el campo de juego, llama al oyente y luego restaura el campo de juego.

Cada fila de la matriz playfieldcontiene 1 elemento adicional, que almacena el número de celdas ocupadas en la fila. El método incrementa el elemento lockTetriminoporque marca las celdas como ocupadas.

Cuando el oyente recibe un campo de juego modificado, llamaPlayfieldUtil.clearRowsPara eliminar filas llenas el método los reconoce al verificar el valor en el elemento adicional de la matriz. Para eliminar una cadena, el código aprovecha el hecho de que en Java, las matrices bidimensionales son esencialmente matrices de matrices; solo empuja enlaces hacia cadenas. PlayfieldUtilcontiene líneas libres; él completa el proceso de limpieza insertando un enlace a uno de ellos. Antes de realizar el cambio, el índice de la fila que se borra se almacena en un elemento de fila adicional. Luego, el enlace a la línea se inserta en la pila.

Entonces el oyente llamaPlayfieldUtil.restoreRowspara descartar los cambios realizados en el campo de juego. Los pasos se cancelan en orden inverso. Primero obtenemos una fila libre desde la parte superior. Luego, la fila llena se recupera de la pila y se restaura el índice del elemento adicional. Se utiliza para cambiar las referencias de línea y volver al lugar de la línea eliminada. Finalmente, se restaura un elemento adicional, se le asigna el valor del ancho del campo de juego: el número de celdas ocupadas en la fila llena.

También PlayfieldUtilhay un método evaluatePlayfieldque calcula y escribe 4 parámetros de evaluación en la clase de contenedor que se muestra a continuación.

 public class PlayfieldEvaluation { public int holes; public int columnTransitions; public int rowTransitions; public int wells; } 

La clase maneja todo esto AI. Contiene dos objetos Searcherconectados entre sí por el oyente que se muestra a continuación.

 public void handleResult( int[][] playfield, int tetriminoType, int id, State state) { if (id == 0) { result0 = state; } Orientation orientation = Tetriminos.ORIENTATIONS[tetriminoType][state.rotation]; int rows = playfieldUtil.clearRows(playfield, state.y); int originalTotalRows = totalRows; int originalTotalDropHeight = totalDropHeight; totalRows += rows; totalDropHeight += orientation.maxY - state.y; int nextID = id + 1; if (nextID == tetriminoIndices.length) { playfieldUtil.evaluatePlayfield(playfield, e); double fitness = computeFitness(); if (fitness < bestFitness) { bestFitness = fitness; bestResult = result0; } } else { searchers[nextID].search(playfield, tetriminoIndices[nextID], nextID); } totalDropHeight = originalTotalDropHeight; totalRows = originalTotalRows; playfieldUtil.restoreRows(playfield, rows); } 

Una clase AIpuede manejar cualquier cantidad de objetos Searcher, pero Nintendo Tetris solo muestra una forma por adelantado. Los objetos Searcherse almacenan en una matriz, y el código que se muestra arriba sirve como su escucha común. El identificador aleatorio pasado al método Searcher.searches en realidad el índice de la matriz, que también es la profundidad de la búsqueda. Cuando se llama al oyente, el identificador dirige la llamada al siguiente Searcheren la cadena. Si llega al final de la matriz, evalúa el campo de juego. Y cuando encuentra un campo de juego con un puntaje de condición física más alto, anota el bloqueado Statedel primero Searcheren la cadena.

AIcontiene un método searchque recibe el campo de juego y una matriz que contiene los tipos de tetrimino creado y el siguiente. El regresaStateque contiene la posición y la rotación en la que debe bloquearse el primer tetrimino. No se enfoca en el segundo tetrimino; la próxima vez que se llama, vuelve a calcular la puntuación. Si el montón es demasiado alto y la cadena Searcherno puede colocar ambos tetriminos, entonces AI.searchvolverá null.

 public State search(int[][] playfield, int[] tetriminoIndices) { this.tetriminoIndices = tetriminoIndices; bestResult = null; bestFitness = Double.MAX_VALUE; searchers[0].search(playfield, tetriminoIndices[0], 0); return bestResult; } 

Desafío AI

Dado que la versión de Java no está vinculada a FCEUX, puede usarse potencialmente para otros proyectos. Para aquellos que estén interesados ​​en integrar AI en otro lugar, esta sección describe todo lo que necesita.

Primero, cree una instancia AI, instancia PlayfieldUtily matriz para contener todos los tipos conocidos de tetrimino. Además, cree una PlayfieldUtil.createPlayfieldinstancia del campo de juego llamando ; devuelve una matriz bidimensional con una columna adicional, que examinamos anteriormente. Probablemente también necesitará un generador de números aleatorios.

 AI ai = new AI(); PlayfieldUtil playfieldUtil = new PlayfieldUtil(); int[] tetriminos = new int[AI.TETRIMINOS_SEARCHED]; int[][] playfield = playfieldUtil.createPlayfield(); Random random = new Random(); 

Inicialmente, el campo de juego está vacío y todas las celdas son relevantes Tetriminos.NONE. Si completa las celdas mediante programación, no olvide anotar el playfield[rowIndex][AI.PLAYFIELD_WIDTH]número de celdas ocupadas en cada fila.

Rellene el conjunto de tipos de tetrimino con los tipos de la forma creada inicialmente y la siguiente forma, que generalmente se seleccionan manualmente.

 tetriminos[0] = random.nextInt(7); tetriminos[1] = random.nextInt(7); 

Luego pasamos el campo de juego y la matriz de tipos al método AI.search. Él regresará Stateen el que necesita bloquear el primer tetrimino. Si regresa null, entonces el juego es inevitable.

 State state = ai.search(playfield, tetriminos); 

Si necesita una forma de crear una figura para bloquear, páselo al Statemétodo AI.buildStateList.

 State[] states = ai.buildStatesList(state); 

Para actualizar el campo de juego, lo pasaremos PlayfieldUtil.lockTetriminojunto con su tipo y objeto State. Este método borra automáticamente las filas rellenas.

 playfieldUtil.lockTetrimino(playfield, tetriminos[0], state); 

Antes de volver a llamar, AI.searchdebe seleccionar aleatoriamente el siguiente tetrimino.

 tetriminos[0] = tetriminos[1]; tetriminos[1] = random.nextInt(7); 

Juntos, se ve así:

 AI ai = new AI(); PlayfieldUtil playfieldUtil = new PlayfieldUtil(); int[] tetriminos = new int[AI.TETRIMINOS_SEARCHED]; int[][] playfield = playfieldUtil.createPlayfield(); Random random = new Random(); tetriminos[0] = random.nextInt(7); tetriminos[1] = random.nextInt(7); while(true) { // ... print playfield ... State state = ai.search(playfield, tetriminos); if (state == null) { break; // game over } playfieldUtil.lockTetrimino(playfield, tetriminos[0], state); tetriminos[0] = tetriminos[1]; tetriminos[1] = random.nextInt(7); } 

En lugar de mostrar el campo de juego en forma de texto, puede usar una forma más interesante para mostrar lo que está sucediendo ...

Visualización del campo de juego

La clase TetrisFrameimita los gráficos de Nintendo Tetris, incluidas las características de comportamiento descritas en la parte anterior del artículo.


Para verlo en acción, ejecútelo tetris.gui.Main. Al igual que con la versión de Lua, podemos ajustar la velocidad del juego cambiando el valor constante al comienzo del archivo.

 public static final boolean PLAY_FAST = true; 

TetrisFrameTiene 4 métodos para manipular la pantalla. El método displayTetriminorepresenta el tetrimino activo en las coordenadas especificadas. Recibe un parámetro de retraso, lo que hace que el método espere antes de devolver el número especificado de cuadros de animación.

 public void displayTetrimino(int type, int rotation, int x, int y, int delay) 

El método lockTetriminobloquea la figura en su lugar. Los colores del contador de filas, puntos, nivel y tetrimino se actualizan en consecuencia, lo que demuestra el comportamiento curioso esperado cuando los valores exceden los valores permitidos. La asignación de un animatevalor a un parámetro trueincluye animaciones de limpieza de filas y parpadeo de pantalla al recibir Tetris. El método está bloqueado hasta que finalice la animación.

 public void lockTetrimino(int type, int rotation, int x, int y, boolean animate) 

updateStatisticsAndNext realiza un incremento del contador de estadísticas para el tetrimino recién creado y actualiza la visualización de la siguiente figura.

 public void updateStatisticsAndNext(int activeTetrimino, int nextTetrimino) 

El método dropTetriminocrea una forma y le permite descender bajo la influencia de la "gravedad", sin hacer ningún intento de girarla o moverla. Mainlo usa para las dos últimas cifras cuando AI.searchregresa null. Si el parámetro animateimporta true, entonces si es imposible crear una figura, se cortará el telón del final del juego. Al igual que con todos los demás métodos, este método bloquea hasta que finaliza la animación. Solo regresa truecuando puede crear una figura en un campo de juego ocupado.

 public boolean dropTetrimino(int type, boolean animate) 

El flujo de trabajo debe llamar a estos 4 métodos, pero se TetrisFramedeben crear en el subproceso de envío de eventos en sí. Para ver cómo se hace esto, vea la clase Main.

En aras del interés, Mainutiliza una clase Randomizerque simula un generador de números pseudoaleatorio sesgado de Nintendo Tetris.

El paquete tetris.gui.imagescontiene archivos relacionados con la pantalla. tiles.png- Esta es una tabla de patrones que contiene todos los gráficos de mosaico. background.datalmacena los identificadores de los mosaicos que forman el fondo; datos extraídos de $BF3F. Y colors.datcontiene bytes que generan colores cuadrados inusuales que aparecen desde el nivel 138.

ImageLoaderContiene una tabla de paletas NES y ImagePanese almacena el conjunto completo de valores de nivel visualizados.

Otros proyectos

Potencialmente, el código se puede usar en lugar de escribir para el modo de demostración. De hecho, dicha demostración se puede representar para siempre, aprovechando la rapidez con que la IA puede despejar todo el campo de juego. Para lograr esto, en el generador de números pseudoaleatorios, debe usar alguna constante arbitraria como semilla, lo que nos dará una secuencia tetrimino determinista. Se grabarán las dos primeras secuencias de tetrimino. Cuando la IA alcanza la limpieza de campo completo, los siguientes dos tetriminos se compararán con los dos primeros de la secuencia. Si coinciden (este evento se espera cada 49 limpiezas de campo completo), entonces el generador de números pseudoaleatorios puede pasar la misma constante que la semilla, lo que creará un bucle de demostración infinito. La duración del ciclo puede ser muy larga para ocultar el hecho de que es un ciclo. Tambiénla demostración puede comenzar en un punto aleatorio del bucle, creando una nueva demostración cada vez.

Otra posibilidad de usar AI es crear un modo de "jugador contra computadora". En el Tetris multijugador, al despejar varias líneas al mismo tiempo, aparecen líneas de basura en la parte inferior del campo del oponente, elevando el campo de juego. La IA debe ser capaz de protegerse de los escombros por la misma razón que puede jugar juegos de tipo B. Sin embargo, como se dijo anteriormente, AI juega de forma conservadora, generalmente luchando por despejar una línea a la vez. Es decir, podrá defenderse de los ataques, pero no podrá atacar. Para poder cambiar su comportamiento, creé una interfaz llamada IChildFilter.

 public interface IChildFilter { public boolean validate(int[][] playfield, int tetriminoType, int x, int y, int rotation); } 

AItiene un constructor alternativo que obtiene una implementación IChildFilter. Si está disponible, IChildFilter.validatesirve como un control adicional para el permiso del estado secundario; si regresa false, entonces el estado secundario no está en cola.

WellFilterEs una implementaciónIChildFilterdestinado a recoger cuatro filas (Tetris). Al igual que los jugadores vivos, construye gradualmente un pozo en la columna más a la derecha del campo de juego, subiendo línea por línea de abajo hacia arriba. Como funciona línea por línea, rechaza los estados secundarios que agregan un cuadrado a la columna de la derecha. Cuando toda la fila, con la excepción de la columna del pozo, está completamente llena, la IA pasa a la siguiente fila. Cuando 4 o más de estas líneas están listas, permite que el "palo" caiga en el pozo y obtenga Tetris. Además, se realiza un seguimiento de la altura del montón; Si se vuelve demasiado grande, WellFilterdeja de afectar a la IA.


Para probarlo en funcionamiento, realice los Mainsiguientes cambios:

 AI ai = new AI(new WellFilter()); 

WellFilterfunciona, pero no es particularmente efectivo. Contiene una heurística simple diseñada para demostrar el concepto. Para obtener Tetris con más frecuencia, debe utilizar una estrategia más sofisticada, tal vez una que pueda optimizarse con PSO.

Además, puede usar el filtro de estado secundario para generar patrones. A continuación se muestra un ejemplo de lo que es capaz de hacer PatternFilter.


PatternFilterCrea imágenes línea por línea de abajo hacia arriba, de forma similar a cómo funciona WellFilter; sin embargo, en lugar de preservar la columna más a la derecha, PatternFiltersolo aprueba los estados secundarios que corresponden a un patrón particular.

El constructor PatternFilterobtiene el nombre de una de las imágenes en el paquete tetris.gui.patterns, que utiliza como plantilla. Cada imagen de 20 × 10 contiene píxeles en blanco y negro correspondientes a las celdas en el campo de juego.

 AI ai = new AI(new PatternFilter("tetriminos")); 

La línea de código que se muestra arriba crea las siluetas de siete tipos de tetrimino.


Otro ejemplo con un gran tetrimino T girado en ángulo.


Otro ejemplo. Si te fijas bien, verás el nombre del juego.


Como WellFilter, no PatternFilteres más que una prueba de concepto. Los patrones que procesa se limitan al fondo del campo de juego debido al hecho de que los intentos de obtenerlos generalmente terminan con el juego terminado. Sin embargo, esta es una idea interesante que vale la pena seguir estudiando.

Versión de Gamepad

El script Lua y el programa Java ignoran la gravedad; para ellos, la velocidad de descenso no es importante, porque dependiendo de la configuración, teletransportan las figuras inmediatamente a la ubicación deseada o arrastran a lo largo de cualquier ruta elegida. En cierto modo, simplemente imitan el Tetris, no lo juegan. Sin embargo, en el archivo zip con las fuentes hay otro script Lua que se reproduce generando las señales de los botones del gamepad, lo que permite que el juego controle el movimiento de las figuras, la gravedad y todo lo demás.

Agregar gravedad expande enormemente el espacio de búsqueda, obligando a AI a tener en cuenta las astutas reglas de manipulación de formas. Los detalles de estas reglas se describen en la primera parte del artículo y se pueden apreciar plenamente mediante un estudio directo del código. Aquí están los más importantes:

• : , .
• «» .
• «» «» .
• .
• .
• .
• .
• , .
• A B .
• «» «» 6 16 . «» «» , .
• «» 3 .
• 96 . , — .

Para acomodar todas estas reglas, la información histórica debe integrarse en los estados de búsqueda. Necesitan campos en los que se almacenará el número de cuadros de retención para cada botón y el número de cuadros después de la última liberación automática. Cada conjunto único de valores, incluidas las coordenadas x, yy la rotación tetrimino caracterizan un estado separado y único. Desafortunadamente, el número de posibilidades es tan grande que una búsqueda completa de este espacio no es práctica. La versión AI para el gamepad explora solo un subconjunto del mismo.

AI usa un objeto Statecon los siguientes campos:

 { x, y, rotation, Left, Right, Down, A, B, fallTimer, visited, predecessor } 

En lugar de usar el cambio automático de AI en cuadros alternativos, presione y suelte el botón de cambio. Por lo tanto, solo necesita monitorear si se presiona el botón y no cuánto tiempo se lo presiona. Dado que no hay rotación automática, la misma idea se aplica a los botones A y B. Por lo tanto el campo Left, Right, Ay Bpuede ser interpretada como una lista que contiene uno de los siguientes valores:

 { RELEASED, PRESSED } 

Por otro lado, para el descenso suave, inicialmente debe mantener presionado el botón "Abajo" durante tres cuadros, lo que requiere la existencia de 4 estados:

 { RELEASED, PRESSED_FOR_1_FRAME, PRESSED_FOR_2_FRAMES, PRESSED_FOR_3_FRAMES } 

Downaumenta gradualmente desde el valor RELEASEDhasta PRESSED_FOR_3_FRAMES, en el que se produce un descenso suave. Después de eso, puede recibir un valor RELEASEDo volver a PRESSED_FOR_2_FRAMES, causando un descenso suave cada segundo cuadro después del retraso inicial. No puede ser RELEASEDde PRESSED_FOR_1_FRAMEo de PRESSED_FOR_2_FRAMES.

En realidad, el código Lua usa una constante entera, pero el principio es el mismo.

Del mismo modo, visitedy predecessor, fallTimerse le asigna el valor obtenido al escribir en el estado de la cola subsidiaria; que fallTimerserá uno más que el valor del estado de los padres. Condición que contienefallTimer, igual a la velocidad de descenso, implica que el descenso automático ocurre en este cuadro, y para los estados posteriores de este estado el valor fallTimerserá 0.

Cada Searcherpredefinición de una 8-matriz que contiene todos los estados posibles ( 20 × 10 × 4 × 2 × 2 × 4 × 2 A × 2 B), y BFS se ejecuta de manera similar al método mostrado para la matriz. El pseudocódigo que se muestra a continuación describe cómo se obtienen los estados posteriores de los estados inactivos.

 Slide = (Left == PRESSED) or (Right == PRESSED) Rotate = (A == PRESSED) or (B == PRESSED) if Down == RELEASED or Down == PRESSED_FOR_3_FRAMES then if Down == RELEASED then nextDown = PRESSED_FOR_1_FRAME else nextDown = PRESSED_FOR_2_FRAMES end addChild(Down = nextDown) if not Rotate then addChild(A = PRESSED, Down = nextDown) addChild(B = PRESSED, Down = nextDown) end if Slide then addChild() if not Rotate then addChild(A = PRESSED) addChild(B = PRESSED) end else addChild(Left = PRESSED) addChild(Right = PRESSED) if not Rotate then addChild(Left = PRESSED, A = PRESSED) addChild(Left = PRESSED, B = PRESSED) addChild(Right = PRESSED, A = PRESSED) addChild(Right = PRESSED, B = PRESSED) end end else if Down == PRESSED_FOR_1_FRAME then nextDown = PRESSED_FOR_2_FRAMES else nextDown = PRESSED_FOR_3_FRAMES end addChild(Down = nextDown) if not Rotate then addChild(A = PRESSED, Down = nextDown) addChild(B = PRESSED, Down = nextDown) end end 

Como se muestra en el pseudocódigo siguiente, la función addChildtiene en cuenta el orden de los eventos que ocurren en cada cuadro (por ejemplo, desplazamiento, rotación y descenso).

 nextFallTimer = fallTimer + 1 if Left == PRESSED and testPosition(x - 1, y, rotation) then x = x - 1 elseif Right == PRESSED and testPosition(x + 1, y, rotation) then x = x + 1 end if A == PRESSED and testPosition(x, y, nextClockwiseRotation) then rotation = nextClockwiseRotation elseif B == PRESSED and testPosition(x, y, nextCounterclockwiseRotation) then rotation = nextCounterclockwiseRotation end if Down == PRESSED_FOR_3_FRAMES or nextFallTimer >= dropSpeed then if testPosition(x, y + 1, rotation) then y = y + 1 nextFallTimer = 0 else lockTetrimino() return end end childState = states[y][x][rotation][Left][Right][Down][A][B] if not childState.visited then childState.visited = mark childState.predecessor = state childState.fallTimer = nextFallTimer queue.enqueue(childState) end 

Como en la versión anterior, AI.searchdevuelve una cadena de objetos State. Pero en este caso, cada uno Statecontiene muchos botones que deben presionarse en cada cuadro. Los campos x, yy rotationno se usan para manipular formas, pero se pueden usar para verificar el movimiento correcto de las formas.

Aunque el espacio de búsqueda se ha reducido significativamente debido a las limitaciones descritas anteriormente, se tarda de 1 a 3 segundos en completar la búsqueda. Si lo ejecuta, notará una pausa después de crear cada tetrimino. Además, los movimientos se ven muy poco naturales; Por lo general, un giro se realiza un instante antes del bloqueo. Sin embargo, esta IA juega casi de la misma manera que la versión que ignoraba la gravedad, incluso a la velocidad máxima.

Para verificarlo, ejecútelo lua/NintendoTetrisAIGamepadVersion.lua, ubicado en el archivo zip con las fuentes .

Una forma más sencilla de explicar la gravedad es limitar el movimiento de las figuras solo girando, seguido de un cambio y luego descender al fondo. La idea es que si se deshace del deslizamiento y el desplazamiento, la velocidad vertical de las figuras tendrá poco efecto en la IA; todo lo que necesita hacer es entregar la figura a la columna deseada, y la gravedad hará el resto. Otra ventaja de esta técnica es que el espacio de búsqueda es muy pequeño, lo que le permite jugar en tiempo real, sin demora para los cálculos. Sin embargo, el inconveniente de este enfoque es que sin deslizarse y desplazarse, la IA juega mucho peor. Sin embargo, la IA de Tetris, incapaz de jugar en tiempo real, es prácticamente inútil.

Además

Anteriormente, escribí un complemento que simulaba procedimentalmente un jugador en Tetris. Sin embargo, mi proyecto tenía algunas desventajas:

1. El bot apagó la gravedad, lo que le permite realizar deslizamientos y desplazamientos, superando las capacidades del jugador en el nivel mínimo de Nintendo Tetris. Nunca sube las cifras, pero la única forma de bajarlas es un descenso suave y controlado. Es decir, juega en un mundo teórico e idealizado. Para decirlo sin rodeos, hace trampa.
2. . — , . Double, Triple Tetris, — , . 90. , , 29 - .
3. . . . , Tetris .

En esta sección, hablaré sobre un bot avanzado que juega Nintendo Tetris sin desactivar la gravedad. Evalúa el riesgo y lo maneja, esforzándose agresivamente por obtener el máximo número de puntos antes de alcanzar una alta velocidad de descenso.

---

Video

Mira cómo el robot gana la cantidad máxima de puntos de Nintendo Tetris a partir del nivel 19 en todos los videos que se muestran a continuación.

---

Descargar

TetrisAI_2018-01-28.zip

El archivo .zipcontiene:

• src - árbol de código fuente.
• TetrisAI.jar - archivo binario compilado.
• lgpl-2.1.txt - licencia de software libre.

---

Lanzamiento

Prerrequisitos

• Nintaco es un emulador NES / Famicom.
• Tetris (U) [!].nes - Archivo ROM de Nintendo Tetris.

Lanzamiento de complemento

1. Inicie Nintaco y ábralo Tetris (U) [!].nes.
2. Extracto TetrisAI.jarde la descargada .zip.
3. Abra la ventana Ejecutar programa seleccionando Herramientas | Ejecutar programa ...
4. JAR Find JAR… .
5. Load JAR, .
6. Run.
7. , GAME TYPE MUSIC TYPE . D-pad ( ) A-TYPE . Start (Enter), .
8. A-TYPE D-pad ( ) LEVEL 9 . , A Start ( X Enter), 19, .

Vale la pena considerar que el bot está diseñado solo para el nivel 19 y superior. En niveles inferiores, no podrá controlar las piezas.

Referencia de velocidad

Para que el juego vaya más rápido, selecciona Máquina | Velocidad | Max

---

Detalles

Meseta

Por debajo del nivel 10, la velocidad de descenso en cada nivel es ligeramente mayor que en el anterior. Pero en el nivel de 10 y superior hay varias mesetas a las cuales la velocidad permanece constante durante varios niveles. Esto es una consecuencia de la forma en que funciona el mecanismo de activación. La velocidad se presenta como el número de cuadros por descenso, que es un valor entero. Es decir, para niveles más altos no quedan muchas opciones: 10–12, 13–15, 16–18, 19–28 y 29+ son 5, 4, 3, 2 y 1 cuadro para el descenso.

El bot se desarrolló teniendo en cuenta solo la meseta de 19–28. Incluso en cuadros, hace clic en el control del juego "Izquierda", "Derecha", A, B o nada. Y en cuadros extraños, permite el descenso automático sin presionar ningún botón. Parece que el juego no percibe el movimiento horizontal que coincide con la rotación; por lo tanto, cada botón se presiona de forma independiente en cuadros pares.

A diferencia de los maestros que juegan a niveles altos, el bot no aprovecha el cambio automático diferido (DAS), también conocido como repetición automática, y técnicas relacionadas. Su trabajo recuerda más la técnica de vibración del pulgar de Thor Akerlund . Sin embargo, aumenta la frecuencia de vibración al máximo teórico permitido por el juego.

Los jugadores son recompensados ​​con 40, 100, 300 y 1200 puntos por Single, Double, Triple y Tetris. Y los puntos se multiplican por el número de nivel más 1. En otras palabras, para obtener el puntaje máximo, el jugador debe luchar por el número máximo de Tetris, jugando el mayor tiempo posible en niveles altos.

El nivel 19 es el más alto que se puede seleccionar como el inicial, lo que permite que el bot salte directamente a la meseta 19–28. Sin embargo, debido a un error en el mecanismo de cálculo de nivel que mencioné en la parte anterior, el juego pasará al nivel 20 después de despejar 140 filas, en lugar de las 200 esperadas. Después de eso, el juego cambiará los niveles cada 10 filas. Sin embargo, después de alcanzar 230 filas, el bot se levantará de la meseta y se rendirá rápidamente. Es decir, necesita marcar tantos Tetris como sea posible antes de limpiar 230 filas.

Descenso suave

El descenso suave también puede aumentar el número de puntos. Para obtener puntos, la figura debe bajarse suavemente para bloquear el campo de juego. Cualquier descenso suave a corto plazo que ocurra en el camino al posicionar una figura no afectará la puntuación. Si el descenso es exitoso, el jugador recibirá un punto por cada línea cruzada durante el descenso suave. Y el valor resultante no se multiplica por el número de nivel, incluso si un descenso suave lleva a despejar las filas.

El descenso suave tiene poco efecto en el puntaje general. Sin embargo, si es posible, el bot completa la colocación de la figura haciendo clic en "Abajo" para obtener estos puntos. En casos raros, puede promediar la diferencia entre un puntaje muy alto y exceder el puntaje máximo.

Algoritmo AI

Al crear una forma, el bot explora cada posible colocación de las formas actuales y siguientes. La ubicación permitida es la posición en la que la figura descansa sobre las celdas ocupadas o en el piso del campo de juego. Desde el lugar de creación de la figura, esta posición se puede alcanzar a través de una secuencia de movimientos horizontales, giros y descensos. Las ubicaciones válidas y las secuencias de ruta se encuentran utilizando BSF.

Colocar una pieza en el campo de juego tiene consecuencias: 4 celdas vacías se ocupan, y todas las filas llenas se borran, dejando que las filas bajen. Para cada ubicación permitida de la figura actual y las consecuencias asociadas con ella, el bot verifica cada ubicación permitida de la siguiente figura, evaluando la combinación de consecuencias. Dicha cadena de búsqueda se presenta SearchChain.

Cada una de las consecuencias combinadas se transfiere a una función de evaluación que calcula el contenido del campo de juego. La combinación con la puntuación más baja gana y la pieza actual se coloca en consecuencia. Los resultados de la cadena de búsqueda solo afectan la forma actual. Al crear la siguiente figura, se evalúa en combinación con la figura que le sigue, y así sucesivamente.

Función de evaluación

La función de evaluación es una suma ponderada de los siguientes parámetros:

• El número total de filas eliminadas es el número de filas eliminadas mediante la adición de ambos tetriminos.
• – , . — , , .
• - – .
• – , -.
• – , . . .
• – . , 1. , , .
• – , . — , — .
• – . , (20).
• – . , 0.
• – , ( ) .
• : — , ( ) . . . .
• – . , 1 , 1, — 0.
• – .
• – .
• – .
• – . .
• – .

Aprendizaje automático

Para encontrar los pesos de la función de evaluación, utilizamos una variante del método de optimización de enjambre de partículas (PSO) descrito en la nota al pie [1]. Para obtener un buen comportamiento convergente, se aplican los coeficientes de inercia y aceleración propuestos. Y los tamaños máximos de los pasos de partículas están determinados por la limitación de sus valores de velocidad.

Durante cada iteración, las partículas se evaluaron en paralelo para aprovechar al máximo los recursos informáticos disponibles. Además, después de que se detectó la convergencia (sin mejoras después de un cierto número de iteraciones), el PSO se configuró para reiniciarse automáticamente con pesos seleccionados al azar, lo que nos permitió explorar aún más el espacio de búsqueda.

Cada vector de posición de partículas se evaluó simulando la finalización de 100 lotes en una meseta de niveles 19–28. Un lote completo implica la limpieza de 230 filas, pero muchas terminaron con un desbordamiento del campo. Las puntuaciones de los lotes se ordenaron y las puntuaciones de partículas se determinaron como el promedio de 33 de cada 100 lotes. La idea era elegir en función de la agresividad. Las partículas en el tercio superior se acostumbran solo a las secuencias deseadas de figuras, lo que limita la necesidad de un juego conservador. Como resultado, tienden a llevar el juego habitual al límite, esperando el próximo "palo".

Se generaron secuencias de patrones para 100 lotes antes de la PSO, y las mismas secuencias se usaron una y otra vez. Esto era necesario para arreglar el espacio de búsqueda, de modo que las opciones de solución pudieran compararse entre sí. Las secuencias se crearon utilizando la lógica de un PRNG Nintendo Tetris real, que está diseñado para reducir las posibilidades de que los duplicados se sigan. Pero PRNG también tiene puntos débiles (consulte la sección "Elegir Tetrimino" de un artículo anterior): no selecciona las cifras de manera uniforme.

Los intentos iniciales dieron como resultado que los bots actuaran de manera demasiado agresiva. Si superaban la meseta 19–28, generalmente llegaban al puntaje máximo. Pero, desafortunadamente, a menudo demasiado pronto llevaron a desbordamientos de campo. En respuesta a esto, se tomaron cuatro pasos para "calmar" a los bots:

1. : Tetris, . «» . . ; 230 . , Tetris . Single, Double Triple. ; .
2. . , , 7 . .
3. , , . , 7 .
4. , , . , . , .

Después de aplicar todas estas reglas para "calmar" a los bots, el método PSO dio los siguientes pesos:

Parámetro	Peso
Número total de filas despejadas	0.286127095297893900
Altura total de bloqueo	1.701233676909959200
Número total de células de pozo	0.711304230768307700
Número total de pozos profundos	0.910665415998680400
El número total de agujeros en las columnas.	1.879338064244357000
Agujeros de columna ponderados totales	2.168463848297177000
Número total de profundidades de agujeros en columnas	−0.265587111961757270
Profundidad mínima del agujero de columna	0.289886584949610500
Profundidad máxima del agujero de columna	0.362361055261181730
El número total de transiciones en columnas.	−0.028668795795469625
Saltos de línea totales	0.874179981113233100
Alturas totales de columna	−0.507409683144361900
Altura del montón	−2.148676202831281000
Dispersión de alturas de columna	−1.187558540281141700
Número total de celdas ocupadas	−2.645656132241128000
Número total ponderado de celdas ocupadas	0.242043416268706620
Dispersión de alturas de columna	0.287838126164431440

Dado que la cadena busca una combinación que minimice la función de evaluación, los parámetros que tienen pesos positivos pueden considerarse bonificaciones, y el resto, multas. Pero los pesos no muestran necesariamente la importancia de los parámetros correspondientes; no están normalizados, por lo tanto no se pueden comparar.

Fuerza AI

Para evaluar la fuerza de la IA, se obtuvieron aproximadamente 1,7 millones de resultados (en puntos) de juegos simulados en una meseta de 19–28. La puntuación no refleja el juego en el nivel 29 o superior, y no tiene en cuenta los puntos obtenidos del descenso suave. Sin embargo, incluye juegos completados prematuramente debido a desbordamientos de campo. La lógica PRNG de Nintendo Tetris se utilizó para generar las secuencias de Tetrimino.

Entre estos resultados, el puntaje más alto es 1,313,600, el mínimo es 0. El

promedio es 816,379 y parece ser pequeño. Pero como se menciona a continuación, los datos están distorsionados, por lo que la puntuación media de 989.200 puntos da una mejor idea del valor típico.

Como se indicó anteriormente, PSO optimizó los pesos en función del promedio del mejor tercio de los lotes. En este caso, el puntaje promedio del mejor tercero es 1 108 860. De hecho, el puntaje promedio del mejor 75% es 1,000,000. El

bot tiene una probabilidad del 47% de alcanzar el límite de puntos al nivel 29. Tiene una probabilidad del 61% de obtener 900,000 puntos al nivel 29. El gráfico a continuación muestra las probabilidades de anotar hasta el nivel 29.


Parece que la probabilidad disminuye linealmente a unos 900,000 puntos. Luego entra en una curva sigmoidea invertida.

A continuación se muestra un histograma suavizado con el número de partidos para cada uno de los puntos anotados. Su forma está determinada por la derivada del gráfico que se muestra arriba.


Si ignora las fluctuaciones, hasta aproximadamente 900,000 es plano, y luego entra en una distribución normal con el centro alrededor de 1,050,000 puntos. Las razones de las fluctuaciones no están claras. Parece que la cantidad de puntos prefiere saltar en incrementos de 20,000 puntos. Quizás esto se deba al ciclo de construcción del montón y a obtener Tetris.

Asignación de RAM y ROM

Para manipular la memoria de la CPU, transmitir clics en los botones y recibir eventos de representación de cuadros, el complemento utiliza la API de Nintaco . Todas las direcciones de memoria se descubrieron utilizando las herramientas de depuración de Nintaco y se agregó información a la wiki de Data Crystal ROMhacking.net . En el código fuente, se ven como constantes en la interfaz Addresses.

---

Referencias

1. van den Bergh, F.; Engelbrecht, AP (2006)
   A study of particle swarm optimization particle trajectories
   In: Information Sciences 176 (2006) (pp. 937–971)
   Retrieved from http://researchspace.csir.co.za/dspace/bitstream/handle/10204/1155/van%20den%20bergh_2006_D.pdf