Triángulos "a la" Knowlton

Dice la Wikipedia: Kenneth Charles Knowlton (6 de junio de 1931 - 16 de junio de 2022) fue un pionero estadounidense de los gráficos por computadora, artista, mosaicista y retratista. En 1963, mientras trabajaba en Bell Labs , desarrolló el lenguaje de programación BEFLIX para crear películas producidas por computadora con imágenes de mapa de bits. En 1966, también en Bell Labs, él y Leon Harmon crearon la obra de arte por computadora Computer Nude (Studies in Perception I). Tal vez uno de sus cuadros más famosos es el de una mujer desnuda, hecho con los símbolos que se usaban para dibujar esquemáticos de electrónica (que se muestra al inicio de este artículo).

Ken Knowlton

Sin embargo, Knowlton dedicó buena parte de su vida a crear arte con la ayuda de la computadora. En https://www.knowltonmosaics.com/ pueden verse la mayoría de sus trabajos. Algunos de ellos me parecen fascinantes, por ejemplo el siguiente:

Básicamente Knowlton hace un filtro mosaico pero en lugar de usar cuadrados o rectángulos, lo hace con triángulos. Probablemente la parte más complicada sea el generar una cuadrícula que pueda pintar rectángulos horizontales y verticales y ya la parte más sencilla, calcular el color promedio del área de cada triángulo.

Me di pues a la tarea de hacer esto y finalmente generé un programa que hace lo que Knowlton diseñó. De hecho, parte de los créditos son de Gemini AI, que resolvió algunos problemas que me hubiese llevado mucho más tiempo solucionar sin su ayuda.

Este es el software corriendo:

y este es el resultado final:

Elena Frolova (original)

Elena Frolova (Procesada)

El efecto es muy parecido al que Knowlton creó. Si vemos la imagen más de cerca, encontraremos lo siguiente: 

Detalle del ojo izquierdo de Elena

Cabe decir que en algún momento quise entrevistar a Ken Knowlton. Conseguí su correo y le pedí una entrevista. Declinó. Me comentó que cuando tuviese algo que decir, me contactaría. Nunca lo hizo. Murió el 16 de junio de 2022. 

El software, para quien lo quiera, es totalmente gratuito. Escríbame a morsa@la-morsa.com y se lo envío. Sólo funciona en Windows.

Un curioso error (bug) de un componente en Delphi

Programar una computadora no es una labor trivial. Hoy en día se tienen un sinfín de herramientas y rutinas que simplifican la vida del programador, pero que funcionan como "cajas negras" en donde no sabemos a ciencia cierta qué está pasando dentro de ese código. Ya Brian Kernigham dijo (en una entrevista), que la programación ya se había vuelto fastidiosa. Uno carga su programa en Python e incluye N bibliotecas de terceros. Uno espera, decía Kernigham, que todo salga bien y que no haya errores. ¿Pero si algo falla? ¿A qué biblioteca particular le echamos la culpa?

Pero claramente hoy no podemos programar todo desde cero. No quiero imaginar pensar en escribir un sistema como Google Maps, por ejemplo, sin un número enorme de bibliotecas. Por ello, usar componentes, bibliotecas, rutinas de otros, es casi un "mal necesario", pues aunque no queramos creerlo, muchas rutinas que se escriben contienen errores sutiles, que muchas veces no salen a la luz hasta que ocurren situaciones muy específicas.

Por ejemplo, Adobe Photoshop, uno de los programas más robustos que conozco, tiene un listado de los problemas y bugs que pueden ocurrir. No es un drama y es parte del ciclo del software. D hecho, peor aún, hace unos 30 años Intel sacó un procesador que cometía un error en ciertas condiciones en su matemática de punto flotante. Un error que les debe haber sido muy costoso, pues todos esos procesadores simplemente ya no se podían usar.

Pues bien, en el software que estoy contínuamente mejorando, sobre un sistema para estudiar táctica, uso un componente que pinta en la pantalla un tablero de ajedrez y además, ya tiene programadas las reglas del juego, incluso la captura al paso. Usando la base de problemas del método del carpintero (que puede descargarse de este enlace), hallé que el ejercicio 157 (véase siguiente diagrama, más abajo), al realizar la jugada ganadora, 1.Tg8, mi sistema hace la jugada del negro, Rxg8 pero de pronto, antes de que pueda continuar, aparece una torre negra en f8. Me sorprendió porque no sabía qué había hecho el componente para de pronto, aparecer una torre negra de la nada.

Ejercicio 157 del Método del Pájaro Carpintero

Después de ejecutar la jugada 1.Tg8, el sistema responde con Rg7-g8 y entonces, ¡aparece la torre negra en f8!

El círculo rojo indica dónde aparece la torre. Sospeché que el componente veía eso como enroque corto y lo hacía entonces. En el código interno del componente el sistema dice: si había una pieza (presumiblemente el rey negro), en e8 y ahora aparece en g8, entonces, la torre negra debe ir a f8 y desaparecer lo que haya en h8. Pero curiosamente, el componente no verifica, antes de hacer estas jugadas, que en e8 y h8 haya piezas negras, De hecho, la jugada 1.Tg8 tiene originalmente la torre blanca en e8.

¿Cómo corregir esto? Había que meterse en el código fuente. Pero he aquí que decidí preguntarle a Gemini AI de Google y como respuesta me dijo cómo modificar el código fuente. Hice lo que me dijo y listo, bug solucionado.

Notable poder resolver estos problemas en minutos, aunque confieso que me llevó algunas horas depurar el código para ver qué pasaba.

 

Buscar combinaciones en ajedrez con la computadora

 Todo ajedrecista que quiera mejorar, debe hacer ejercicios de táctica. Estos ayudan a crear la visión cuando hay una posible combinación, lo cual es básicamente un reconocimiento de patrones. El ajedrez se puede estudiar precisamente porque se repiten las situaciones. En ocasiones es difícil hallar el o los motivos que hacen que una combinación sea posible, pero claramente existen configuraciones, patrones, que nos permiten descubrir las posibilidades combinativas en ciertos momentos de la partida.

 Hoy tenemos muchos libros de ejercicios de táctica. ¿Cómo es que fueron escritos? El primero que se me ocurre es el de Fred Reinfeld, “1001 combinaciones de mate”. Se hizo cuando no había computadoras y probablemente el autor recolectó, a través de los años (tampoco había Internet), cientos de posiciones. Cuando tuvo 1001 mates interesantes, los plasmó en un libro. Fue una labor de años, probablemente. Hoy, sin duda, este trabajo es mucho más fácil de hacer.

 Por ejemplo, tenemos un ejército de youtubers e influencers, que cada vez que ocurre una combinación brillante en algún torneo, la publicitan en sus respectivos canales de videos. Así, viendo los canales de algunos de estos entusiastas creadores de contenido de ajedrez, podríamos ir recolectando partidas de forma mucho más sencilla.

 Pues bien, pensando en esto, se me ocurrió discurrir sobre la posibilidad de escribir una aplicación (software), para que dado un archivo PGN (una colección de partidas), me dijera el sistema en qué momento se dio alguna combinación.

 Evidentemente el problema es definir lo que es una combinación para la computadora. Algunos criterios podrían ser:

•  ·         Secuencia forzada con ganancia material
• ·         Mate en N jugadas
• ·         Sacrificio seguido de ventaja clara
• ·         Evaluación que cambia drásticamente (ej. +0.5 → +5.0)
•  

Para ello podemos usar un motor de ajedrez como Stockfish, Houdini, etcétera. El único requisito sería usar el protocolo UCI para comunicarse con el programa de ajedrez para que nos ayudara en esta labor.

 El flujo sería algo como esto:

 Archivo PGN → Parser → Tablero posición por posición → Motor de ajedrez → Detección de combinación → Reporte

 Un detector de combinaciones debe entonces definir las reglas de esta manera:

•  Si la evaluación cambia más de X puntos → posible combinación
• Si hay sacrificio + mejora → combinación
• Si hay mate en N → combinación

 Por ejemplo, el reporte potencial que debería entrega el software es:

 Partida 12 (Kasparov vs Topalov)

• → Jugada 24: combinación detectada
• → Evaluación: +0.3 → +6.5

 Habría que ver, más adelante, si puede saberse qué tipo de combinación es la que ocurre, por ejemplo:

 → Tipo: sacrificio + ataque

 pero por lo pronto, nos bastaría saber si el cambio radical en la valoración del motor de ajedrez, es suficiente como para definir que existe una combinación.

 Yo estoy convencido que no es un criterio absoluto y que habrá un alto porcentaje de combinaciones detectadas únicamente usando este criterio. No obstante, podrá haber "falsos positivos", con los que habrá que lidiar.

 Por ende, me senté a escribir mi analizador de partidas de ajedrez. La conexión entre el engine de ajedrez y mi programa (en Delphi 7), fue quizás lo más complicado. Primero usé un componente de terceros, pero parece que no usa threads  (hilos e ejecución, que son una forma de ejecutar código en paralelo al flujo principal de tu programa), y entonces la interfaz gráfica se congela de manera aleatoria. Gemini me dio la solución (y hasta me ayudó con el fragmento de código), y entonces todo fluyó.

 La imagen 1 muestra mi software evaluando una partida mía, en donde hice una simpática combinación al buen amigo, el Dr. en Física, Efraín Chávez, que reconozco, siempre tuvo mala suerte conmigo cuando nos tocó jugar (y que con él lo hemos comentado en más de una ocasión). La partida está analizada aquí.

 

Imagen 1

Nótese la valoración que da Stockfish en LiChess, la cual se mantiene bastante parecida. Las diferencias son porque LiChess tiene computadoras y servidores más robustos y rápidos. Sin embargo, en mi máquina se mantiene la misma forma de la gráfica (Véase la segunda imagen).

 

Imagen 2

Puede verse que el error del negro ocurre en la jugada 16, en donde pasa de +0.2 a +4.8. El cambio es muy brusco, lo que sugiere fuertemente una combinación (que de hecho, existe).

 ¿Para qué puede servir este software? Fácil: se puede poner una colección de partidas en formato PGN y pedirle al programa que analice automáticamente cada una de estas partidas e indique si se sospecha de una combinación, al haber un cambio brusco en la valoración.

 Ahora estoy trabajando sobre la interfaz con el archivo PGN. Sin embargo, los avances hasta ahora me tienen contento. Cabe decir que hay un sitio, https://chessgrammar.com/, el cual hace algo similar, pero es de paga (aunque da oportunidad de probarlo de forma gratuita). Hace algunas otras cosas, como reconocer algunos patrones tácticos. Se ve bien pero no sé qué tan efectivo sea. En cualquier casoo, cmo ejercicio de programación me parece una buena idea.

Seguiremos informando.

¿El Filtro “Moiré” revela problemas de software o hardware?

Las computadoras modernas manejan un mundo de gráficas. Hoy en día cualquier computadora tiene una tarjeta gráfica que puede presentar casi unos 17 millones de colores. Y de hecho, no tiene sentido hacer hardware más sofisticado para presentar más combinaciones de colores porque simplemente el ojo humano ya no los reconoce. 

Otro punto importante es la resolución de dichas tarjetas gráficas. La mayoría puede desplegar desde 320 x 200 puntos hasta unos 2000 x 2000 puntos e incluso algunas tarjetas pueden manejar resoluciones de 4K. Esto hace que las imágenes y fotografías que se desplieguen en el monitor se vean muy nítidos, con luminosos colores y cada vez más cercanas a la imagen original. 

Por otra parte, los filtros gráficos son una vertiente artística del procesamiento digital de imágenes y se han escrito un buen número de rutinas para convertir las imágenes en toda clase de representaciones gráficas. Por ejemplo, hay filtros elementales como aquellos que cambian las imágenes en color a tonos de gris, o bien, que manipulan contraste y brillo fácilmente. Sin embargo, hay filtros que requieren mucho más trabajo. Uno de ellos lo descubrí en Instagram y pensé que no podía ser muy difícil realizarlo. El efecto toma una fotografía (puede ser en color o blanco y negro), y tomar un punto central de dicha imagen. Una vez en esa posición se empiezan a pintar círculos concéntricos hasta llenar toda la imagen. La siguiente fotografía muestra la idea:

 Imagen 1

Nótese que en esta imagen los círculos concéntricos se ven perfectos. El código que escribí en Delphi me dio (usando otra imagen porque no tengo la original), lo siguiente (ver Imagen 2):

Imagen 2

Puede verse que los círculos concéntricos no son perfectos (como en la imagen 1). Véase una parte de la Imagen 2 amplificada (Imagen 3):

Imagen 3

El algoritmo para crear este efecto es relativamente simple, pero las rutinas que pintan círculos en la pantalla parecen no hacer correctamente la tarea. Mi primera sospecha fue que la resolución de las tarjetas gráficas, para el consumidor final de electrónica, tienen muy mala resolución. Sin embargo, hay muchas imágenes en Internet con este efecto y se ven perfectamente bien. Así que mi sospecha recayó en algo que se llama antialias o en español, “suavizado”, lo cual funciona añadiendo píxeles grises a lo largo del borde de una línea o curva para integrarse con el color de fondo. Este proceso de fusión reduce la visibilidad de los bordes irregulares, haciéndolos más suaves y menos visibles. Un ejemplo exagerado de esto puede verse aquí (Imagen 4):

Imagen 4

La cuestión es ahora averiguar la razón del problema que se presenta al dibujar círculos que –al menos en teoría– deberían ser perfectos, pero hay alguna razón que impide que se p0jnten correctamente. Seguiremos investigando. 

Dawkins y los cambios acumulativos en la evolución natural

Richard Dawkins es un biólogo evolucionista muy popular y famoso. Es autor de varios libros, entre ellos "El gen egoísta" (1976), en donde popularizó la idea de la evolución basada en los genes.  Dawkins usa la definición de gen de George C. Williams como "aquello que se separa y recombina con frecuencia apreciable". Y a partir de ahí intenta mostrar que gracias a esta recombinación de los genes, se evoluciona y se tienen individuos más aptos. 

Podríamos decir que en su siguiente libro, "El relojero ciego" (1986), es una continuación de El gen egoísta, en donde Dawkins responde a una serie de críticas a sus teorías evolutivas a partir de la genética. Comienza discutiendo las ideas del teólogo William Paley (de 1802). De acuerdo a Paley, la vida, debido a su complejidad y perfección, es evidencia para creer en Dios. Es un mecanismo como un reloj, y los relojes son creados por relojeros. De hecho, Paley pone como ejemplo la complejidad biológica del ojo humano. Dawkins usa ese símil para argumentar que el supuesto relojero de la vida no planifica a largo plazo (porque es ciego). Argumenta que la vida, aunque compleja, no es perfecta. El propio ojo humano contiene una falta de eficiencia debida a la orientación de las células fotosensibles. El punto fundamental es cuando Dawkins indica: "La consecución de la complejidad se puede lograr mediante la acumulación progresiva de pequeñas modificaciones".

Pero... ¿es así? Dawkins no se conforma con sus argumentaciones, sino que pasa al terreno de la práctica para demostrar esta acumulación progresiva de pequeñas modificaciones que, en términos evolutivos, puede llevar mucho, pero mucho tiempo. Sin embargo, Dawkins plantea el conocido problema de los monos que ciegamente escriben en máquinas de escribir al azar, hasta que se produce -eventualmente- las obras de Shakespeare. Dice el famoso biólogo: "No sé quién fue el primero en argumentar que, dado un espacio de tiempo lo suficientemente largo, un mono que pulsara las teclas de una máquina de escribir de manera aleatoria llegaría a escribir todas las obras de Shakespeare. Obviamente, la parte crucial de esta hipótesis es 'dado un espacio de tiempo lo suficientemente largo'". Y agrega "De todas maneras, limitemos un poco la tarea del mono: supongamos que no tiene que escribir las obras completas de Shakespeare, sino simplemente la frase methinks it is like a weasel ('yo creo que se parece a una comadreja'). Pongámosle las cosas aún más fáciles: el mono dispondrá de un teclado más sencillo de lo normal, con sólo las 26 teclas correspondientes al alfabeto inglés (todas mayúsculas) y la barra espaciadora. ¿Cuánto tiempo le llevaría al mono escribir esta frase?" 

El ejemplo de Dawkins está diseñado para hacernos considerar la producción de una secuencia de 28 caracteres, asumiendo que cada uno de ellos es seleccionado aleatoriamente. El número de posibles secuencias, dado el alfabeto disponible, es de 27^28, o aproximadamente 10^40. La probabilidad de que el mono produzca una secuencia determinada es extremadamente pobre. Cualquier secuencia puede ser seleccionada como el objetivo, y todas ellas tienen la misma probabilidad de ser producidas que la secuencia objetivo de Dawkins, es decir, 'METHINKS IT IS LIKE A WEASEL'.

Dawkins entonces escribió un programa de computadora tratando de simular las condiciones impuestas: un simio informático que escribe azarosamente en un teclado limitado.  Este mono produce líneas de 28 caracteres al azar. Si pensamos así, probablemente le llevaría varias veces la vida del universo para llegar a la frase buscada.  Pero Dawkins ilustra así una concepción equivocada (pero muy común) de la evolución: que las secuencias de ADN y otros compuestos orgánicos como las proteínas son el resultado de una combinación aleatoria de átomos. Dice Dawkins: "Si la selección natural funcionara de esta manera, la probabilidad de que se formara una secuencia de aminoácidos concreta sería extremadamente reducida". La selección natural, agrega Dawkins, no funciona así, sino que procede en pequeños cambios cumulativos. Seguidamente, demuestra que el proceso de selección cumulativa conlleva una reducción muy considerable en el número de pasos necesarios para producir cualquier secuencia posible.

Y continúa el biólogo evolucionista: "Introduzcamos ahora una sutil diferencia en nuestro programa. El primer paso, al igual que antes, consiste en producir una secuencia aleatoria de 28 caracteres. Pero los pasos subsiguientes no consisten en producir más secuencias aleatorias. Más bien, cada paso produce varias copias de la secuencia anterior, pero con la posibilidad de que alguna copia no sea perfecta. A los errores de copia los llamaremos mutaciones. El programa examina las copias mutantes y selecciona la que se aproxime más a la secuencia objetivo 'METHINKS IT IS LIKE A WEASEL', por pequeña que sea la mejora".

Esto es -de hecho- el algoritmo genético de John Holland, el cual es en sí es un procedimiento para maximizar funciones. No sé si Dawkins lo sabía, pero su programa encuentra en unas 43 generaciones -siguiendo el procedimiento descrito- la frase buscada. Así que decidí escribir mi versión de la idea de Dawkins (apoyándome en la versión en Pascal descrita en https://rosettacode.org/wiki/Evolutionary_algorithm#Pascal), y lo puse a prueba. Es un programa escrito en Delphi 7 y encuentra la frase buscada en 798 generaciones, aunque ejecutando el programa en diferentes ocasiones, estos números cambian. 

Esta es una corrida del software:

BPMQDQWS ZRJYKYIVDGVTTULKDHZ

MPMHDQKS ZTJYS LIDGVT WEKDHL

MPTHDQKS ZTJIS LIKEVT WEKDHL

MPTHDQKS ITJIS LIKEVT WEADEL

METHDQKS ITJIS LIKEVT WEASEL

METHINKS ITJIS LIKE T WEASEL

METHINKS ITJIS LIKE T WEASEL

METHINKS IT IS LIKE T WEASEL

METHINKS IT IS LIKE A WEASEL

Dawkins concluye: "El tiempo necesario para completar la tarea es irrelevante. Si de verdad le interesa, le diré que la primera vez tardó la media hora que me lleva a mí almorzar. Algunos aficionados a la informática podrían pensar que esto es un tiempo excesivamente largo, pero eso es porque la primera versión del programa estaba escrita en BASIC, un lenguaje con una sofisticación mínima. Cuando lo traduje a PASCAL, el programa tardó once segundos en producir la secuencia objetivo. También es cierto que los ordenadores son considerablemente más rápidos que los monos, pero, de nuevo, esto no es relevante. Lo que importa es la diferencia relativa entre el tiempo que lleva producir METHINKS IT IS LIKE A WEASEL por selección cumulativa, y el tiempo que llevaría producir la misma secuencia, a la misma velocidad de computación, por selección no-cumulativa -aproximadamente un sixtillón de años. Esto equivale a un cuatrillón de veces la edad actual del Universo".

Puede asombrar a más de uno todo esto, pero para quien sigue contemplando la vieja idea de que los cambios en la evolución son azarosos, Dawkins nos muestra que no necesariamente es así.

A quien le interese el software, escríbame  a morsa@la-morsa.com y se lo mando a vuelta de correo electrónico.

¿Funciona mi conexión de Internet?

La tecnología nos ha traído Internet y con los años hemos visto aumentar significativamente el ancho de banda, es decir, la velocidad de acceso a la información. Quienes tengan la suficiente edad sabrán que hubo tiempos en que los módems trabajaba a 300 baudios, La velocidad en baudios es el número de veces por segundo que una señal cambia de estado; el cual puede ser un nivel de voltaje, una frecuencia o un ángulo de fase de frecuencia. Si la señal cambia una vez para cada bit de datos, entonces un bit por segundo equivale a un baudio.

Por años tuvimos velocidades de 1, 2 y hasta 10 megabits por segundo, lo cual evidentemente significa que –mientras más alta la velocidad, más datos se reciben por segundo– pero también, mientras más aumenta la velocidad, más pagamos por el Internet. Hoy hablamos de 100, 200, 500 y hasta mil megabits por segundo, lo cual es cada vez más necesario pues la cantidad de información que recibimos y mandamos se ha incrementado exponencialmente.

Desde luego que estos avances han significado cambiar las líneas de cobre por la fibra óptica, pues al final del día Internet funciona gracias al acceso telefónico que se ha ido colocando con los años en todos los países. Los primeros módems los podíamos comprar en las tiendas de electrónica y había que marcar a un teléfono que recibía la conexión del módem, se hacía el “handshake” (es decir, los equipos se “saludaban” y se “daban la mano”) y entonces se iniciaba la comunicación entre equipos. Hoy son los proveedores de Internet quienes nos dan los módems en calidad de préstamo para poder acceder al servicio a velocidades mucho más altas que hace unos años.

Hay varios proveedores de Internet, los cuales prometen muchas veces “las perlas de la virgen”. Es probable que la mayoría de los usuarios hayan sufrido problemas técnicos. En muchas ocasiones simplemente no hay conexión y pagamos por un servicio que nos deberían dar y que es de 24/7. Las empresas de tecnología, lo sabemos bien, no son inmunes a los errores y a veces las cosas salen mal. El problema empieza cuando el usuario reclama y no hay respuesta o bien, quien nos atiende no nos cree que no tenemos conexión o que llevamos horas sin conexión. Todo termina en discusiones donde es la palabra del usuario contra la de quien nos atiende.

Pensando en ello, escribí un pequeño programa que revisa, cada 20 segundos, si hay conexión a Internet. Estrictamente un “ping” es el método para medir el tiempo más corto necesario para enviar y recibir una pequeńa cantidad de datos a través de la conexión de Internet. Normalmente el procedimiento pide hacer un ping a un sitio web que sabemos está activo (por ejemplo Google), y si éste contesta, entonces quiere decir que hay conexión en la red. Cuando falla nuestro servicio, el ping falla y entonces el programa escrito inicia un cronómetro, contando los segundos que no tenemos Internet. El software puede mantenerse funcionando todo el tiempo mientras estamos trabajando en cualquier otro programa. Finalmente, podemos grabar los resultados que presenta el software de manera que tengamos un reporte por escrito del tiempo que no tuvimos conexión a la red de redes.

A quien le interese este software escríbame a morsa@la-morsa.com y a vuelta de correo recibirá un enlace para que descargue el programa de instalación y pueda usarlo. El software solamente corre en el sistema operativo Windows.

Bosquejo para crear software que genere y resuelva crucigramas

Uno de los temas que tengo en el tintero, desde hace años, es cómo se crean los crucigramas que vemos publicados en los periódicos. Y eso me lleva siempre a preguntarme: ¿Usan algún software específico para eso? ¿Es posible escribir un software que genere crucigramas "profesionales", es decir, crucigramas que contienen ciertas características (de las que hablaré más adelante)? Y más aún, es posible escribir software que -dado un diccionario de palabras (quizás muy grande), pueda resolverlos automáticamente.

Si lo pensamos, muchos juegos se resuelven ya hoy en día a través de software, por ejemplo, los sudokus, el cubo de Rubik, etc. La idea de software que genere y resuelva crucigramas cae probablemente en la "programación lúdica" y sin embargo, es un interesante reto a resolver. Para ello, primero definamos lo que quiero decir con un crucigrama "profesional". Básicamente es aquel que en la mayoría de los casos es una malla cuadrada de letras, en donde los límites entre las palabras son cuadros negros que forman una imagen geométrica, muchas veces incluso simétrica. Por ejemplo, el siguiente crucigrama no es muy profesional. El dibujo de los cuadros negros está más puesto por las necesidades de cómo están puestas las palabras que por el hacer un dibujo simétrico.

El siguiente crucigrama, es uno profesional. Obsérvese que el dibujo que se genera es simétrico. Esto es lo común en los crucigramas que aparecen en los periódicos y otras publicaciones.

Podemos pues definir el problema en dos partes: i. generación de un crucigrama y ii. resolución del mismo. Analicemos brevemente ambos temas:

i. Generación de un crucigrama

Crear crucigramas requiere de una lista de palabras y de una cuadrícula, que no necesariamente debe ser cuadrada, en donde aparecen las palabras elegidas. Desde luego que esas palabras deben poderse definir de acuerdo al diccionario de la Real Academia de la Lengua para así crear el acertijo completo. No es fácil, al menos en esta primera incursión, saber si primero debemos dibujar los cuadros negros, los límites de las palabras o bien, empezar a poner palabras y después poner el correspondiente dibujo de cuadros negros. En primera instancia pareciera que es necesario primero definir la imagen de cuadros negros y entonces empezar a acomodar las palabras. Hacerlo de manera inversa parece más difícil en el momento de querer dibujar una figura simétrica.

Desde luego, podemos en un principio obviar el problema de la figura de cuadros negros simétrica, pero claramente es importante en el momento de escribir un software que bien podría usarse en publicaciones comerciales. Así, dada una colección de palabras, tenemos que tener una manera de revisar de forma automática su definición, para poder incorporar después esto en el acertijo final. Una idea sería tener un diccionario de la Real Academia de la Lengua Española en formato electrónico para así hallar por software las definiciones que necesitamos. Afortunadamente hay más de una versión de este diccionario en PDF.

Una vez teniendo esto, probablemente lo que haya que hacer es categorizar las palabras que se quieren poner en el crucigrama en el número de letras, de una letra, dos, tres, hasta N letras. Esto parece ser una buena idea porque también podemos hacer un dibujo de cuadros negros y hacerlo de manera tal que haya espacio para palabras de una letra, dos letras, tres letras, etc.

Y una vez que tenemos todo esto, empezar por asignar a alguna parte de las cuadrícula una palabra... y entonces ver si podemos poner alguna otra que sea en el sentido opuesto, es decir, si pusimos una palabra en vertical, la siguiente debería ser quizás horizontal. No podemos poner todas las palabras horizontales o verticales porque entonces tendríamos zonas con palabras sin sentido. Podemos seguir este proceso hasta que ocurra un camino cerrado y entonces, al no tener ninguna palabra para poner tenemos dos opciones: a. buscar una palabra que cumpla con ciertos requisitos y entonces ponerla o bien, b. desechar la última palabra puesta y buscar otra, en un proceso de backtracking que bien podría irse casi hasta la primera palabra puesta si es necesario. Si hacemos esto último, el problema es que no podríamos garantizar que el crucigrama se generara. Es decir, tendríamos un programa indecidible. Sin embargo, este problema, el núcleo de la creación de un crucigrama, lo hace un problema fascinante.

ii. Resolución de un crucigrama

He visto desde hace mucho programas que buscan resolver crucigramas automáticamente. De hecho, en un libro en Prolog vi un pequeño programita que resuelve un crucigrama trivial, el cual lo hace a través de backtrack (ver aquí - https://la-morsa.blogspot.com/2009/07/creador-de-crucigramas.html). La idea es simple: se busca una primera palabra de la lista que contenga el número de letras que llenen el espacio de letras que estamos buscando. La ponemos y ahora buscamos la segunda palabra, que intersecte con la primera en alguna letra y qué, además, tenga la cantidad de letras necesarias para llenar el espacio. Si la encontramos la ponemos en el crucigrama y seguimos buscando. Pero... ¿qué pasa si hay un error y no tenemos ningunas palabra que resuelva el siguiente espacio de letras? Pues hacemos backtrack, es decir, nos regresamos al paso anterior, buscamos otra palabra que cumpla con las condiciones de la última palabra requerida (que sea diferente a la que ya pusimos). Si la hallamos, la ponemos y seguimos. Si no encontramos ninguna palabra, entonces hacemos backtrack sobre la palabra anterior a esta, y así sucesivamente. Eventualmente -si el crucigrama se puede resolver- el sistema lo podrá solucionar. Sin embargo, de nuevo caemos en el terreno de lo indecidible.

Otros detalles

Cabe decir que los crucigramas profesionales ya usan algunas palabras que ocurren frecuentemente cuando se generan este tipo de acertijos. Por ejemplo, muchas veces aparece "Dios del Sol egipcio", lo cual es "Ra". Hay así algunas palabras comodines que nos ayudan a la creación de un crucigrama profesional. En cambio, un crucigrama no profesional, de aficionado, cuando tiene que llenar un espacio y le quedaron las letras AVZ, por ejemplo, lo resuelve definiendo esa palabra como "Arturo Vázquez Zetina (iniciales)". Esto es muy poco profesional y me parece que este recurso no se usa en los crucigramas comerciales.

El problema de generación y resolución de crucigramas, creo yo, da para una tesis de licenciatura en la carrera de ciencias de la computación y/o matemáticas. Si alguien quiere hacer tesis con este tema, escríbame a morsa@la-morsa.com y lo platicamos.

Convierta sus imágenes como si estuviesen pintadas con lápiz

Los filtros gráficos artísticos suelen convertir las imágenes en fotos hechas como si se hubiesen pintado como óleo, o bien, como si se usara carboncillo. He aquí el bosquejo de un filtro que busca simular una imagen como pintada con lápiz.

Los filtros sobre imágenes son básicamente transformaciones de los pixeles. Por ejemplo, se puede pasar de una imagen en color a tonos de grises mediante la conversión del color de cada pixel (con componentes rojo, verde y azul (RGB)), mediante esta fórmula:

Gris = R + G + B div 3

y colocando el valor Gris en lo que viene a ser su respectivo rojo, verde y azul.

Muchos filtros usan una matriz de valores para realizar este tipo de transformaciones. Por ejemplo, la "convolución"  es simplemente una matriz de número impar de columnas y renglones, en donde se colocan valores, los cuales se multiplican a los correspondientes pixeles, y esto permite filtros que permiten encontrar bordes, o bien, hace una imagen más borrosa, o más precisa, o bien, quitándole "artefactos", que no son otra cosa que pixeles indeseables en la imagen que se está procesando.

Hay un filtro de convolución para encontrar bordes. Sin embargo, la siguiente idea puede hacer lo mismo con menos procesamiento y de manera muy simple. Veamos: La idea es usar un filtro de esta naturaleza para hacer que se parezca a un dibujo hecho a lápiz. El algoritmo es éste:

• Obténgase el color del pixel que queremos procesar. 
• Obténgase el coor del pixel exactamente abajo de éste.
• Calcúlese el promedio de los componentes R, G y B para cada pixel y tómese el valor absoluto de la diferencia de los promedios.
• Si la diferencia entre los promedios está por debajo de un valor UMBRAL, coloque el pixel actual en blanco, sino en negro.

Pero entendamos cómo funciona el filtro. En esencia lo que se hace es sacar la diferencia entre dos pixeles y ver si esta diferencia es mayor que un valor que llamamos "umbral". Esto es equivalente a decir que si la diferencia es mayor, estamos ante un borde en la imagen, es decir, la diferencia de los dos valores resulta ser demasiado grande. En términos conceptuales el algoritmo es muy simple.

Teniendo esto definido, escribir el código correspondiente es muy fácil. He aquí el fragmento en Delphi:

Aplicando el código a una imagen (pasada a tonos de grises para hacer el trabajo más simple), se encontró el siguiente resultado:

Desde luego que este filtro dista ser uno que parezca como si la imagen se hubiese hecho a lápiz. Hay artículos técnicos muy interesantes al respecto, como éste, que usa una técnica muy elaborada.

Quien le interese jugar con mi software, escríbame a morsa@la-morsa.com y se lo mando a su correo de forma gratuita.

GigaChess: una base de datos de posiciones de ajedrez

Llevo tres años trabajando en el doctorado y parece ser que ya las cosas se están aclarando. Tengo un lenguaje de descripción de patrones y ahora el plan -entre otros- es hallar los patrones comunes en la base de partidas que hoy en día tiene más de 7 millones de estas.

Una idea que llevaba hace tiempo trabajando era la de buscar patrones en una base de datos de posiciones, lo cual debe ser mucho más rápido que el tener que buscar el patrón jugando cada partida. Además, si cambio de patrón, tendría que volver a "jugar" partida tras partida para ver si el patrón que busco existe.

Por otra parte, pienso que si guardo cada partida como "fotografías" de cada posición que se dio, puedo hacer las búsquedas más rápidamente. La primera pregunta es cuánto espacio necesito. Hagamos uns imple cálculo: 7 millones de partidas por 80 posiciones (asumiendo que en promedio una partida tiene 40 jugadas, 80 movimientos de blancas y negras). Esto da: 560,000,000 posiciones en total. Si necesito un registro de al menos 64 casillas para guardar una posición (en formato Forsyth), esto nos dará 35,840,000,000 bytes, es decir, unos 35 gigabytes de almacenamiento. Hay que guardar, desde luego, el encabezado de cada partida y hacer el sistema que buisque los patrones. Vamos, hay trabajo por hacer.

35 Gigabytes no parece mucho espacio hoy en día, en donde tenemos discos con 1 o 2 terabytes de almacenamiento.

Así pues, el primer problema es generar las posiciones y ya escribí hace tiempo un programa que hace esta tarea. Cada partida, en la máquina que tengo, se procesa en promedio, en 5 segundos (veces menos).  Eso da, para 7 millones de partidas un total de 35,000,000 segundos, lo cual en días es equivalente a 405 días, como un año y tres meses...

Denasiado tiempo. Así que he reeducido a un millón de partidas, quizás menos. Por otra parte, AMD me donó una computadora mucho más rápida que la que uso normalmente y espero que esto baje el tiempo de procesamiento aún más. Con un millón de partidas, más o menos tardaré: 57 días, unos 2 meses...

Pronto seguiré dando avances sobre esta idea, la cual -después de mucho pensarlo- me parece más útil para la cuestión de programación de computadoras que para el ajedrecista que usa programas para apoyar su estudio.

Un nuevo reto lúdico: los números de Munchhausen

Las matemáticas recreativas siempre presentan posibles retos para la programación. En esta ocasión hablaremos de los curiosos números de Munchhausen y plantearemos el reto a solucionar.

Dice la Wikipedia: "un número de Munchhausen (o Münchhausen) es un número natural n el cual la suma de sus dígitos (en base 10), elevados a la misma potencia de ellos mismos es el mismo número es decir n. Por ejemplo:

3435 = 3^3 + 4^4 + 3^3 + 5^5 = 27 + 256 + 27 + 3125 = 3435.

El término fue una invención del ingeniero y matemático holandés, Daan van Berkel, que en el 2009 estudió este tipo de números. La idea de llamarlos así a estos números se debe a que cada dígito está "elevado" por sí mismo y esto evoca la historia de Barón Munchhausen que se elevó a sí mismo hacia arriba jalando su propia coleta. Como todos sabemos, el Barón de Munchhausen era un mentiroso crónico e inventaba las más increíbles historias, recopiladas en un libro incluso.

La idea de estos números puede dar a un nuevo reto lúdico. Se trata de averiguar cuántos números hay con esta propiedad. El 1, por ejemplo, cumple pues es 1^1 = 1. El segundo número es el 3435 y parece que no hay más. Consideramos normalmente que 0^0 = 1, pero si tomamos la definición "no estándar" de que 0^0 = 0, entonces el número 438,579,088 es también de Munchhausen.

El reto lúdico es pues escribir un programa que dado un intervalo de números naturales, empezando en 1 y terminando en el número que se deseé, el programa encuentre en el menor tiempo posible cuáles son los números de Munchhausen. Aunque ya sabemos la respuesta, el ganador del reto será quien encuentre en el menor tiempo posible el resultado correcto, considerando un intervalo de al menos 10 millones de números: del 1 al 10 millones. Además, el programa deberá usar la definición estándar de 0^0 = 1 y 0^0 = 0, esto, desde luego, por separado.

Cabe señalar que yo ya escribí mi propia versión del reto. En este caso, le puse una opción que me dice qué número está procesando, pero para efectos de mediciones, le puedo quitar eso porque el despliegue de esta información hace mucho más lenta la ejecución del software.

El reto tendrá como premio una taza de la Morsa. Si el ganador es de provincia, se le mandará un USB de 8 GB al menos, porque mandar una taza por mensajería es ridículamente costoso. Cabe señalar que este concurso busca simplemente alentar el trabajo de la programación y mostrar que puede ser lúdica. Es un concurso de buena fe. Si hay, por ejemplo, dos o más respuestas satisfactorias, ganará quien la haya mandado primero. El ganador cede su código fuente a la comunidad. Es decir, se promueve el código abierto.

Las respuestas al reto deben mandarlas a morsa@la-morsa.com. A quien le interese ver mi programa corriendo, envíeme un mensaje a mi correo y le mandaré el enlace para que lo descarguen y vean mis resultados. ¡Suerte!

Para revivir a Delphi

Borland fue una empresa de software que en su momento sus políticas revolucionaron el cómputo y la programación. Su compilador original, Turbo Pascal, fue un éxito instantáneo al venderlo en 50 dólares. El sistema venía en un diskette y traía compilador y editor (¡en sólo 12K bytes!) y un buen número de ejemplos. Fue el estándar del lenguaje Pascal por muchos años. Microsoft incluso decidió dejar de vender su propio compilador de Pascal porque simplemente no podían competir.

Con el tiempo y el éxito de este compilador, empezaron a salir una serie de bibliotecas de desarrollo: Turbo Editor ToolBox, Graphix ToolBox, Turbo Lightning, entre otros, Turbo Pascal se convirtió en una estupenda herramienta. Borland entonces sacó su versión 4, 5, 5.5, 6 y 7, la cual ya era mucho más pulida que la original, pero conservaba la filosofía de compilar a toda velocidad, haciendo que el programar fuese mucho más fácil y atractivo para los desarrolladores.

Entonces Borland inició la aventura de crear los "turbo lenguajes", y sacó Turbo C, Turbo Basic e incluso Turbo Prolog. Hay que señalar que al menos los dos últimos de esos lenguajes fue creación de Borland, sino que se encargaron a diferentes empresas. Y con ello probablemente la empresa creció y se hizo de muchos más adeptos. Borland incluso sacó a la venta el Turbo Prolog Toolbox, que contenía muchísimas herramientas para los que programábamos en turbo Prolog, una versión no muy estándar de Prolog, pero sí mucho más atractiva incluso para ciertas aplicaciones del mundo real.

Pero algo pasó. Tal vez la moda terminó. Quizás muchos programadores, particularmente de Turbo Basic y Turbo Prolog, migraron -los primeros- a Visual Basic, Los números deben haber dado con la decisión de regresar a sus fabricantes originales Turbo Prolog y Turbo Basic. Por ejemplo, El compilador de Turbo Basic fue creado por Bob Zale, a quien Borland compró los derechos. Cuando Borland decidió abandonar la línea de Turbo BASIC, Zale compró nuevamente los derechos para continuarlo mejorando y comercializarlo bajo el nombre de PowerBASIC a partir de 1989.

De Turbo Prolog podemos decir que PDC Prolog / Visual Prolog fue quien creó este sistema, pero la licencia del programa fue vendida por Borland a la división de la empresa que se había encargado de su desarrollo, la cual había creado en 1984 la compañía PDC (Prolog Development Center) y se hizo cargo del producto; pasó a comercializarlo con el nombre de PDC Prolog (para primero para los sistemas operativos MS-DOS y OS/2, y posteriormente para Windows 3.1) y en 1996 renombró el software a Visual Prolog, actualizando y manteniendo el producto en el mercado hasta la actualidad. A partir de la versión 6.0 (lanzada en 2002) el lenguaje era completamente orientado a objetos.

Sin embargo, Borland parecía haberse establecido como una empresa de software exitosa. En algún momento compró DBase y de pronto, por alguna razón, separaron sus sistemas de bases de datos, Dbase e Interbase, con los de desarrollo, Turbo C y Turbo Pascal. Para ese entonces (1995), Borland ya estaba anunciando Delphi 1.0, que fue la primera herramienta RAD que pensaba competir no contra Visual Basic, que se consideraba en muchos sentidos solamente para hacer prototipos, sino contra Power Builder, que de acuerdo al CEO de Borland, Phillipe Kahn, era a quien había que desbancar.

Delphi se fue desarrollando a toda velocidad y la acogida de los programadores fue estupenda. En los siguientes años los programadores tuvieron un número enorme de bibliotecas, rutinas, documentación, etcétera, tanto en las páginas web como por parte de Borland. La empresa entonces sacó, año con año, nuevas versiones del compilador de Delphi y de C++ Builder y todo parecía ir sobre ruedas.

Pero de nuevo, algo pasó y de pronto Borland se vendió. He aquí un resumen de estos eventos:

• En 1991, Borland adquirió la compañía Ashton-Tate, de la que siguió comercializando sus productos estrella, dBase e Interbase.
• Hacia 1993-94 hubo acuerdos con WordPerfect de cara a la cooperación en ofimática, comercializándose conjuntamente sus productos.
• Tras la compra de Visigenic (empresa especializada en CORBA y creadora de VisiBroker) en 1997, cambió su nombre a Inprise.
• En 1999 Microsoft hace una inversión en la compañía, 2 meses después de haber ocasionado la salida de los principales directivos de Inprise.
• En 2000 hubo un intento fallido de fusión con Corel.
• En 2001, Inprise retomó su afamado nombre, denominándose desde entonces Borland Software Corporation.
• El 14 de noviembre de 2006 el departamento de IDEs y compiladores (Borland Developer Tools Group) se separó de Borland formando una nueva filial (cuyo único accionista era Borland), llamada CodeGear. La casa matriz, Borland Software Corporation, se centrará en herramientas de análisis, diseño y "gestión del ciclo de vida de la aplicación" (Application Lifecycle Management, ALM).
• En mayo de 2008 Borland Software Corporation llegó a un acuerdo para la venta de CodeGear a Embarcadero Technologies por 23 millones de dólares.
• En mayo de 2009, el desarrollador de software Micro Focus compra Borland Software Corporation por 75 millones de dólares.

Hoy Embarcadero es quien comercializa los productos de lo que fuera Borland. y los programadores siguen trabajando intensamente sobre sus compiladores, haciendo que estos puedan compilar para Android, iOS y Mac, inclusive. pero esto conlleva un gran costo y las herramientas de Embarcadero son muy costosas para la mayoría de los programadores y más si vivimos en países donde las devaluaciones están siempre al acecho. Pero incluso, para los estadounidenses, Embarcadero no vende software barato y por ello quizás, además de que hay muchos sistemas con versiones gratuitas (como Visual Studio para la comunidad), Delphi no C++ Builder han podido llegar a ser lo que fueron en su mejor tiempo. Y es una pena, porque son herramientas estupendas. De hecho, Embarcadero ahora está pensando en versiones de sus productos para Linux por lo que, podemos decir, siguen trabajando fuertemente y con la pasión de siempre.

¿Cómo poder recuperar el lustre del pasado? ¿Cómo hacer que los programadores puedan regresar a las nuevas versiones de Delphi y C++ Builder? No es sencillo, pro probablemente una buena alternativa es bajar los precios y hacer sus productos muchos más accesibles. La pregunta de ¿qué es más fácil, vender mil de a peso o 1 de a mil? resuelve esto. Probablemente sea difícil vender un producto de a 1000, pero vender mil de a peso quizás no sea tan sencillo. Tal vez puedan venderse unos 800 u 850. ¿No sería mejor política?

Como en todo, el precio es fundamental en la decisión de lo que decidimos adquirir. Si Embarcadero fuese menos costoso para quienes usan herramientas de desarrollo, las comunidades de programadores crecerán (como lo hicieron en el pasado) y por ende, todo mejorará para esta herramientas. En el fondo, el problema quizás es hacer gráficas en donde se vea cuánta gente compra herramientas de desarrollo, a qué precio, y en dónde se maximizan las ganancias con respecto a la cantidad de usuarios y no al total de lo vendido.

Y si hago toda esta reflexión es porque me parece que Delphi y C++ Builder merecerían regresar al gusto de los programadores. Las herramientas han madurado y ahora hacen muchas cosas que antes era complicado. Pero los mejores sistemas de programación no sólo depende de los compiladores y del desarrollo de los creadores de los mismos, sino del volumen de clientes que pueden tener. Ahí lo dejo a las reflexión mientras me voy silenciosamente.

AlphaZero es el nuevo súper gran maestro, ¿es eso muy grave?

Hace un par de días se dio la noticia de que AlphaZero y su algoritmo de aprendizaje reforzado, había sido aplicado al juego del ajedrez y en sólo cuatro horas, el sistema había aprendido a a jugar un ajedrez de súper gran maestro a partir del único conocimiento de cómo se movían las piezas. Los investigadores de DeepMind, que es una empresa de Google, pusieron a jugar a su invento contra uno de los mejores programas de ajedrez, StockFish, el cual es además de código abierto. Jugaron 100 partidas y AlphaZero venció 28-0 con 72 empates. Es decir, la máquina de Google no perdió una sola partida. Verdaderamente asombroso.

Y esto, por supuesto, como seres humanos, nos hace pensar si este nuevo algoritmo de redes neuronales es capaz de sintetizar en 4 horas 500 años de lo que sabemos de ajedrez y sin siquiera alimentárselo.  Si pensamos en los esfuerzos que se han hecho desde los años sesentas del siglo pasado en el campo de ajedrez por computadora, podemos observar un desarrollo sistemático y muy lento para llegar a tener motores de ajedrez como Komodo, Houdini o StockFish. Y lo que hizo AlphaZero parece ser el parte aguas el cual puede modificar de por vida la manera en como vemos el ajedrez.

Pero yo creo que el avance científico no tiene siquiera que estar peleado con el propio ajedrez. Ahora dispondremos de una herramienta mucho más poderosa que la anterior. Cabe por ejemplo señalar, que ya los programas como Houdini o Komodo, le ganan al 99.95% de los jugadores en todo el mundo y que desde el año 2000 aproximadamente, debido a los avances de cómputo, ya ni siquiera se hacen esos espectaculares encuentro de grandes maestros contra las computadoras. La razón es simple: ya nos ganó la técnica. Ya no podemos competir a la frialdad de los cálculos y valoraciones de árboles de variantes gigantescos. Vamos, el juego no estará resuelto oficialmente, pero ya lo está en la práctica.

Y entonces, AlphaZero es como una motocicleta en una carrera de 100 metros planos de seres humanos. Simplemente no podemos competir contra ella y listo. Pero eso no acabó con las carreras de los seres humanos y la razón es simple: sí, tenemos artefactos y dispositivos que juegan muy bien y mucho mejor que nosotros, los seres humanos, pero que en el fondo tienen otra naturaleza diferente al de la raza humana. Yo simplemente no me preocuparía tanto.

Creo que el alcance de AlphaZero será importante y modificará algunos aspectos de cómo vemos el ajedrez pero de ahí a decir que ya hay que guardar nuestras piezas y peones para siempre, me parece que no debe ser así. AlphaZero habla finalmente de algo importante: sabemos muy poco de ajedrez y ahora tenemos una herramienta formidable. Usémosla. Aprendamos de ella y sigamos dando jaques.
¿Por qué no?

¿El fin del ajedrez?

En 1997 Garry Kasparov perdía un match a seis partidas contra una máquina preparada sólo para jugar al ajedrez. IBM había puesto mucho dinero y su plan era demostrar que una máquina ya tenía la suficiente capacidad para derrotar al mejor jugador del mundo en este difícil arte del ajedrez. Pero 20 años después nos enteramos que DeepMind había puesto un programa llamado AlphaGo, a jugar contra el mejor jugador del juego chino Go, y que le había derrotado sin duda ninguna. Hoy DeepMind nos da la noticia que su programa, aplicado al ajedrez, logró en sólo cuatro horas de auto entrenamiento, el nivel de súper gran maestro y para ello ha usado su técnica de redes neuronales de aprendizaje reforzado. AlphaGo ha logrado entender más de 500 años de experiencia en ajedrez en tan sólo unas horas. Algo inconcebible e impresionante.

El algoritmo desarrollado por Google y DeepMind, sintetiza todo el conocimiento del ajedrez y para demostrar este nivel, los investigadores decidieron poner como rival a StockFish, el mejor programa de ajedrez de código abierto, que está entre los tres mejores programas (incluyendo los comerciales), del mundo.

AlphaGo venció a Stockfish en un encuentro a 100 partidas, por 28-0 y 72 empates. Es decir, el poderoso StockFish no pudo ganar una sola partida. Esto solamente habla de la capacidad del algoritmo de DeepMind, el cual ni siquiera necesita bases de partidas, tablas de finales o podas alpha-beta para correr.

El artículo “Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm” describe el trabajo realizado y sin duda es un parteaguas en el mundo del ajedrez por computadora. El enfoque es tan diferente a todo lo anterior hecho en esta disciplina que habrá que estudiar cómo es que este algoritmo de Google y DeepMind se está volviendo una de las maneras más eficientes para atacar problemas que no tienen solución definitiva y que se han atacado antes a través de heurísticas

Programación lúdica: ecualización del histograma de una imagen

El proceso digital de imágenes tiene una serie de técnicas para poder manipular los pixeles de una imagen. En un artículo pasado vimos la manera de ajustar el contraste a partir de estirar el histograma de frecuencias de valores de los pixeles en una imagen de tonos de gris. Cabe señalar que en una imagen de grises solamente puede haber 256 tonos diferentes, cuyas componentes de color son: (0,0,0) que es el negro; (1,1,1) que es menos negro... y así hasta (255,255,255), que es blanco.

Desafortunadamente el estirar el histograma no sirve cuando la diferencia entre el contraste mínimo y máximo es de 255, porque la fórmula para cada nuevo pixel sería: (TonoDeGris / 255) * 255, lo cual sería dividir entre 255 y multiplicar entre 255, lo que dejaría el resultado como el pixel original. Por ello, es necesaria otra técnica y ésta es lo que se llama la "ecualización de un histograma".

Cuando uno "ecualiza" algo, por ejemplo, una señal de audio, lo que hacemos es que los bajos y los altos se igualen. En lo que se refiere a gráficas, cuando hay muchos pixeles oscuros entonces se reduce esa cantidad y si hay pocos pixeles claros, se incrementan estos.

Para "ecualizar" (o igualar) los valores del histograma, lo que tenemos que hacer es simplemente crear algo que se llama CDF (Cumulative Distribution Frequency), lo cual es simplemente un arreglo de 256 bytes que contienen la suma de los valores de las frecuencias de los valores previos. Por ejemplo, si tenemos valores de frecuencias para los tones de grises: 52 tenemos 1, 53 tenemos 3, 58 tenemos 2 y 59 tenemos 3, entonces el CDF será 1, 4, 6, 9, etcétera, para el CFD[52], CDF[58] y CDF[59]. Simplemente sumamos el valor actual con el anterior y listo. Teniendo este valor, solamente nos falta calcular la ecualización de cada pixel, la cual es una función como ésta, para cada pixel en la imagen: NuevoPixel = round(((CDF[R]-1) / CDF[255]) * 255).

Para ver si esto funciona, tomemos la siguiente imagen de Lena:

Y procesemos de acuerdo a lo que hemos dicho:

Puede observarse que la imagen se ecualizó y el contraste cambió significativamente. Nótese cómo el histograma se "estiró" de alguna manera.

Cabe señalar que esta técnica puede no ser necesariamente la mejor pero todo dependerá de qué queremos hacer y por qué queremos ecualizar una imagen.

A quien le interese este tema, escríbame a morsa@la-morsa.com y le enviaré el software ejecutable y el código fuente escrito en Delphi.

Cómo realizar el contraste de una imagen

En el curso que doy en la Facultad de Ciencias de la UNAM, de Proceso Digital de Imágenes, enseño cómo hacer una serie de filtros, muchos de ellos se pueden ver directamente en Photoshop, aunque otros, sobre todo los artísticos, no parecen ser fáciles de saber cómo están hechos, porque no hay documentación al respecto y en el oráculo que es Internet no he encontrado referencias sobre los mismos.

De todas maneras en este blog ya he descrito muchos de los filtros que enseño y otros que incluso no están disponibles en Photoshop o que hacerlos mediante esta herramienta pudiese resultar muy problemático de simular.

Uno de los filtros más comunes es el del contraste, y existen un par de algoritmos para realizarlos. Cuando uno aplica este filtro lo que hace es mover normalmente un valor el cual modifica pixel a pixel la imagen con la que estamos trabajando. Sin embargo, el resultado final muchas veces se hace a "ojímetro", es decir, midiendo visualmente cómo se ve la imagen al aplicarle cierto contraste.

Hay, sin embargo, una idea interesante para contrastar imágenes de manera automática. Esto se hace a través del ajuste del histograma de una imagen, el cual se basa en diferentes pasos (primero hablaremos de imágenes en tonos de gris):

1.  cargar la imagen a procesar
2.  calcular el histograma de frecuencias de tonos de gris de la imagen
3.  Localizar los valores máximo y mínimo de los pixeles y hacer la resta de forma absoluta, es decir, nos dará el máximo contraste en términos positivos
4. Aplicar la siguiente fórmula: NuevoPixel = (TonoDeGris / MaximoContraste) * 255
5. Colocar el tono de gris nuevo en los tres componentes del pixel procesado (RGB).

Cabe decir que si tomamos el máximo contraste (MaximoContraste) como 255, la fórmula simplemente no hace nada, pues tendríamos: NuevoPixel = (TonoDeGris / 255) * 255, lo cual da que el valor es simplemente NuevoPixel = TonoDeGris, o lo que es lo mismo, multiplicamos y dividimos por 255.

Por ejemplo, la siguiente imagen de Einstein (ver siguiente figura), muestra su histograma que, como puede verse, tiende a estar más oscura que clara. Si tomamos la diferencia de contrastes como 225, entonces podemos aplicar la fórmula mencionada y ver cómo mejora la imagen.

Obsérvese (siguiente imagen), el resultado de esto. Nótese cómo cambia el histograma también.

Este procedimiento, como se mencionó, falla si tomamos 255 como el máximo contraste porque entonces no le estamos haciendo nada a la imagen. Sin embargo, se me ocurrió que bien podría yo decirle el valor máximo de contraste y debería funcionar. Como no estaba seguro de esto, hice el programa en cuestión y ¡ay! hallé que en principio sirve, pero deja "artefactos", es decir, puntos indeseables que no deberían quedar en la imagen procesada (véase la siguiente imagen)

Este proceso puede hacerse para imágenes en color también (no lo he hecho aún), pero en los documentos y páginas web que he leído, aparentemente funciona. Ya hablaré de los resultados de este proceso usando color, pero pienso que igual que en el caso anterior de tonos de gris, en algunos casos el procedimiento también dejará artefactos.

La solución es hacer una ecualización del histograma, pero esto es más complejo y lo abordaremos en otro artículo. Mientras tanto, dejo accesible el código fuente y ejecutable en Delphi de este programa. Basta con pedírmelo a mi correo morsa@la-morsa.com y lo encontrará a la brevedad en su buzón.