Una IA capaz de resolver crucigramas pudo vencer a los campeones del torneo más importante del mundo

Publicado el

crucigrama

Nuevamente, se han puesto a prueba las capacidades de la inteligencia artificial, con interesantes resultados.

Investigadores de la Universidad de California en Berkeley, presentaron recientemente Berkeley Crossword Solver, el primer programa de ordenador capaz de superar a todos los competidores humanos en el torneo de crucigramas más importante del mundo.

Un algoritmo capaz de resolver crucigramas complejos eficientemente

El algoritmo desarrollado en UC Berkeley es capaz de resolver crucigramas mediante un procedimiento en el que, en primer lugar, se genera una distribución de probabilidad sobre las posibles respuestas a cada pista presentada, planteándoselas al sistema a modo de pregunta. El algoritmo tiene la tarea de mapear tanto las preguntas como las respuestas en un espacio integrado compartido, que permite manejar los conflictos —a través de un método de inferencia probabilística— entre las posibles respuestas, de acuerdo a cómo se cruzan en la grilla del crucigrama.

Para refinar los resultados obtenidos, el algoritmo ejecuta una búsqueda en una base de datos local, con el propósito de reafirmar la elección de determinadas letras que no generen la suficiente confianza como para considerarlas adecuadas. Para realizar esta comprobación, el sistema utiliza un modelo de lenguaje generativo, que reemplaza las letras conflictivas iterativamente, hasta que se encuentra una solución localmente óptima.

Este desarrollo fue denominado como Berkeley Crossword Solver y fue diseñado para resolver únicamente crucigramas al estilo americano. Por lo general, estos crucigramas involucran temas de cultura general, juegos de palabras y pistas desafiantes. Usualmente, varían en tamaño de cuadrícula de 15×15 a 21×21.

Este modelo fue sujeto a evaluación con crucigramas de cinco de las principales editoriales de crucigramas, incluyendo las aclamadas publicaciones de The New York Times. Producto de estas pruebas, se pudo demostrar que el sistema obtiene una precisión de letra del 99,7% en promedio.

Un algoritmo ganó la competencia más importante de crucigramas

El American Crossword Puzzle Tournament (ACPT) es el torneo de crucigramas más grande y de mayor duración y está organizado por Will Shortz, el editor de crucigramas del New York Times. 

Para participar de la edición 2021 del ACPT, el equipo de Berkeley se asoció con Matt Ginsberg, desarrollador de Dr. Fill, un software que previamente participó de la misma instancia en 2012, consiguiendo el puesto 141 entre 650 competidores. En esta nueva oportunidad, fue combinada una versión anterior del sistema de control de calidad de Berkeley con el procedimiento de búsqueda de Dr. Fill. Esta combinación dio buenos resultados, haciéndolos ganadores del certamen, frente a más de mil competidores. El sistema resolvió los siete acertijos planteados como desafío en menos de un minuto, faltando sólo tres letras en dos acertijos.

Este sistema continuará sujeto a mayores perfeccionamientos. Para incentivar su desarrollo, fue publicado un conjunto de datos de 6,4 millones de pistas de respuestas a preguntas y el código de esta herramienta, junto con una demostración interactiva en el sitio web de Berkeley Crossword Solver.