Una de las definiciones que más me gustan de un sistema de Inteligencia Artificial (IA) es la debida a Ray Kurzweil, quien afirma que “son programas que realizan tareas que cuando las hace una persona requiere inteligencia para llevarlas a cabo”. ¿Cuáles son estas tareas que requieren inteligencia para llevarlas a cabo? Bueno, existen varias, pero sin duda una de las más distintivas de los seres humanos es la de jugar (especialmente entre adultos) y es en la que me gustaría centrar este artículo.
¿Qué tienen los juegos que los hace tan atractivos para aplicarles las técnicas de IA?
En primer lugar, que el estado del juego en un momento dado (las piezas y sus posiciones) es fácil de representar y generalmente están restringidos a un pequeño número de acciones cuyos resultados están definidos por reglas precisas (las del juego en cuestión).
En segundo lugar, son interesantes porque son demasiado difíciles de resolver, no son los problemas triviales que se plantean para el desarrollo y comprobación de algoritmos. Por ejemplo, el ajedrez tiene un número de medio de posibilidades por movimiento de 35 (esto se llama factor de ramificación) y una partida típica dura unos 50 movimientos por oponente, lo que en teoría nos proporciona un espacio o árbol de búsqueda (de movimientos teóricamente posibles a realizar en una partida), de 35100, aunque típicamente el número de movimientos posibles reales es de “sólo” 1040.
Y en tercer y último lugar, los juegos son interesantes porque penaliza mucho la ineficiencia en los algoritmos de búsqueda ya que normalmente hay un tiempo limitado para realizar un movimiento, por lo que la investigación en juegos ha sido prolífica en descubrir cómo hacer un uso eficiente del tiempo.
Merece la pena que repasemos como los sistemas de IA han ido conquistando el ajedrez, aunque sea a un nivel divulgativo, ya que éste es uno de los juegos que tradicionalmente más se ha asociado con la inteligencia humana y cómo los hallazgos obtenidos para este propósito han pasado al campo de la IA en general.
Para jugar bien al ajedrez un sistema de IA ha de hacer tres cosas:
En primer lugar ha de aplicar algún tipo de técnica que le permita encontrar el movimiento óptimo (esto se hace a través de un algoritmo conocido como minimax), teniendo en cuenta que existe enfrente un adversario con «información perfecta» (es decir, que conoce de antemano nuestra estrategia y sus consecuencias).
En segundo lugar, el sistema de IA ha de aprender a reducir el espacio de búsqueda para poder elegir un buen movimiento cuando el tiempo de búsqueda es limitado (aunque quizás no el óptimo), para lo cual se utilizan técnicas que permiten ignorar las porciones del árbol de búsqueda que no hacen ninguna diferencia de cara al resultado final y por tanto son «prescindibles» (el algoritmo más usado para esto se llama podado [del árbol] alfa-beta).
Finalmente, hay que hacer uso de funciones de evaluación heurísticas (basadas en la experiencia de los jugadores de ajedrez) que nos permitan aproximar lo “buena” que es una posición concreta del juego en una partida sin tener que hacer una búsqueda completa de todos los movimientos posibles “hacia adelante” de la partida.
Por otro lado, en cuanto al desarrollo del juego, las partidas de ajedrez tienen 3 fases: la apertura, el juego medio y los finales. Al principio de las partidas, en las aperturas, el árbol de búsqueda es enorme, por lo que, en vez de calcular el mejor movimiento, lo que nos haría perder por exceder del tiempo asignado (y si se juega sin límite de tiempo por aburrimiento de nuestro oponente), es mucho más rápido usar una estructura de datos denominada tabla de consulta que se almacena en la memoria del sistema de IA, donde ésta puede consultar los movimientos a jugar en estas primeras jugadas, lo que es equivalente a disponer de un “libro de aperturas”.
Este mismo razonamiento se utiliza para los finales de partida. Ya han sido resueltos todos los finales de partida de cinco piezas (por oponente) y muchos con seis piezas, por lo que en esta fase los sistemas de IA son implacables, mejorando las prestaciones de los mejores jugadores humanos.
Es en el juego medio con todos sus matices tácticos y estratégicos donde las fuerzas con los seres humanos están más igualadas en la actualidad. Aquí la clave está en usar una función de evaluación potente con decenas o centenares de características.
En 1997, anunciando el fin de la supremacía de los seres humanos en el ajedrez, el sistema Deep Blue de IBM (un superordenador con 30 microprocesadores IBM RS/6000 trabajando en paralelo) venció al campeón del mundo Garri Kasparov (3,5-2,5). Según los expertos, la victoria se basó en la capacidad bruta de procesamiento, capaz de buscar 30.000 millones de posiciones por movimiento y “anticipar” 14 niveles de forma habitual frente a los 5 o 6 niveles de anticipación de los grandes maestros. La clave estaba que en las posiciones más prometedoras en términos de movimientos de “obligar” al oponente o también, “forzados” por el oponente, podía “anticipar” hasta 40 niveles. La función de evaluación tenía más de 8.000 características del juego, algunas muy específicas de determinados patrones de juego, un libro de aperturas de más de 4.000 posiciones y una base de datos de 700.000 partidas de grandes maestros de las cuales se extrajeron recomendaciones consensuadas de juego.
Kasparov vs IBM Deep Blue, 1997
Desde aquel encuentro, que supuso un duro varapalo para el orgullo de la Humanidad, el incremento exponencial de la capacidad de computación junto el refinamiento de las estrategias de búsqueda de la IA (que permitió rebajar el factor de ramificación ¡de 35 a 3!) hizo que, en 2006 y con un ordenador normal de sobremesa, el programa Deep Fritz venciera al campeón mundial Vladimir Krámnik por 4-2.
En todo caso estas estrategias de IA desarrolladas para jugar al ajedrez (y a otros juegos) se han usado posteriormente en la vida real, por ejemplo, en sistemas de planificación de rutas de flotas de vehículos o en secuenciadores industriales que planifican el flujo de piezas y componentes en las líneas de montaje de las plantas industriales. La importancia de estas técnicas de búsqueda en el espacio de soluciones en el desarrollo de los sistemas de IA es tan grande que muchos expertos piensan que “los sistemas de IA son, en esencia, formas más o menos ingeniosas de reducir el espacio de búsqueda”. La diferencia es que en la vida real no suele existir un «adversario», por lo que se pueden ampliar la gama de técnicas de búsqueda en el espacio de posibles opciones permitiendo una gama más rica de algoritmos.
En la actualidad, una vez superado el shock inicial por la derrota de Kasparov y la mejora de los programas de ajedrez hasta alcanzar capacidades sobrehumanas, estos programas se han convertido, en vez de la amenaza para la Humanidad que algunos esperarían, en un reto, una fuente de inspiración y estudio para los jugadores de todo el mundo, que ahora aprenden nuevos movimientos y combinaciones de los sistemas de IA.
Este, por cierto, es un comportamiento que nos vamos a ir encontrando en otros juegos y otros campos donde han entrado los sistemas de IA, pero eso será materia para otro día.
