lunes, 24 de enero de 2022

El ajedrez y el factor escala en el aprendizaje algorítmico

Usando unos mecanismos que en estos momentos nos son desconocidos, el cerebro humano es capaz de evaluar situaciones y responder de forma adecuada, o al menos razonable, de forma casi instantánea. No sabemos cómo lo hace y lo cierto es que, cuando estamos en el campo de la algoritmia, nos vendría muy bien saberlo, porque nos permitiría seguramente resolver computacionalmente problemáticas que hoy en día nos están vedadas o, al menos, nos resultan complejas.

Algunos de los fenómenos que los humanos parecemos ser capaces de gestionar bastante bien es la ambigüedad, las situaciones o datos que no son 'blanco' o 'negro' o los casos con información incompleta. Aunque a nivel algorítmico se van produciendo avances en esa línea, lo cierto es que cuesta conseguir buenos resultados.

Otro aspecto que los humanos (y otros seres vivos) somos capaces de manejar bien, no sé si de manera óptima pero al menos sí razonable, es lo que aquí he denominado factor escala y que se refiere a la cantidad de opciones posibles en un momento dado. 

Y eso es lo que quisiera traer a colación, no para descubrir nada nuevo, sino para ilustrar para el lector que lo desconozca, lo importante que esa esa escala y las dificultades que genera a nivel algorítmico.

Y lo comento usando el socorrido mundo de los juegos, de los juegos de mesa, tan utilizado para la investigación en inteligencia artificial.

Lo bueno de los juegos, como campo de estudio es que ofrecen un entorno hasta cierto punto complejos pero con reglas muy claras y con un número de opciones finito, cosa que los hace relativamente manejables para el estudio, la experimentación... y la consecución de éxito. En cierto sentido, podemos decir que este tipo de juegos eliminan el factor ambigüedad y limitan, aunque no siempre en muy alta medida, la escala. 

Pero pasemos ya a comentar brevemente el efecto de esa escala.


La fuerza bruta y la programación tradicional


En juegos muy sencillos, es posible resolverlos mediante programación tradicional (programación que no incluye aprendizaje y en que las reglas son explícitas). Estoy pensando en el caso, por ejemplo, del tres en raya.

Aunque debo confesar que ya no recuerdo exactamente cómo lo hice, sí puedo decir que hace muchos años, cuando comenzaba el 'boom' de la informática personal y cuando yo daba mis primeros pasos (bueno, quizá segundos pasos) en programación, desarrollé, en el venerado Turbo PASCAL, un programa que jugaba al tres en raya. No me costó demasiado tiempo. Se me han olvidado muchos detalles pero recuerdo que lo que le introduje en su lógica fue una cascada de reglas, unas reglas que me inventé yo mismo, que no eran muchas y que no sé si eran perfectas o no, pero lo cierto es que el programa jugaba bien o muy bien y creo que nunca conseguí ganarle, sólo empatar. 

En esto consisten en general los algoritmos de programación tradicional: simplemente, el programador (o el diseñador) sabe qué reglas hay que aplicar, las especifica de manera inequívoca y las traslada al software. Y el comportamiento externo es perfectamente inteligente aunque no consideremos esto realmente inteligencia artificial.

Hay otra forma: la fuerza bruta. Se trata, simplemente, de ensayar todas las opciones y quedarse con la buena, algo que conocemos, por ejemplo, del mundo de la ciberseguridad donde una contraseña corta se puede llegar a descubrir mediante fuerza bruta (de ahí la limitación de intentos en un 'login'). 

En el caso de un juego sencillo. como es el tres en raya, esta fuerza bruta se podría aplicar de una forma muy sencilla. En el tres en raya sólo hay nueve casillas, y cada una de esas casillas sólo puede estar en tres estados: vacía, ocupada por el jugador A u ocupada por el jugador B. Es decir, el número de estados posibles es:


NUMestados = 39 = 19.683


En realidad, ni siquiera hay 19.683 estados posibles porque no todas las combinaciones están permitidas. Así, por ejemplo, no es posible que todas las casillas estén ocupadas por el jugador A o todas por el jugador B. En realidad, el número de casillas ocupadas por A y B debe ser igual en número o superior en uno a favor del jugador que inicia la partida (digamos que el A). No sé cuántos jugadas de ese total de 19.683 habría que descartar, pero tampoco importa mucho para lo que nos ocupa. Estamos hablando de un juego en que el número de estados posibles es de unos pocos miles. Unos pocos miles en computación no es demasiado. Una forma, no digo que la mejor, pero una forma viable, de aplicar fuerza bruta sería, simplemente, hacer una base de datos con una tabla de diez columnas: las nueve primeras representarían el estado de cada casilla y la décima, la jugada que debería hacerse. El algoritmo lo único que tendría que hacer, en cada jugada, es consultar en la base de datos cuál es la jugada a realizar en la situación en que se encuentra en ese momento.

En este caso, aplicamos en cierto sentido fuerza bruta, porque tenemos la solución para todas las posibilidades. Y, de nuevo, no lo consideramos inteligencia artificial, porque lo inteligente no es el algoritmo sino la persona que rellena la tabla de la base de datos. 

En cualquier caso, estamos ante una situación de una escala muy manejable, lo cual permite su resolución muy efectiva (perfecta, en realidad) mediante algoritmos relativamente sencillos y con unas necesidades computacionales limitadas.


La búsqueda alfa-beta


Pero ahora damos el salto a un juego mucho más difícil: el ajedrez. En este caso, y según descubro en el libro 'Artificial Intelligence. A modern approach' de Stuart Russell y Peter Norvig el número de jugadas posible es de 1040 jugadas,

1040 es un número gigantesco y que, al menos hasta la llegada efectiva de la computación cuántica, no permite la fuerza bruta... y mucho menos para hacerlo en tiempo real, como debe ser un juego.

Un juego como el ajedrez (también el tres en raya, por cierto) se puede resolver mediante los algoritmos de búsqueda en un árbol alfa-beta, donde se va generando y explorando un árbol de opciones y usando, para evaluar cada opción una función de utilidad. Esa función de utilidad se debe maximizar para el jugador que 'somos' y minimizar para el contrario, dando lugar a lo que se denomina el 'minimax',

Sin embargo, si no hacemos nada más, este algoritmo es casi una forma de fuerza bruta. En la realidad, sin embargo, estos algoritmos de búsqueda se sofistican bastante mediante el uso de diversas estrategias y heurísticas que disminuyen mucho el espacio de búsqueda efectivo (aunque con riesgo de no adoptar la decisión óptima, sino sólo una buena decisión). Además, y si se quiere que esto se haga en tiempo real o cuasi-real se trabaja con superordenadores altamente paralelos.

Así es como trabajaba el famoso 'Deep Blue' que batió a Kasparov.  

Es una forma de afrontar la escala, y una forma que se aplica con éxito hoy en día.


El aprendizaje supervisado


Otra forma es el uso del aprendizaje supervisado

En este caso, de alguna forma es el algoritmo el que tiene que descubrir el patrón subyacente (en este caso podríamos pensar en la estrategia para jugar bien) a partir de una serie de datos de ejemplo en que se instruye al algoritmo acerca de cuál es la respuesta correcta en cada caso.

Así, en el caso del ajedrez, podríamos tomar como datos de ejemplo las partidas de grandes maestros en que estos maestros han ganado. Y podríamos asumir que, aunque quizá no necesariamente óptimas, las jugadas que realizaron en esas partidas que ganaron eran, quizá no perfectas, pero sí buenas.

Pero hay, sin embargo, hay una gran dificultad y que tiene que ver con la escala 

Según descubro leyendo a Russell y Norvig (y debo confesar que el dato que viene a continuación es lo que me inspiró este artículo),  aplicando esa forma de tener datos de ejemplo de buenas jugadas, 'sólo' hay disponibles 1010 (diez mil millones) de jugadas. Diez mil millones pueden parecer muchas, pero si se comparan esos diez mil millones, 1010, con los 1040 de jugadas posibles, nos damos cuenta de que estamos enormemente lejos de cubrir todas las opciones posibles, eso sin contar con el tiempo y recursos computacionales que podría consumir el aprendizaje,

Por supuesto, es imposible, al menos con la tecnología actual, aplicar la fuerza bruta al ajedrez, pero tampoco parece muy prometedor conseguir buenos resultados con un aprendizaje supervisado, lo cual no quita a que los algoritmos de aprendizaje supervisado sean muy exitosos hoy día en muchos campos y hayan permitido resolver de forma satisfactoria muchos problemas, y muchos problemas complejos, además.


Otras formas de aprendizaje


Ya comentaba hace unas semanas, en el artículo titulado 'La equívoca relación de inteligencia artificial y datos: cinco mitos comunes' cómo la dependencia de los datos en el entrenamiento de los algoritmos es en realidad una forma de limitación. 

Una parte importante de la investigación en algoritmia de aprendizaje (el 'transfer learning', el aprendizaje parcialmente supervisado o el aprendizaje por refuerzo, por ejemplo) tienen que ver, al menos en parte, con formas de aprendizaje más económicas en datos... como parece que es, aunque tampoco podemos estar seguros de ello, el aprendizaje humano. 


No hay comentarios:

Publicar un comentario