¿Cómo aprende una máquina a ganarnos en un juego?

Por Colaborador Invitado, el 19 octubre, 2016. Categoría(s): Divulgación • Tecnología

robot

El aprendizaje en máquinas es algo que está a la orden del día. Habitualmente vemos ordenadores que aprenden a ganarnos en juegos como el Ajedrez, Go, etc. Este aprendizaje nos produce inquietud ya que nos planteamos cosas como “¿Qué está aprendiendo realmente?”, “¿Hasta dónde aprende?”. Estas inquietudes se basan en que pensamos en el aprendizaje de una máquina como en el aprendizaje humano porque es el que conocemos. ¿Realmente una máquina aprende como nosotros? ¿Cómo lo hace?, esas preguntas vamos a responderlas a continuación.

Antes de ver cómo aprende una Inteligencia Artificial debemos conocer cómo juega, esto es interesante porque nosotros lo hacemos de forma parecida aunque no nos damos cuenta.

minimax

Una máquina ve el juego como un árbol en el que cada jugada es un nodo, cada uno de los nodos da lugar a diferentes jugadas, cada una de las cuales tendrá un valor que dependerá de lo prometedora que sea. Si juega contra un adversario, entre cada nivel de nodos con sus jugadas habrá otro con las jugadas posibles de dicho adversario. ¿Y cómo elige qué hacer? muy sencillo, imaginemos que estamos en un nodo A; desplegaremos nuestras posibles jugadas en sus nodos hijos. Después, de esos nodos hijos desplegamos los posibles “contraataques” del oponente, y así hasta llegar a los nodos que acabarán el juego o a cierto nivel si hemos puesto un límite de cálculo de jugadas. Ahora damos un valor a los nodos terminales con una función de utilidad (puede ser las fichas comidas, avance en el tablero, etc.). Después recorremos el árbol de abajo hacia arriba, dando a los nodos superiores el valor mayor de los nodos inferiores si estamos en la hilera de nuestro turno o el menor si es el nivel de nuestro oponente. Iremos subiendo hasta llegar al nivel de la jugada en la que nos encontramos y realizaremos el movimiento de mayor valor.

Lo malo de este algoritmo es que debemos recorrer todo el árbol antes de tomar una decisión, eso es algo que lleva mucho tiempo. Para ahorrar tiempo podemos hacer dos cosas:

  1. Establecer una profundidad límite de recorrido del árbol.
  2. Podar aquellas ramas cuyo valor no nos interese y acortar la anchura del árbol.

La opción 2 es muy útil en juegos con muchas posibles jugadas, como el ajedrez. En el caso de la poda: ¿cómo sabemos que no estamos podando una rama que nos podría llevar a la victoria, aunque a priori sea mala?, ¿por qué no podar en su lugar una rama que parece muy prometedora pero nos va a dar menos posibilidades de éxito al elegirla? Aquí es donde entra en juego el aprendizaje.

Imaginemos un hortelano cuidando de un árbol frutal. En la época de poda elegirá eliminar aquellas ramas débiles que no darán producción y quitarán la fuerza al árbol, dejando aquellas ramas más fuertes que aseguren una mejor producción. A priori parece algo sencillo, pero en base a su experiencia, el hortelano podrá dejar alguna rama menos fuerte porque le vea algunas yemas que indiquen que va a tener una buena floración. También podrá eliminar una rama muy fuerte porque le esté quitando fuerza al resto de ramas, o porque sabe que no va a producir como se esperaba. Si nuestra máquina poda en función del valor de los nodos, no va a poder tener esa experiencia que le dice “mejor poda esa otra rama que esta te puede ir bien”. Para que adquiera ese conocimiento se debe usar una Red Neuronal.

Una red neuronal puede dotar a nuestro sistema de una forma de podar más inteligente, escogiendo las mejores ramas en base a lo aprendido por su experiencia. Las redes neuronales no son más que un conjunto de unidades funcionales que aplican una función matemática a un valor de entrada, al que se suma un peso y dan como resultado un valor de salida. A estas unidades las llamamos neuronas. Estas redes constan de varias capas de neuronas interconectadas, el número de capas dependerá del problema que vayamos a resolver. A continuación se muestra un esquema de red neuronal.

rna

Para saber más de redes neuronales os invito a leer el siguiente artículo: I.A. Sobrevivir en un mundo que no es binario

La red neuronal dotaría a nuestro sistema de capacidad de aprendizaje, esto es, la máquina jugaría contra nosotros y cada vez que se equivocase modificaría los pesos de los valores de entrada. Haciendo esto, modificaría su comportamiento para tomar mejores decisiones y ganarnos. Para conseguir que aprenda bien deberíamos hacer que juegue contra diferentes oponentes y así se acostumbre a distintas formas de jugar. Esto haría que nuestro sistema consiguiese ser prácticamente imbatible, pues en base a lo aprendido elegiría jugadas que le llevasen a la victoria, pero nuestro sistema no sería perfecto. Si la máquina se acostumbra a ganar de un determinado modo, nunca tomaría decisiones arriesgadas para buscar otras formas de ganarnos y, si se enfrenta a un jugador que consigue aprender sus patrones aprendidos no podrá ganarle.

¿Qué hacer para que nuestra red neuronal no tome siempre las mismas decisiones? Si queremos que nuestra máquina tome decisiones más arriesgadas, que puedan descolocar al oponente y hacernos pensar que su comportamiento es inteligente, lo que debemos hacer es meterle un poco de azar. Para ello podemos usar el Método de búsqueda de Montecarlo. Este método sustituiría a nuestra poda porque no evalúa cada nodo del árbol, sino que hace recorridos aleatorios empleando los resultados de sus recorridos anteriores. El método de Montecarlo va construyendo de forma gradual un árbol en memoria, este árbol irá mejorando con cada recorrido estimando los valores de los movimientos más prometedores. Tiene cuatro pasos principales, que se repetirán hasta que encontremos la mejor solución o hasta un límite de tiempo que escojamos. En cada iteración se parte del nodo en el que nos encontramos en el juego.

  1. Selección: recorre el árbol desde el nodo actual hasta encontrar un nodo hoja, se elegirán las ramas en función a la estrategia de selección que se determine (fichas comidas, avance en el tablero…) y de la información que se haya almacenado en ese nodo en ese momento (valor y número de visitas). Para cada uno de los movimientos posibles calcularemos una combinación de la tasa de éxito de ese nodo y las veces que lo hemos visitado, se usará un coeficiente para dar más prioridad a una u otra.
  2. Expansión: se añaden hijos al nodo según un criterio. Éste se puede expandir siempre que visitemos un nodo o cuando se alcanza un mínimo de visitas, este último nos ahorra espacio en memoria. Además de esto se puede decidir si añadir todos los nodos hijos posibles o un sólo nodo hijo.
  3. Simulación: se simula el juego a partir del nodo hijo alcanzado hasta finalizar la partida. Aquí el sistema simula las jugadas del oponente. En este paso se pueden elegir movimientos aleatorios o combinar esa aleatoriedad con una función que evalúe la validez de los nodos, escogiendo el más prometedor con cierta probabilidad.
  4. Retropropagación: el resultado de la simulación se propaga partiendo de los nodos hoja hasta el nodo actual actualizando sus valores. Se incrementará el número de visitas y se cambiará su valor por el resultado de la simulación. Se escogerá el nodo más prometedor en función de su valor y número de visitas.

Al ver cómo funciona el algoritmo de Montecarlo nos podemos preguntar que pinta nuestra red neuronal en todo esto. Es sencillo, la red neuronal guiará al algoritmo de Montecarlo en el primer paso eligiendo el mejor nodo y en el segundo paso ella añadiría el hijo que crea mejor en base a su experiencia, en el caso de que escojamos añadir un único hijo. Así mezclamos la aleatoriedad con el aprendizaje de una red neuronal. Un ejemplo de este sistema es el algoritmo que usa AlphaGO, el sistema de IA de Google que juega al Go con muy buenos resultados, quedando el número dos del mundo en el ranking no oficial de Rémi Coulom.

Como se ve en este artículo, una inteligencia artificial cuando aprende jugando contra nosotros no aprende de nuestras emociones, o si estamos nerviosos, tampoco aprende a empatizar… Lo único que hace es aprender a ser un mejor agricultor y escoger las mejores ramas de ese árbol que compone el juego.

 

Este artículo nos lo envía Sara Robisco Cavite @SaraRC83, ingeniera en informática por la Universidad de Alcalá de Henares (Madrid) especializada en Inteligencia Artificial. Entusiasta de la ciencia y del arte, vive siempre aprendiendo.



Por Colaborador Invitado, publicado el 19 octubre, 2016
Categoría(s): Divulgación • Tecnología