Monte Carlo, además de ser un distrito de Mónaco famoso por su casino, es un método no determinista para encontrar aproximaciones a problemas complejos. Básicamente se basa en usar el azar para simular muchos casos de estudio y evaluar estadísticamente los resultados de esas simulaciones.
En el caso del baduk, desde hace unos pocos años se está aplicando con aceptable éxito. El ordenador simula, dada la posición a estudiar, miles de partidas aleatorias y estima que porcentaje ganó blanco o negro. La idea de aplicar Monte Carlo al juego ya se dio en los 90, pero últimamente ha tenido éxito, consiguiendo que un ordenador salte la barrera del dan.
Eso si, tampoco hay que ser triunfalistas y lanzarse a decir que en 10 años tendremos un campeón del mundo robótico. Cada paso en baduk es más difícil. Por ejemplo, un 10 kyu tiene un 34% de posibilidades de ganar a un 9 kyu, mientras que un 5 dan sólo un 20% de ganar un 6 dan. De mi experiencia con profesionales coreanos también veo que de 6 a 7 dan amateur hay un mundo, y de estos a 1 dan pro más. De ser un pro del montón a ser uno del top 100 hay otro mundo, y de ahí a llegar al top 10…
Técnicas de inteligencia artificial se han utilizado muchas. Las más sencillas son crear mapas de influencia (véase el vídeo), reglas sobre libertades y n-libertades (las libertades de las libertades, como usa GNU Go). Por otro lado también se han explorado aproximaciones de análisis de patrones, ideales para secuencias de esquinas. Por supuesto se han aplicado redes neuronales. O incluso aproximaciones de alto nivel, creando reglas tipo «para matar un grupo primero tienes cortar todas sus salidas».
En mi opinión Monte Carlo no será la piedra que consiga la victoria final para las máquinas. Es necesario una nueva revolución en algorítmica, o dos, hasta llegar a ver a una máquina dando 3 piedras a un profesional (según Otake Hideo, sería el hándicap entre un pro y dios). Mientras tanto, podemos disfrutar jugando con los numerosos programas que se han creado o reprogramando usando Monte Carlo: desde los bots de Zen en KGS, a jugar con Fuego en la web (es muy bueno en 9×9). O incluso descargar Fuego y compilarlo en Linux.
Me ha llamado la atención la dificultad creciente que comentas en subir cada peldaño. Llevo cerca de un año aprendiendo Go, y desde muy pronto me dio la sensación de que una de las diferencias grandes con el ajedrez es que en el Go hay, por así decirlo, más capas de aprendizaje, de pofundización. Digamos que en ajedrez un elo de 2500 tiene alguna posibilidad de ganar a un 2700, pero mi sospecha es que el equivalente a un 2500 en Go prácticamente no tendría niguna oportunidad contra un 2700 (estoy quitando de la lista los errores exagerados; dejarse una pieza, o no ver un atari a un grupo grande).
Sobre el tema de los motores, recientemente ha aprecido lo que podría ser un nuevo acercamiento al problema. Hay un tipo de red neuronal, «Convolutional Neural Networks», con las que al parecer se ha conseguido una red neuronal bastante compente; por ejemplo, venciendo de manera bastante consistente a GnuGo.
http://arxiv.org/pdf/1412.3409v1.pdf
El caso es que las redes neuronales, dada una posición, proporcionan un output de manera casi instantánea. El nuevo acercamiento podría ser el de usar una de estas redes para decirle a un motor «tipo montecarlo» el orden en que analizar los movimientos, para hacer más rápida la búsqueda.
Si, es muy típico pensar que las diferencias de nivel no son tan marcadas, pero la profundidad del Go es muy grande. Dicen que un 10 kyu necesitaría un libro para explicar todo lo que sabe, mientras que un 1 dan necesita una enciclopedia.
Había visto el paper sobre esas redes neuronales aplicadas al Go, y la verdad es que soy relativamente escéptico. Básicamente porque a nivel dan ya se juega con conceptos totalmente abstractos: acabar una secuencia en sente, intercambios, maximizar el uso de una piedra muerta, ser muy flexible, etc. Estos conceptos me parece más lógico abstraerlos usando algún sistema de reglas heurísticas que con una red neuronal. Una red neuronal lo hará muy bien en campos como el reconocimiento de patrones, pero sospecho que no tan bien con reglas abstractas. Quizás se necesite un sistema híbrido. En todo caso, el tiempo dirá.
De todas formas sospecho que faltan al menos 2 revoluciones en algorítmica antes de llegar a ver a una computadora batiendo a un profesional a igualdad.