Identificación y recopilación de datos clave
Exploré varios algoritmos para optimizar y reducir el espacio de búsqueda para todos los combos posibles. Sin embargo, el hecho de que cada carta pueda aparecer dos veces aumentó la cantidad de combinaciones potenciales, lo que dificulta el seguimiento y la validación de cada una. Mientras competía en Codeforces, encontré un problema que me recordó el ‘problema de la isla,’ lo que me dio una nueva visión sobre cómo abordar el sistema de evaluación de manos.
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 palos. Cada celda de esta cuadrícula contiene el recuento de cartas en la mano, en nuestro caso 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, arriba o abajo) en la cuadrícula.
2. Todas las celdas dentro de la misma columna también están conectadas si ambas contienen al menos unos, incluso si no son adyacentes (arriba o abajo).
EXP de la ‘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 hacernos la vida más fácil asignando cada isla a un tipo de clase, llamémosla _cardGraph. Esta clase será responsable de esa isla en términos de operaciones de extracción, modificación o eliminación.
Para mayor claridad, aislaremos una isla y trabajaremos en ella en las próximas secciones, para que le resulte más fácil seguirla. Si te ayuda, puedes pensar en cada isla como un gráfico conectado, como se muestra en la siguiente figura:
Ahora, si tomas varios ejemplos de islas e intentas extraer las combinaciones posibles, notarás que algunas cartas tienen funciones únicas al diversificarse hacia combinaciones potenciales. A este tipo de tarjetas las llamaremos puntos de control o Cptos en definitiva, ya que juegan un papel fundamental al reducir significativamente el espacio de búsqueda como verás en los siguientes pasos.
Cptos: Para que una tarjeta se considere Cpts, debe estar en una posición en la que tengamos que elegir a qué combinación (ejecución o conjunto) agregarla. Si una tarjeta puede encajar naturalmente en varias combinaciones sin forzar una elección (por ejemplo, una tarjeta duplicada con dos opciones de combinación, cada tarjeta se agregará a una combinación), no se considerará Cpts.
En el caso de nuestro ejemplo de isla, el 3 de corazón se identifica como cpts. A continuación se muestran 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 mejorar la eficiencia de la memoria, puede convertir esta en una tabla compartida; cada instancia de _cardGraph creada manualmente puede hacer referencia a ella y usarla. En esta tabla, a cada tarjeta en 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 califica como 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 múltiples conjuntos.
Aquí hay un ejemplo de un flujo de bits: 00000111 Aquí tenemos:
• El primer bit (1) significa que la tarjeta puede pertenecer a una ejecución.
• 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 ejecución o un 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 de bits. Si este recuento excede el número total de esa carta en la mano, se considera cpts. Por ejemplo, si una tarjeta aparece dos veces (es decir, tiene dos copias) y su representación de bits es 00000101, no es un cpt. Sin embargo, si la representación de bits es 00000111 como en el ejemplo, entonces califica como 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 descomponer la isla en líneas horizontales y verticales. ¿Pero por qué? Dividir el gráfico de tarjetas en estas líneas simplifica el proceso de identificación de ejecuciones y conjuntos, ya que nos permite centrarnos en secuencias contiguas de tarjetas que se pueden procesar de manera más eficiente. Como puedes adivinar, las líneas verticales representarán los conjuntos, mientras que las líneas horizontales representarán las carreras.
Almacenaremos cada línea horizontal en una lista de tipo tupla, donde el primer elemento representa el índice inicial de la línea y el último elemento representa el índice final (inclusive). Para las líneas verticales, basta con almacenar el índice de la columna en una lista.
Consejo: Podemos realizar esta tarea junto con el paso de representación de bits en un solo bucle, logrando una complejidad O(n).
Generar combos
Ahora, tomemos un descanso y recapitulemos: hemos identificado los puntos de control (CPT) y los hemos almacenado en _cptsStack. También descompusimos la isla en líneas verticales y horizontales, y completamos el _flagMap con representación de bits de tarjeta.
Con nuestros datos listos lo que queda es utilizarlos para generar todos los posibles combos válidos de la isla. ¿Pero cómo hacemos eso? Aquí hay un enfoque simplificado:
1. Asignar Ubicaciones Válidas para los Puntos de Control (Cpts):
Tomamos la representación de bits de un cpt de _flagMap, que indica todas las ubicaciones posibles para ese cpt. Luego, observamos el número de copias de los cpts en _cardGraph y ajustamos su representación de bits a una configuración válida actual. Por ejemplo, si cpts tiene una representación de bits de 00001111 y 2 copias, podemos generar todas las ubicaciones válidas para él, que es C(4,2)=6C(4,2) = 6C(4,2)=6. Las posibles combinaciones serían 0011, 0101, 1100, 1010, 1001 y 0110.
2. Uso de DFS para configurar todas las combinaciones posibles para cada Cpt:
Usaremos una búsqueda en profundidad (DFS) para iterar sobre las 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 ruta válida. configuración combinada. Para cada nodo “hoja” (final de la ruta DFS), procedemos al siguiente paso.
3. Generando Combos:
En este paso, iteramos sobre 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, agregamos continuamente tarjetas de [line start to line end] en una lista para formar una carrera. Dejamos de agregar if ( card_bit_representation | 00000001 == 0 ). Si la longitud de la carrera es mayor o igual a 3, la agregamos al combo de carrera; de lo contrario, cada tarjeta va a la lista de volcado y continuamos intentando formar otra serie 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 la operación u (00000010). Esto nos permite identificar posibles segundas ejecuciones.
El mismo enfoque se aplica a la extracción de conjuntos, pero utilizamos operaciones de bits con 00000100 y 00001000.
4. Registre el combo válido y pase 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 DFS para repetir el proceso. De esta manera, exploramos sistemáticamente todas las configuraciones potenciales para combos válidos.
Si codificó todo correctamente y lo alimentó con nuestro ejemplo de isla: “2H3H4H5H4H5H6H3C3C3D3D4D”, debería descomponerse como se muestra a continuación. Observe que agregué algunos 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 la mano y la estrategia de la IA. Si has seguido hasta aquí, no te resultará difícil ver cómo podemos optimizar la adición y eliminación de tarjetas, así como incorporar las dos reglas que dejamos de lado al principio. ¡Estén atentos y nos vemos la próxima vez! “ojalá 😉”.
A menos que se indique lo contrario, todas las imágenes son creadas por el autor utilizando Lucidchart, Gimp y Python.