miércoles, 4 de febrero de 2015

Cae otro bastion de la superioridad humana


Uno de los últimos bastiones de la superioridad humana sobre los ordenadores está a punto de caer a manos de los implacables algoritmos de aprendizaje automático
Los ordenadores empiezan a funcionar mejor que los humanos en prácticamente todos los campos. Por ejemplo, los expertos en visión automática revelaron hace poco un algoritmo que es mejor que los humanos a la hora de reconocer caras. Empieza a haber algoritmos de este tipo con la misma capacidad que los humanos para reconocer objetos. Y los ajedrecistas hace tiempo que se rindieron en la lucha contra los ordenadores.



Pero existe un campo en el que los humanos aún triunfan y es en el antiguo juego chino del Go. Los ordenadores nunca han llegado a dominar este juego. Los mejores algoritmos sólo logran el nivel de un buen aficionado al que los mejores jugadores humanos superan con facilidad.




Sin embargo, parece que eso va a cambiar gracias al trabajo de Christopher Clark y Amos Storkey en la Universidad de Edimburgo (Reino Unido). Estos investigadores han aplicado las mismas técnicas de aprendizaje automático que han transformado los algoritmos de reconocimiento facial al problema de encontrar la próxima jugada en una partida de Go. Y sus resultados dan pocas esperanzas a la continuidad del dominio humano en este juego.




En pocas palabras, el Go es un juego para dos jugadores que se suele jugar sobre un tablero de 19 x 19 casillas. Los jugadores se turnan para colocar piedras blancas y negras en las casillas con el objetivo de haber ocupado un espacio mayor que su oponente cuando acaba la partida. Los jugadores pueden eliminar las piedras del contrario rodeándolas con las propias.




Los expertos creen que hay dos motivos por los cuales los ordenadores no han conseguido dominar el Go. El primero es la tremenda cantidad de movimientos posibles en cada fase del juego. Los jugadores de Go tienen 19 x19 = 361 posibles movimientos de apertura y suele haber cientos de movimientos posibles en cualquier punto del juego. En comparación, la cantidad de movimientos posibles en el ajedrez suele ser de 50.




El segundo problema es que a los ordenadores les cuesta evaluar los puntos fuertes y débiles de una posición de juego. En el ajedrez basta con sumar el valor de cada pieza que sigue sobre el tablero para tener una idea razonable de la fuerza de la posición de un jugador. Pero eso no funciona con el Go. "Contar la cantidad de piedras que tiene cada jugador no es un buen indicador de quién va ganando", afirman Clark y Storkey.




Los algoritmos más avanzados para el análisis del Go abordan este problema jugando toda la partida después de cada movimiento de muchas formas distintas. Si el ordenador gana la mayoría de estas partidas, entonces se considera que la jugada es buena.




Claramente se trata de una tarea que lleva mucho tiempo y necesita bastante potencia computacional. Aún así no suele servir para ganar a los expertos humanos en Go que valoran el estado de un tablero de Go con un simple vistazo.




Muchos expertos creen que el secreto para dominar el juego del Go es el reconocimiento de patrones, la capacidad de detectar puntos fuertes y débiles basándose en la forma que adoptan las piedras y no pensando en varias jugadas posibles.




Por eso los avances recientes en algoritmos de patrones de reconocimiento podrían ayudar a los ordenadores a hacer este trabajo mucho mejor. Estos avances han usado enormes bases de datos de imágenes para entrenar redes neuronales convolucionales de aprendizaje profundo a reconocer objetos y caras con una precisión comparable a la de los humanos. Así pues, resulta razonable imaginar que este mismo enfoque serviría para cambiar mucho las cosas en la evaluación automática de los tableros de Go.




Y eso es exactamente lo que han hecho Clark y Storkey. Han entrenado a una red neuronal convolucional para responder a la siguiente pregunta: Partiendo de una imagen de una partida de Go entre dos expertos, ¿se puede predecir la próxima jugada?




Han abordado el problema usando una vasta base de datos de partidas de Go para entrenar a una red neuronal para que encuentre el siguiente movimiento. Clark y Storkey usaron más de 160.000 partidas entre expertos para generar una base de datos de 16.5 millones de posiciones junto con su siguiente jugada. Usaron casi 15 millones de estas parejas de posición-jugada para entrenar a una red neuronal convolucional de ocho capas para reconocer qué jugada harían los jugadores expertos. Este proceso llevó varios días.




Después usaron el resto de datos de la serie para poner a prueba la red neuronal. Es decir: presentaron a la red una posición de una partida y le pidieron que escogiera la siguiente jugada. Clark y Storkey afirman que la red entrenada así es capaz de predecir la siguiente jugada un 44% de las veces, "superando a los mejores programas anteriores para esta tarea por un margen significativo".




Eso es interesante para empezar porque el nuevo enfoque no usa ninguna de las jugadas anteriores para tomar su decisión y tampoco evalúa posiciones futuras.




Una vez entrenada la red neuronal, Clark y Storkey la hicieron jugar contra dos de los mejores algoritmos para jugar al Go que existen. El primero se llama GNU Go, que juega a un nivel equivalente a un amateur intermedio con un nivel de 6-8 kyu. (Los niveles de Go van desde principiante, con una puntuación de 30-20 kyu, a experto profesional, con un nivel de 1 kyu).




El segundo es el mejor programa que existe, llamado Fuego 1.1. que tiene un nivel de aproximadamente 5-4 kyu. Un jugador humano tiene que estudiar muchos años para alcanzar este nivel.




Los resultados sugieren claramente que a los jugadores humanos de Go se les está acabando el monopolio. La red neuronal de Clark y Storkey ganó a GNU Go casi el 90% de las veces en una serie de 200 partidas. Es decir: tras apenas unos días de entrenamiento, la red neuronal podía ganar a GNU Go con consistencia.




Contra Fuego 1.1 le fue peor, ya que ganó un poco más del 10% de sus partidas. Sin embargo, es un logro importante. "Poder ganar aunque solo fuera unas cuantas partidas contra este contrincante significa que había adquirido alto nivel de habilidad", afirman Clark y Storkey.




Algo claramente prometedor. "A pesar de que las redes juegan con una política de 'búsqueda de jugadas futuras cero' y una fracción del tiempo de computación del que usan sus contrincantes, juegan mejor que GNU Go y consiguen ganarle algunas partidas a Fuego", afirman.




Y hay un claro margen para mejorar, al combinar por ejemplo este enfoque con otros que sí usan movimientos previos y futuros. Una idea sugerida por Clark y Storkey es ejecutar la red neuronal convolucional en paralelo con el método convencional para poder sacarle todo el jugo a los posibles movimientos a explorar.




Clark y Storkey no sugieren en ningún momento que este método pueda ganar a los mejores jugadores de Go del mundo. Pero seguro que sólo es cuestión de tiempo que los jugadores de Go tendrán que inclinarse ante sus señores informáticos.




Ref: arxiv.org/abs/1412.3409: Enseñar a Redes Neuronales Convolucionales de Aprendizaje Profundo a Jugar al Go