Tutorial de Pong en JavaScript II: Una IA más avanzada.

Escrito por el 30 abril, 2013

En el tutorial anterior expliqué cómo programar el juego Pong en JavaScript utilizando vectores, lo que me permitía hacer que la pelota modificara su ángulo de salida según la zona de la pala por donde le pegaba a la pelota. Esto hacía que las partidas fueran mucho más interesantes y divertidas porque la pelota ahora tiene un comportamiento un poco menos predecible.

También le metí una IA mu básica, excesívamente fácil de vencer, donde la pala manejada por la CPU únicamente perseguía la pelota. Lo que vamos a hacer en este tutorial es explicar los fundamentos básicos para programar una primera IA funcional que le complique la vida al jugador.

pong

Aquí teneis un enlace para poder probarlo online, y aquí está el zip con todo el código necesario para descargarlo y jugar en local. Las palas se mueven con W y S para el jugador 1 y los cursores para el jugador 2, siempre que los checkbox correspondientes estén desactivados.

En el HTML sólo he incluído un par de checboxs, así que omitiré mostrarlo por su sencillez. Luego, en la clase principal Pong, los enlazo con getElementById. Además, para tener el código mejor organizado, he creado una clase nueva, Ia.js, que contendrá el objeto con los métodos necesarios para manejar la IA de las palas, que veremos después.

En el constructor de Pong declaro dos atributos nuevos: los checkbox para saber cuándo usar la IA, y una instancia de IA para cada pala. De momento sólo necesitas saber que la clase IA requiere que le pasemos un puntero a la pelota, un puntero a la pala que debe manejar, la altura que tiene el campo de juego, y un número que indicará si la IA de la pala es para el jugador 1 o para el jugador 2. Comentaré el código que no ha cambiado para que se destaque lo nuevo:

function Pong(ia){
    /*this.controles = new Controles();

    this.canvas=document.getElementById("canvas");
    this.canvas.width=800;
    this.canvas.height=500;
    this.canvas.style.backgroundColor="black";

    this.contexto=this.canvas.getContext('2d');

    this.palas=[new Pala(30,this.canvas.height), new Pala(this.canvas.width-30,this.canvas.height)];
    this.pelota=new Pelota(this.canvas.width,this.canvas.height,this);*/


    this.iachk1=document.getElementById("ia1");
    this.iachk2=document.getElementById("ia2");
    this.ia1=new Ia(this.pelota,this.palas[0],this.canvas.height,1);
    this.ia2=new Ia(this.pelota,this.palas[1],this.canvas.height,2);

    /*this.puntuaciones=[0,0];

    this.tiempoTranscurrido=Date.now();
    this.loop();*/

}

El método loop ahora controla si cada checbox está marcado, y utiliza la IA para generar una dirección. Y si no está marcado, utiliza las teclas. Muy básico:

Pong.prototype.loop=function(){
    /*var direccion1=Direccion.QUIETO;
    var direccion2=Direccion.QUIETO;

    var delta=(Date.now() - this.tiempoTranscurrido)/1000;
    this.tiempoTranscurrido=Date.now();*/


    //Movemos las entidades
    if (this.iachk1.checked)
    {
       direccion1=this.ia1.direccion();
    }
    else
    {
        if (this.controles.W && !this.controles.S)
        {
            direccion1=Direccion.ARRIBA;
           
        }
        else if(!this.controles.W && this.controles.S)
        {
            direccion1=Direccion.ABAJO;
        }
    }
    if (this.iachk2.checked)
    {
       direccion2=this.ia2.direccion();
    }
    else
    {
        if (this.controles.ARRIBA && !this.controles.ABAJO)
        {
            direccion2=Direccion.ARRIBA;
        }
        else if(!this.controles.ARRIBA && this.controles.ABAJO)
        {
            direccion2=Direccion.ABAJO;
        }
    }
    /*this.palas[0].mover(delta,direccion1);
    this.palas[1].mover(delta,direccion2);
   
    var quantum=Math.floor(delta/0.005);
    for (var i=0;i<quantum;i++)
    {
        this.pelota.mover(0.005);
    }
    quantum=delta-quantum*0.005;
    this.pelota.mover(quantum);

    //Dibjuamos las entidades
    this.contexto.clearRect(0,0,this.canvas.width,this.canvas.height);
    this.dibujarMundo();

    this.palas[0].dibujar(this.contexto);
    this.palas[1].dibujar(this.contexto);
    this.pelota.dibujar(this.contexto);

    var angulo=this.pelota.vector.getAnguloRelativo();

    log("Velocidad: " +this.pelota.velocidad + " // Angulo: " + angulo);

    var self=this;
    requestAnimationFrame(function(){ self.loop(); });*/

}

Otro cambio pequeño que he tenido que hacer es el saque de la pelota. Si sacaba paralelo al eje X como antes con dos palas manejadas por la IA, no se moverán. La pelota chocaría con sus centros, por lo que su ángulo de salida nunca cambiaría y por consiguiente las palas tampoco se moverían. Y la partida nunca acabaría, la pelota simplemente iría de lado a lado de la pista paralelamente al eje X. Para evitarlo, en la dirección del saque inicial hay que meterle un poco de componente Y para que ya no sea paralelo al eje X y obligue a las palas a moverse.

Recordad que antes de escalar el vector, éste debe estar normalizado.

Pelota.prototype.sacar=function(direccion){
    /*this.pos=this.posIni.clonar();
    this.velocidad=this.velocidadIni;*/

    this.vector=new Vector2D(direccion,0.1).normalizar().escalar(this.velocidad);
};

Y por fin, pasemos a ver la nueva clase IA que contendrá todos los métodos y atributos necesarios para conseguir que ganar a la CPU suponga realmente un reto para el jugador. De hecho os pegará una paliza una y otra vez a la mayoría de vosotros.

Una introducción a la inteligencia artificial

Pero antes, pensemos qué tiene que hacer la IA. Una forma de resolver el problema antes de escribir una sola línea de código es ser capaces de responder estas cuatro preguntas:

  • ¿Qué objetivo tiene que conseguir nuestra IA?
  • ¿Cuál es la mejor estrategia a la hora de jugar al Pong?
  • ¿Qué atributos del “mundo” necesita nuestra IA para conseguir resultados con nuestra estrategia?
  • ¿Cuál es el algoritmo más óptimo para conseguir esos resultados?

Crear inteligencias artificiales no es nada sencillo. Muchas veces, los algoritmos más complicados suelen pertenecer a las IAs de los juegos. El tamaño y complejidad del algoritmo suele crecer exponencialmente cuanto mayor “calidad y eficiencia” queremos en sus resultados.

Pero para nuestra primera IA decente, no vamos a descubrir la cuadratura del círculo. Nuestro algoritmo, con una buena idea feliz, será más que suficiente para vencer a cualquier jugador novato sin despeinarse. Ésta es la IA que he pensado yo:

  • ¿Qué objetivo tiene que conseguir nuestra IA?

En cada vuelta del ciclo principal, nuestra IA debe proporcionar una dirección de entre tres opciones: Direccion.ARRIBA, Direccion.ABAJO, Direccion.QUIETO. Sólo eso.

  • ¿Cuál es la mejor estrategia a la hora de jugar al Pong?

Tras echar una partidas con un amigo, he visto que una buena estrategia ganadora es seguir dos pasos: Cuando la pelota está yendo hacia mi rival, lo mejor que puedo hacer es colocarme en el centro de la pista, como los tenistas. Y cuando la pelota viene hacia mí, lo mejor es prever dónde estará la pelota cuando llegue a mi pala.

Además, también podríamos elegir con qué zona de la pala pegarle a la pelota teniendo en cuenta la posición de la pala del rival, complicándole mucho la vida. Tras probar el juego un par de veces, he optado por no implementar esta idea, porque la dificultad de vencer la IA con sólo el punto anterior ya era sobradamente elevada.

  • ¿Qué atributos del “mundo” necesita nuestra IA para conseguir resultados con nuestra estrategia?

En principio sólo necesito saber las posición, tamaño y ángulo de la pelota, la posición y anchura de la pala, y la altura que tiene el tablero para calcular los posibles rebotes. También necesito saber para qué jugador es la IA, para saber si la pelota se acerca o se aleja, para poder elegir la estrategia a seguir.

  • ¿Cuál es el algoritmo más óptimo para conseguir esos resultados?

Aquí está la madre del cordero. Hay un montón de algoritmos para calcular IA’s complejas. Por ejemplo, se me ocurren: Backtracking para calcular el movimiento del caballo por un tablero de ajedrez saltando a todas las casillas. Algoritmo A* para buscar rápidamente rutas en grafos (por ejemplo, mapas de tiles). Algoritmo MiniMax para juegos de tablero por turnos como el 3 en raya. Ramificación y poda para una IA de ajedrez. Programación dinámica para el juego Reverse. Programación voraz para juegos de estrategia. Etcétera. Todas ellas técnicas más o menos complejas. Quizás escriba sobre alguna de ellas en algún futuro tutorial.

Para el pong no llegaremos tan lejos. Lo más complicado es programar un algoritmo capaz de prever la posición de la pelota según una posición inicial, un ángulo de salida, y la altura del mapa para calcular posibles rebotes. ¿Cómo hacemos ésto? Programar no es escribir código como un poseso, es pensar cómo resolver problemas usando código, que no es lo mismo. Si de verdad quieres aprender algo en este tutorial, tómate unos minutos para hallar la solución por tu cuenta. Y cuando termines, la comparas con la que yo opté. Si es diferente a la mía, os animo a que escribáis un comentario con vuestro código. Es bonito conocer diferentes puntos de vista.

Deja de leer YA y ponte a ello.

foto-pensar2

La idea feliz

Estoy seguro que no me has hecho ni puto caso, pero bueno, veámos cómo lo resolví yo: Tuve una idea feliz. ¿Qué es una idea feliz? Pues mira, te voy a explicar con una anécdota, lo que es una idea feliz. Y para más cachondeo, dicha anécdota TAMBIÉN resuelve el problema del Pong. Dos pájaros de un tiro.

En alguna cena informal entre amigos, se encontraba John Von Neumann, probablemente la mayor mente matemática del siglo XX, inventor entre otras muchas cosas de la teoría de juegos y de la arquitectura moderna de los ordenadores (hace 70 años, un visionario). Entre lingotazo y lingotazo, se propusieron problemas de ingenio para matar el tiempo; el que nos interesa tiene este enunciado:

Dos trenes separados por 200 kilómetros se mueven el uno hacia el otro por la misma vía. La velocidad de ambos trenes es de 50 kmh. En el momento inicial, una mosca situada en el morro de uno de los trenes comienza a volar hacia el otro, en viajes de ida y vuelta, a una velocidad de 75 kmh. Lo hace repetidamente hasta que ambos trenes chocan entre si matando a la mosca. ¿Qué distancia ha recorrido volando el insecto?

Inmediatamente, Von Neumann respondió: ¡150 kilómetros!, por lo que el autor de la pregunta se sintió algo decepcionado. ¡Usted sabía el truco!, le acusó el amigo. y Von Neumann respondió ¿Qué truco? ¡Lo único que hice fue sumar mentalmente la serie infinita!.

¿Cómo resolvió Von Neumann el problema? Pues como él dijo, sumando una serie (matemática) infinita, es decir, calculó la distancia de cada viaje de la mosca y luego las sumó, creando y resolviendo mentalmente en un segundo una serie infinita que la mayoría de vosotros no sería ni capaz de hacer en una semana y sin ayuda con lápiz y papel.

Pero… ¿Cuál es el truco al que se refería su amigo? Pues ni más ni menos, eso es la idea feliz, es decir, una forma sencilla de resolver un problema aparentemente complicadísimo.

¿Y cuál es la idea feliz para resolver el problema de los trenes y la mosca?

Pues bien, los trenes están separados por 200 km, y cada uno viaja a 50 kmh, es trivial calcular que el choque se producirá en 2 horas. Como sabemos que la mosca volaba a 75 kmh, durante esas dos horas, recorrió 150 kilómetros. Un niño de primaria podría haber resuelto el problema.

Esta misma idea feliz me ha servido como idea feliz para calcular los rebotes del pong. ¿Se te ocurre ya cómo? Si aún no la tienes, tómate otro momento para reflexionar sobre lo divino y lo humano.

mono-pensando-217x300

La clase IA

El constructor recoge los punteros a la pelota y a la pala, y también a la altura que tiene el mundo (como altura siempre me referiré al tamaño con respecto al eje Y), y un 1 o un 2 que indica el jugador que representa la IA.

function Ia(pelota,pala,alto,jugador){
    this.pelota=pelota;
    this.pala=pala;
    this.alto=alto;
    this.jugador=jugador;

    this.prediccion=null;
}

La idea que vamos a llevar a cabo ya la expliqué antes. Ahora voy a detallarla un poco más.

Primero comprobamos si la pelota se acerca o se aleja de la pala. Sabiendo si mi pala es la del jugador 1 o la del jugador 2, puedo saber si la pelota se acerca o se aleja mediante el componente X de su vector. Si el componente es positivo, y mi pala es la del jugador 1, o el jugador es el 2, y el componente X es negativo, la pelota se aleja. En otro caso, la pelota se acerca.

Si la pelota se aleja, mi mejor movimiento es irme al centro de la pista. Asi que meto en la variable local ideal, la coordenada Y hacia donde quiero mover la pala. Si la pelota se acerca, ejecuto mi método para prever la posición final de la pelota, que veremos después. Dicho método no devuelve valores, lo que hace es llenar un atributo, prediccion, con la posición Y estimada. ¿Por qué lo hago así? Porque me basta con prever la posición final de la pelota una sola vez, en cuanto mi rival le pegue a la pelota y ésta cambie el signo del componente X de su dirección. Una vez que la pelota venga hacia mi pala, no es necesario calcular los rebotes en cada paso, SIEMPRE debería de dar el mismo resultado, si el algoritmo está bien hecho.

Para ello he usado el atributo prediccion. Si el método calcularRebotes ve que prediccion ya tiene un valor, no hará nada. Y si es un null, entonces ejecutará el algoritmo que resuelve el problema. Este atributo estará a null cuando la pelota se aleja, y la primera vez que se detecte que la pelota se acerca, contendrá la posición Y final estimada.

Ia.prototype.direccion=function(){
    var ideal;
    if (this.jugador==1 && this.pelota.vector.x>0 || this.jugador==2 && this.pelota.vector.x<0)
    {
        ideal=this.alto/2;
        this.prediccion=null;
    }
    else
    {
        this.calcularRebotes();
        ideal=this.prediccion;
    }

Una vez obtenemos la posición ideal a la que la pala debe ir, con una sencilla comprobación sabremos si nos tenemos que mover hacia arriba, hacia abajo, o nos basta con permanecer quietos. Si sólo comparara el centro de la pala y la posición ideal, la pala “temblaría” cuando la pala alcanzara dicha posición. El tembleque queda muy feo, así que para evitarlo, incluiré que si la posición ideal está dentro del rango que ocupa la pala, no se mueva. El rango de la pala podría ser el completo, de punta a punta, pero entonces la IA casi siempre le pegaría a la pelota con una de los bordes. He preferido usar la mitad central de la altura de la pala, asi que la IA intentará pegarle más a menudo con el centro.

    if (ideal-this.pelota.lado/2 < this.pala.pos.y-this.pala.alto/4)
    {
        return Direccion.ARRIBA;
    }
    if (ideal+this.pelota.lado/2 > this.pala.pos.y+this.pala.alto/4)
    {
        return Direccion.ABAJO;
    }
    return Direccion.QUIETO;
};

Y por fin, el algoritmo que calcula la trayectoria de la pelota por el mapa. ¿Cuál es la idea feliz que tuve? Pues el secreto está en el problema de la mosca y el tren. Hago prácticamente lo mismo, aunque adaptado a mi “mundo”.

¿Cuanto tiempo tardará la pelota en alcanzar la coordenada X de la pala? Pues si tengo la posición de la pelota, y la posición de la pala, y la velocidad a la que se mueve la pelota, es trivial calcular el número de segundos. Distancia partido por velocidad es igual a tiempo, es una fórmula de 1º de la ESO, o como diablos se llame ahora. ¿Cuál es la distancia en el eje X entre la pelota y la pala? Pues el valor absoluto de la resta de sus respectivos componentes X. ¿Cuál es la velocidad de la pelota? Si recuerdas el tutorial anterior, tenemos un vector donde se almacenaba la dirección y velocidad de la pelota. El componente X de dicho vector es el que necesitamos para saber la velocidad en el eje X con la que cruzará de lado a lado el mapa.

Bien, ya tengo el tiempo que tardará la pelota en llegar a alguna posición Y de la misma coordenada X donde está la pala. ¿Cómo obtengo esa posición Y? Pues también sé a qué velocidad se mueve la pelota en el eje Y, así que multiplico esa velocidad por el tiempo que tardará la pelota en llegar a la zona de la pala, que calculamos antes. Y así obtengo la cantidad de movimiento en píxeles que realizará la pelota en el eje Y.

Ahora tengo dos datos que me interesan: La posición Y de la pelota, y la cantidad de movimiento que realizará en el eje Y. Si sumo ambas, en la variable local y, obtengo donde estará la pelota en el futuro, aunque sin tener en cuenta los rebotes con el “mundo”. Es importante notar que ahora sólo me preocupa el eje Y. Es decir, me basta con imaginar que la pelota sólo se moverá paralelamente al eje Y, totalmente hacia arriba o totalmente hacia abajo. El desplazamiento en X no nos sirve de nada.

Seguro que hay una forma más inmediata de calcular rebotes, pero lo que yo he hecho es obtener una cota inferior y una cota superior del rango donde la pelota se puede mover. El mundo empieza en cero, pero la pelota tiene un tamaño de lado que hay que tener en cuenta. Asi que la cota inferior es la mitad de su lado (recordad que la pelota es un cuadrado). La cota superior es en ancho del mundo menos la mitad del lado de la pelota. Sabiendo las cotas, con un bucle WHILE compruebo si la variable y está dentro del rango. Si lo está, el bucle termina de ejecutarse y esa posición y es la ideal para el movimiento de la pala. Y si no lo está, entonces compruebo por qué cota se ha salido, y actualizo la variable local y en consecuencia.

Coge un papel y lápiz y dibuja un par de situaciones para facilitar el cálculo. Imagina que el mundo mide 100 píxeles de altura, y que la pelota mide 20 píxeles. La pelota está en la posición Y 50, y se mueve hacia arriba 60 píxeles. Es decir, la pelota estará en -10 píxeles, que está fuera del rango válido (que sería entre 10 y 90). Asi que rebotará con la cota inferior. ¿Cómo calculo el rebote? Pues si la cota inferior es 10, y estoy en -10, me he salido del rango en 20 píxeles. Asi que esos 20 píxeles son los que rebotarán con la cota inferior, por lo que se los sumo, con lo que la posición final será de 30. Si te estrujas el cerebro, al final te darás cuenta de que la formulilla es inferior-y+inferior, o lo que es lo mismo, inferior*2-y.

Para la cota superior, siguiendo el mismo razonamiento, no te debería costar obtener la formulilla. Y si no eres capaz, plantéate cambiar de hobby y ponte a hacer encaje de bolillos o punto de cruz.

Es posible que la pelota rebote más de una vez, he ahí la necesidad de usar el bucle while. Y por fin, os presento la sucesión de caracteres ascii que simbolizan un procedimiento algebraico de Boole que produce un resultado válido. Oséase, el código:

Ia.prototype.calcularRebotes=function(){
    if (this.prediccion!=null) return;
    var tiempo=Math.abs((this.pala.pos.x-this.pelota.pos.x)/this.pelota.vector.x);
    var y=this.pelota.vector.y*tiempo+this.pelota.pos.y;
    var inferior=this.pelota.lado;
    var superior=this.alto-this.pelota.lado;
    while(y<inferior || y>superior)
    {
        if (y<inferior)
        {
            y=inferior*2-y;
        }
        else
        {
            y=superior*2-y;
        }
    }
    this.prediccion=y;
}

Y con ésto, ya está tó el pescao vendío.

Nota final

Para que no sea tan difícil jugar contra la máquina, se podría haber programado una IA que adaptara su dificultad según la puntuación de la partida. Por ejemplo, si la pala con IA va ganando, en vez de calcular la posición justo cuando la pelota empiece a venir hacia la pala, que lo haga cuando la pelota ha cruzado el medio campo. Así la pala reaccionaría mas tarde, y sería más fácil meterle algún gol para empatar la partida. O mejor aún, hacerlo gradualmente según la cantidad de goles de diferencia. Por ejemplo, partir la anchura del campo en 7 trozos, y usar la posición X de cada trozo como zona donde la IA reaccionará según la diferencia de goles que haya en la partida.

O también podemos jugar metiendo un error aleatorio en la posición Y calculada. En la última línea del método calcularPosición, por ejemplo:

var margenError=Math.max(0,puntuacion.jugador.ia - puntuacion.del.otro.jugador)*(Math.random()*2-1)*(this.alto/100);
this.prediccion=y+margenError;

Así conforme la IA vaya ganando por muchos goles, el margen de error máximo va creciendo y al final el rival podrá marcar algún gol. Cada gol de diferencia es un 1% más de margen de error máximo con respecto a la altura del mundo. Ese porcentaje se puede incrementar al 2% (dividiendo entre 50 en vez de 100), al 4% (25), etc, según la velocidad con la que quieras empeorar la estimación de la IA.

Incluso se pueden combinar ambas ideas.

Y aunque me joroba mucho no haber llegado a mis 5000 palabras habituales, a pesar de haber metido de estrangis toda la paja posible entre concepto y concepto, aquí termina este primer tutorial centrado única y exclusívamente en la programación de una IA decente con ideas aprovechables (convenientemente adaptadas) para usar en un porrón de minijuegos donde se necesite una estimación de posición.

Nos veremos en el próximo tutorial dentro de ¿un día?¿Un mes?¿Un año? Quién sabe. Lo bonito es la emoción de la espera.

Volver al índice

Etiquetas: , ,

Comentarios (5)

  • Me encanta compañero, la IA está muy currada, siempre he tenido pegas en ese tema, ahora me mirare el código más lentamente, pero en sí está muy bien explicado.

    Pd: El enlace para bajar el zip está caido, ojalá pudieras resubirlo, está el código del pong muy bien.

    Saludos! 🙂

  • Amigo excelente el tutorial me ha sido de gran ayuda, sin embargo tengo una pregunta, quiero redondear el borde de las palas para que tengan forma de cápsulas, intenté con la función lineJoin de Javascript pero no logro hacer que se dibujen los bordes, si puedes enviarme o publicar algún material que me apoye en la tarea te lo agradeceré… Por lo demás, sigue así…

  • Muy buen tutorial, solo le agregaria un metodo para pausar el juego, y claro otro para reiniciar, he tratado pero no logro reiniciar el juego.

    Logro generar un stop con la sig intruccion

    window.requestAnimationFrame = (function(){
    return false;
    })();

  • Para hacer que las palas tengan forma de cápsulas, sería utilizar utilizar otras instrucciones de dibujo gráfico para dibujar las esquinas redondas, en vez de utilizar el fillRect que sirve para rellenar rectángulos.

    Por ejemplo, en éste enlace http://js-bits.blogspot.com.es/2010/07/canvas-rounded-corner-rectangles.html salen varios ejemplos de cómo hacerlo.

    Para pausar el juego, basta con poner un IF con alguna condición al final del bucle principal del juego LOOP para evitar que se ejecute el requestAnimationFrame. Para reactivarlo, pues otro código que se dispara por ejemplo al presionar alguna tecla que ejecute el requestAnimationFrame llamando a la función LOOP del juego.
    El requestAnimationFrame funciona igual que el setTimeout, pero mejorado, no confundirlo con el setInterval.

  • Puede que haga mucho que se escribió esta entrada, pero aun así quiero dejar mi agradecimiento al creador de la misma. Estoy haciendo una inteligencia artificial para Pong en Unity y tenía el problema del tembleque, había llegado a saber cómo calcular todo lo demás por mí mismo, pero no tenía ni idea de como solucionar el temblor. Me ha servido de mucho esta información, así que mil gracias y un gran saludo.

¿Tienes algo que decir?

Gestionado con Wordpress y Stripes Theme Entradas (RSS) | Comentarios (RSS)