« Curso MOOC de NetLogo… « || Inicio || » Sobre el modelado mat… »

Teoría Algorítmica de la Información y el juego del GO

Última modificación: 3 de Diciembre de 2016, y ha tenido 1386 vistas

Etiquetas utilizadas: || || || ||

Sobre el Go

El Go (también conocido como igo en japonés, weiqi en chino, o baduk en coreano) es un juego de mesa famoso por las complejas estrategias que se pueden desarrollar en él a pesar de tener unas reglas muy simples.

El juego es para dos jugadores que, alternativamente, colocan piedras negras y blancas sobre las intersecciones libres de una cuadrícula de 19x19 líneas. El objetivo es controlar una porción más grande del tablero que el oponente. Un conjunto de piedras del mismo color que son adyacentes entre sí forman un grupo que se comporta como una unidad. Una piedra o grupo de piedras se captura y retira del juego si no tiene intersecciones vacías adyacentes (libertades); esto es, si se encuentra completamente rodeada de piedras del color contrario. [Si quieres saber más sobre este juego, puedes visitar esta página.]

Por tanto, situar piedras juntas ayuda a protegerlas entre sí y dificulta que sean capturadas porque suman sus libertades, pero por otro lado, colocarlas con una cierta separación entre ellas hace que se tenga influencia sobre una mayor porción del tablero. Simultáneamente, situar piedras demasiado pegadas a los bordes del tablero facilita conseguir áreas en las que estar a salvo, pero son áreas pequeñas; mientras que jugar en las zonas centrales aumenta la capacidad de capturar territorio, pero aumenta la inseguridad. Parte de la dificultad estratégica del juego surge a la hora de encontrar un equilibrio entre estas alternativas opuestas. En su enfrentamiento, los jugadores pueden actuar de manera ofensiva o defensiva y deben elegir entre tácticas de urgencia que les permitan mantener vivos sus grupos de piedras, y planes a largo plazo más estratégicos que les ayuden a ganar más territorio y seguridad.

En términos de combinatoria, el Go es un juego de suma nula (la ganancia o pérdida de un participante se equilibra exactamente con las pérdidas o ganancias de los otros participantes), con información perfecta (los jugadores, cuando tienen que realizar un movimiento, tienen un conocimiento completo de lo que ha sucedido desde el principio del juego), partidista (en cada paso, las opciones de cada jugador pueden ser distintas) y determinista (no hay intervención del azar). En consecuencia, cae dentro de la misma clase que el ajedrez, las damas, o el reversi.

Se dice que en la actualidad el Go es el juego más complejo del mundo debido al elevadísimo número de variaciones que se pueden producir en una partida individual. El tamaño del tablero y la falta de restricciones permiten un amplio abanico de estrategias en las que se puede expresar la individualidad y personalidad de los jugadores. Las decisiones que se tomen en una parte del tablero pueden influir, y ser influidas, por las situaciones que se den en zonas relativamente lejanas, y los primeros movimientos del juego pueden determinar la naturaleza de los conflictos que nos encontraremos cientos de movimientos más tarde. Es decir, es sensible a las condiciones iniciales, está fuertemente conectado y se rige por reglas locales muy simples...

La complejidad de este juego hace que la simple descripción de estrategias elementales rellene muchos libros introductorios, y de hecho se estima que el número de posibles jugadas de Go excede el número de átomos en el universo observable.

En Go, al igual que ocurre en ajedrez, el rango de un jugador indica su habilidad con el juego. Tradicionalmente, los rangos se miden mediante un sistema de grados de kyu y dan, el mismo sistema que ha sido adoptado por diversas artes marciales (recientemente, se han adaptado sistemas de calificación similares al Elo, pero habitualmente ofrecen un mecanismo para calcular el equivalente en kyu o dan). Los grados de kyu (abreviados k) son considerados grados de estudiante; su número disminuye a medida que el nivel de juego aumenta, de modo que el 27k es el más débil y 1k es el grado de kyu más fuerte. Los grados de dan (abreviados d) se consideran grados de maestro, y se incrementan de 1d a 7d. Los jugadores profesionales obtienen un grado especial de dan, el dan profesional (abreviado p), cuyo máximo grado es el 9d.

Sobre la Teoría Algorítmica de la Información

Como escribe G. Chaitin en el prólogo a la segunda edición del libro "Information and Randomness: An Algorithmic Perspective" de C. Calude, la Teoría Algorítmica de la Información (TAI, o AIT por sus siglas en inglés) es el resultado de poner la Teoría de la Información de Claude hannon y la Teoría de la Computabilidad de Alan Turing en una coctelera y agitar vigorosamente. La idea básica consiste en medir la complejidad de un objeto por el tamaño del menor programa que lo calcula.

Por ejemplo, según la definición clásica de Claude Shannon, el contenido informativo de las siguientes cadenas binarias es la misma (ya que sólo se aplica la entropía de primer orden, esencialmente, el número de 0's y 1's que contienen):

1100100001100001110111101110110011111010010000100101011110010110
1111111111111111111111111111111100000000000000000000000000000000

Sin embargo, la primera secuencia ha sido producida por un muestreo aleatorio, mientras que en la segunda secuencia se utiliza un "programa" muy sencillo:

 Repite 32 veces: imprime 1
Repite 32 veces: imprime 0

Desde el punto de vista de la TAI, la primera secuencia tiene más información algorítmica, ya que es mucho más compleja de describir por medio de un programa. Quizás la única forma de describirla sea haciendo que el programa tenga almacenada la propia cadena y la repita paso a paso... no se puede comprimir. Es decir, la información algorítmica de una cadena es mayor cuanto menos puede ser comprimida por medio de un programa y mñas información de la propia cadena hay que darle a este para poder replicarla.

La complejidad de longitud de programa (que es como a veces se llama a lo anterior) es un concepto mucho más profundo que la complejidad de tiempo de ejecución que, sin embargo, es de una gran importancia práctica en el diseño de algoritmos eficientes.

La TAI estudia, principalmente, estas medidas de complejidad sobre cadenas (sucesiones de elementos de un alfabeto prefijado), y como la mayoría de los objetos matemáticos pueden ser descritos en términos de cadenas, o como el límite de una secuencia de cadenas, puede ser usado para estudiar una amplia variedad de objetos matemáticos, incluyendo números enteros o números reales, imágenes discretizadas, lenguajes formales, etc.

Debe tenerse en cuenta que las que consideramos "cadenas aleatorias" no contienen ningún patrón predecible y por tanto no son compresibles, lo que establece relaciones interesantes entre complejidad, aleatoriedad, compresibilidad y predecibilidad.

En general, es imposible encontrar "el menor programa" que comprime un objeto, por lo que no encontraremos metodos prácticos para calcular la complejidad del objeto, pero sí podremos hacer estudios comparativos de diversos objetos viendo cómo son los programas que los codifican sobre un lenguaje de programación prefijado. Por tanto, aunque no seamos capaces de decir cómo de complejo es un objeto, sí seremos capaces de decir, bajo ciertas suposiciones, que un objeto es más complejo que otro.

Compresión de datos

Con la compresión de datos se pretende almacenar la misma información, pero empleando la menor cantidad de espacio. Para ello, se usan un par de programas que sean capaces de comprimir la información y descomprimirla. Existen diferentes tipos de compresores: compresores con pérdida y compresores sin pérdida. Los primeros se usan cuando es suficiente recuperar una versión aproximada de la información original (por ejemplo, en una imagen, en la que únicamente buscamos que la impresión visual tras descomprimirla sea la misma), mientras que los segundos son necesarios cuando precisamos de una copia exacta al original tras la descompresión (por ejemplo, cuando comprimimos un archivo de texto o un fichero ejecutable). En el caso de estudiar la complejidad de un objeto analizando el tamaño de su versión comprimida, será habitual hacer uso de compresores sin pérdida.

La mayoría de compresores están basados en el algoritmo LZW (Lempel-Ziv-Welch) que se basa en un análisis inicial de la cadena para identificar partes repetidas y así formar un diccionario de equivalencias que asigne códigos breves a estas subcadenas. En una segunda etapa, se convierte la cadena inicial usando los códigos equivalentes para las subcadenas repetidas. Por tanto, requiere de dos etapas, una de análisis y otra de conversión, junto con el almacenamiento del diccionario que se ha construido, lo que incrementa el tamaño del archivo de salida.

Dos usos muy extendidos de la compresión de datos los encontramos en los compresores de archivos (ZIP, RAR, LZW,...) y en la transmisión de archivos multimedia por medio de canales de información (JPEG, PNG, ... en imagen; MPG, MOV, AVI... en video; MP3, WAV, OGG,... en audio).

En particular, podremos hacer uso de los compresores de datos para poder medir la complejidad de las estructuras de datos sobre las que operan.

Poniendo todo junto

La pregunta que fusiona todo lo anterior es... ¿cómo puedo medir la complejidad de una partida de Go?

La idea que usaremos a partir de todo lo que hemos presentado más arriba es relativamente sencilla: si una partida de Go se produce como una sucesión de movimientos sobre un tablero, podemos representar un instante de la partida como un cuadrado de 19x19 píxeles (uno por cada intersección del tablero) con tres posibles colores; por ejemplo, si la intersección está vacía: pixel negro; si la intersección está ocupada por una piedra blanca: pixel rojo; y si está ocupada por una piedra negra: pixel azul (el uso de estos tres colores se basa en su cercanía a los canales RGB con los que suelen almacenarse las imágenes). En consecuencia, un instante de la partida se podrá asociar a la complejidad (compresión) de la imagen asociada a la configuración que representa. Por tanto, a cada partida se le puede asociar una función que mide la evolución de complejidad de la distribución de las piedras en el tablero a lo largo del tiempo (turnos). 

                        

= 84 bytes

¿Habrá alguna relación entre la complejidad de la partida y la forma de esta función? Como suponemos que la complejidad de una partida debe estar relacionada con el rango de los jugadores que intervienen, sería lógico pensar que las curvas que describen las partidas entre jugadores de rango inferior y aquellas entre jugadores de rango superior deben presentar diferencias apreciables.

Con esta idea en mente hemos realizado el siguiente estudio:

  1. Dividimos el conjunto de rangos en las siguientes horquillas: Pro (profesional), 1d-7d, 1k-10k, 10k-20k20k-30k.
  2. Para cada una de las horquillas anteriores bajamos un conjunto de partidas reales (en formato SGF) entre jugadores de esa horquilla (ambos jugadores debían pertenecer a la misma horquilla). El número de partidas en cada horquilla ronda la cantidad de 1000. La razón de usar un conjunto elevado de partidas es, evidentemente, para mitigar las posibles variaciones de la muestra.
  3. Con el fin de realizar un análisis comparativo, y como referente, generamos 1000 partidas aleatorias (grupo Rnd). Estas partidas son aleatorias pero reales, es decir, cada "jugador" coloca al azar una de sus piedras, pero siguendo las reglas del juego (por lo que se eliminan las piedras capturadas, se impiden movimientos prohibidos, etc.)
  4. Para cada partida calculamos la curva de complejidad que representaban las configuraciones que produce (para ello, utilizamos el algoritmo de compresión de imágenes en PNG, que es suficientemente bueno y sin pérdida).
  5. Calculamos la curva media de todas las partidas pertenecientes a la misma horquilla de rangos.
  6. Representamos las curvas medias de cada horquilla... obteniendo los resultados que se muestran a continuación:

(Nota: el tablero inicial está vacío, pero su complejidad no es 0, sino una cantidad fija que representa información que no está relacionada con la imagen en sí, sino con el algoritmo de compresión y descompresión, formato del archivo, etc... y esta cantidad ha sido sustraida de cada una de las curvas)

¿Qué conclusiones podemos extraer?

Como parece natural, las partidas al azar son las que tienen una mayor complejidad, ya que no debe haber un patrón que las dirija. La imagen muestra que la complejidad está directamente relacionada con el nivel, de forma que, como parecería natural suponer, las partidas con jugadores de mayor rango tienen complejidad más alta.

Sin calculamos las diferencias entre las curvas de cada nivel y la curva aleatoria (para comparar los rangos entre sí), obtenemos las siguientes curvas:

Que nos da información acerca de la verdadera diferencia de complejidad entre niveles (obsérvese ahora que las curvas más altas son las más "simples", ya que se diferencian más de la complejidad mayor que es la aleatoria). Destaca la diferencia, desde los primeros movimientos, entre el nivel inferior (20k-30k) y el resto, así como la proximidad entre la complejidad de los rangos 1d-7d y 1k-10k. En este último caso, parece que la diferencia principal entre ambos niveles se produce en los movimientos finales (a partir del 250), donde hay que saber resolver las situaciones de conflicto que se han ido generando.

Supongo que como soy un simple aficionado no soy capaz de extraer mucha más información del estudio anterior, pero parece que los resultados confirman que, al menos, la complejidad puede ser una herramienta interesante para abordar ciertos problemas de clasificación en juegos. Por supuesto, sería deseable disponer de una base de datos de partidas reales grabadas que permitiesen un análisis mucho más detallado de las horquillas de rangos, pero se plantean algunas cuestiones que pueden ser interesantes:

  • ¿De qué forma las variaciones en su curva de complejidad pueden reflejar los momentos importantes de una partida?
  • ¿Podría establecerse un método para, a partir de las curvas de un par de jugadores de un nivel similar, decidir qué rango asignarles?
  • ¿Cómo se podría afrontar el problema de partidas entre jugadores con niveles dispares?, ¿seríamos capaces de ver, a partir de la curva, qué diferencia de nivel hay?
  • Si se comprime toda la partida como una "película de imágenes", ¿podríamos establecer comparativas entre partidas puntuales? Realmente, este experimento se ha intentado usando el algoritmo de compresión de videos, APNG (Animated PNG), pero no es capaz de comprimir nada en la tercera dimensión, en la temporal, por lo que cada fotograma era simplemente un añadido del anterior. Quizás usando un algoritmo de compresión sin pérdida adecuado podríamos arrojar alguna luz sobre su uso.

« Curso MOOC de NetLogo… « || Inicio || » Sobre el modelado mat… »