Identificar y recopilar datos clave.
Exploré varios algoritmos para optimizar y reducir el espacio de búsqueda de todos los combos posibles. Sin embargo, el hecho de que cada carta pueda aparecer dos veces aumenta el número de combinaciones potenciales, lo que dificulta el seguimiento y la validación de cada una. Mientras participaba en una competencia en Codeforces, encontré un problema que me recordó a ‘problema de la isla‘, lo que me dio una nueva visión del enfoque del sistema de evaluación manual.
Podemos representar la mano como una cuadrícula 2D de tamaño 4×13, donde cada columna representa los rangos del 1 al 13 y cada fila corresponde a los 4 colores. Cada celda de esta cuadrícula contiene el número de cartas que tenemos en mano en nuestro caso, ya sea 1, 2 o 0. Esto nos permite dividir la mano en «islas», que se definen como grupos de celdas terrestres conectadas con recuentos de 1 o 2 según las siguientes reglas de conectividad:
1. Dos celdas se consideran conectadas si comparten un lado (izquierdo, derecho, superior o inferior) en la cuadrícula.
2. Todas las celdas de la misma columna están igualmente conectadas si ambas contienen al menos 1, incluso si no son adyacentes (arriba o abajo).
EXP ‘Mano A’: 11C 3H 4H 11D 3D 5H 9D 2H 6H 3C 4H 3D 4D 5H 12D 3C
Nuestra primera tarea es identificar y etiquetar todas las islas distintas. Dado que cada isla es independiente de las demás, podemos hacer la vida más fácil asignando cada isla a un tipo de clase, llamémoslo _cardGraph. Esta clase será responsable de esta isla en cuanto a operaciones de extracción, modificación o eliminación.
Para mayor claridad, aislaremos una isla y trabajaremos en ella en secciones futuras, para que sea más fácil de seguir. Si te ayuda, puedes pensar en cada isla como un gráfico conectado, como se muestra en la siguiente figura:
Ahora, si tomas varias islas de ejemplo e intentas extraer las combinaciones posibles, notarás que ciertas cartas tienen funciones únicas en la creación de combinaciones potenciales. A este tipo de tarjetas las llamaremos puntos de control O Cuentas en definitiva, porque juegan un papel vital a la hora de reducir significativamente el espacio de búsqueda como verás en los siguientes pasos.
Cuentas: Para que una carta sea considerada Cpts, debe estar en una posición en la que debemos elegir en qué fusión (ejecución o conjunto) agregarla. Si una carta puede encajar naturalmente en varias combinaciones sin forzar una elección (por ejemplo, una carta duplicada con dos opciones de combinación, cada carta se agregará a una combinación), no se considerará un Cpt.
En el caso de nuestro ejemplo de isla, el 3 de corazones se identifica como cpts. A continuación encontrarás todas las combinaciones a las que podría unirse el 3 de Corazones, una a la vez.
Nuestro siguiente paso es marcar cada tarjeta que califique como Cpts. Para hacer esto, crearemos una tabla de 4×13 (en tipo byte), llamémosla _flagMap. Ahora, para una mayor eficiencia de la memoria, puede convertirla en una tabla compartida, cada instancia de _cardGraph creada desde main puede hacer referencia a ella y usarla. En esta tabla, a cada mapa de una isla se le asignará un flujo de bits en el índice correspondiente en _flagMap, este byte representará sus ubicaciones potenciales en diferentes ejecuciones o conjuntos. Si una tarjeta se considera Cpts, se almacenará en una pila (la necesitaremos más adelante), a la que llamaremos _cptsStack. Aquí hay un desglose de la estructura de bytes: el primer bit indica si la tarjeta pertenece a una ejecución, el segundo bit indica su ubicación en una ejecución adicional, el tercer bit representa si pertenece a un conjunto y el cuarto bit especifica si pertenece . a varios conjuntos.
Aquí hay un ejemplo de una secuencia binaria: 00000111 Aquí tenemos:
• El primer bit (1) significa que la tarjeta puede pertenecer a una serie.
• El segundo bit (1) significa que la tarjeta puede pertenecer a una segunda tirada.
• El tercer bit (1) significa que la tarjeta pertenece a un conjunto.
• El cuarto bit (0) significa que la tarjeta no pertenece a un segundo conjunto.
Podríamos estar en el caso de que la configuración sea 00000101 para una tarjeta (sin copia), lo que significa que la tarjeta pertenece a una serie o conjunto. U otra configuración podría ser 00000011, lo que significa que la tarjeta pertenece a dos ejecuciones diferentes.
Para identificar un cpt, simplemente cuente los «1» en su representación binaria. Si este número excede el número total de esta carta en la mano, se considera un conteo. Por ejemplo, si una tarjeta aparece dos veces (es decir, tiene dos copias) y su representación binaria es 00000101, no es un cpts. Sin embargo, si la representación binaria es 00000111 como en el ejemplo, entonces se considera cpts.
En nuestro ejemplo de isla, así es como se vería la tabla _flagMap:
Una vez que hayamos poblado el _flagMap e identificado los cpts, la siguiente tarea es dividir la isla en líneas horizontales y verticales. ¿Pero por qué? Dividir el gráfico del mapa en estas líneas simplifica el proceso de identificación de caminos y conjuntos porque nos permite centrarnos en secuencias contiguas de mapas que se pueden procesar de manera más eficiente. Como puedes adivinar, las líneas verticales representarán las eliminatorias, mientras que las líneas horizontales representarán las carreras.
Almacenaremos cada fila horizontal en una lista de tuplas, donde el primer elemento representa el índice inicial de la fila y el último elemento representa el índice final (inclusive). Para filas verticales, simplemente almacene el índice de la columna en una lista.
Consejo: Podemos realizar esta tarea con el paso de representación de bits en un solo bucle, logrando una complejidad O(n).
Generar combos
Ahora, hagamos una pausa y recapitulemos: identificamos los puntos de control (CPT) y los almacenamos en _cptsStack. También descompusimos la isla en líneas verticales y horizontales y llenamos el _flagMap con una representación de los bits del mapa.
Con nuestros datos listos solo queda usarlos para generar todos los combos válidos posibles en la isla. ¿Pero cómo hacemos esto? Aquí hay un enfoque simplificado:
1. Asignar ubicaciones válidas para los puntos de control (Cpts):
Tomamos la representación binaria de un cpt de _flagMap, que indica todas las ubicaciones posibles para este cpt. A continuación, examinamos el número de copias de los cpts en _cardGraph y ajustamos su representación binaria a una configuración actual válida. Por ejemplo, si cpts tiene una representación binaria de 00001111 y 2 copias, podemos generar todas las ranuras válidas para él, es decir, C(4,2)=6C(4,2) = 6C(4,2)= 6. Las posibles combinaciones serían 0011, 0101, 1100, 1010, 1001 y 0110.
2. Usando DFS para configurar todas las combinaciones posibles para cada Cpts:
Usaremos una búsqueda en profundidad (DFS) para iterar sobre ubicaciones válidas para cada cpt, como se muestra en el paso 1. Cada nodo en el árbol DFS representa una posible ubicación para un cpt determinado, por lo que cada ruta DFS única representa una ubicación válida. . configuración combinada. Para cada nodo «hoja» (final de la ruta DFS), pasamos al siguiente paso.
3. Genera combos:
En este paso, escaneamos las líneas horizontales y verticales de la isla para identificar ejecuciones, conjuntos y una lista de volcados. Esto se hace en dos pasadas para cada línea, de la siguiente manera:
- Pase 1: Para una línea horizontal, por ejemplo, continuamente agregamos mapas de [line start to line end] en una lista para formar una carrera. Dejamos de agregar if ( card_bit_representation | 00000001 == 0 ). Si la duración de la carrera es mayor o igual a 3, se suma al combo de carrera; de lo contrario, cada tarjeta va a la lista de volcado y seguimos intentando formar otro conjunto hasta llegar al final de la línea.
- Pase 2: Repita el proceso, esta vez buscando tarjetas que coincidan con un patrón de bits diferente con una operación (00000010). Esto nos permite identificar posibles segundas ejecuciones.
El mismo enfoque se aplica a la minería de conjuntos, pero utilizamos operaciones bit a bit con 00000100 y 00001000.
4. Guarde el combo válido y proceda a la siguiente configuración DFS:
Después de completar todas las ejecuciones, conjuntos y volcados del combo actual, guardamos el combo y luego pasamos a la siguiente configuración de DFS para repetir el proceso. De esta manera exploramos sistemáticamente todas las configuraciones potenciales para combos válidos.
Si ha codificado todo correctamente y le proporciona nuestra isla de ejemplo: «2H3H4H5H4H5H6H3C3C3D3D4D», debería desglosarse como se muestra a continuación. Tenga en cuenta que agregué cálculos a cada combo generado para que podamos tener una idea de cómo actuará la IA.
En el próximo artículo, profundizaré en el resto del sistema, centrándome en la modificación dinámica de las manos y la estrategia de IA. Si has seguido hasta aquí, no te resultará difícil ver cómo podemos optimizar la adición y eliminación de tarjetas, además de incorporar las dos reglas que reservamos al principio. ¡Estén atentos y hasta la próxima! “Espero 😉”.
A menos que se indique lo contrario, todas las imágenes son creadas por el autor utilizando Lucidchart, Gimp y Python.
