Tutorial de algoritmos en javascript, minimax: Tres en raya

Escrito por el 26 Septiembre, 2013

Tras un largo periodo vacacional, aquí estamos de nuevo para explicar un nuevo tipo de algoritmo básico que nos ayudará con la IA de cierto tipo de juegos: Algoritmo minimax.

El juego donde vamos a usar este tipo de algoritmo será el tres en raya, también conocido como tres en línea, o tic tac toe en la pérfida Albión. El juego se juega típicamente con bolígrafo y papel, y consiste en rellenar tres celdas consecutivas de un tablero de 3 x 3 formando una línea vertical, horizontal o diagonal. Se juega por turnos, y normalmente se usan los símbolos “X” para el primer jugador y “O” para el segundo.

13915155-tic-tac-toe-simbolo

Para probar el juego, pincha aquí. Está hecho en HTML4 para representar el tablero y por supuesto javascript. No debería tener ningún problema en ejecutarse en cualquier tipo de máquina

Algoritmo Minimax

El algoritmo minimax se puede ver como una especialización de bactracking para juegos por turnos de dos jugadores. Ninguna de estas palabras sobra, Minimax está pensado para juegos por turnos de dos jugadores, y nada más. Minimax sirve para que la IA elija el siguiente movimiento a realizar suponiendo que el otro jugador siempre escogerá el movimiento que más perjudique a la IA.

¿Y cómo funciona el chiringuito? Pues bien, al igual que backtracking, consiste en recorrer todo el árbol de soluciones del juego a partir de un estado dado, es decir, según las casillas que ya han sido rellenadas. Por tanto, minimax se ejecutará cada vez que le toque mover a la IA (aunque ciertas versiones de minimax almacenan en estructuras de datos internas el árbol de soluciones generado la primera vez, el cual ya contiene, siempre que no se haya realizado alguna poda, todas las posibles jugadas que debe realizar la IA).

A continuación, éstos son los pasos típicos del algoritmo minimax. Al igual que bactracking, minimax es una IDEA, la implementación tiene muchas formas diferentes:

  1. Generar el árbol de soluciones completo a partir de un nodo dado. Si la complejidad del juego es bestial, y generar todo el árbol de soluciones es inviable, como por ejemplo en el ajedrez, se puede limitar la generación del árbol hasta cierto nivel de profundidad pasado al algoritmo como parámetro. Para el tres en raya, que tiene un árbol de soluciones pequeño, no es necesario.
  2. Para cada nodo hoja, es decir, un nodo sin hijos que es un estado terminal del juego (por ejemplo en el tres en raya, no quedan casillas libres o ha ganado alguno de los jugadores), le asignamos un valor numérico que describe si le interesa a la IA alcanzar o no ese nodo hoja. En nuestra implementación usaremos un 0 para las partidas que terminen en empate, un 1 para las que gane la IA y un -1 para las que gane el jugador humano. En otro tipo de juegos más complejos se puede usar un rango numérico mayor; por ejemplo en el dominó, se suele utilizar el número de puntos de las fichas que te comes (en negativo) o el número de puntos de fichas que se le endosan al rival (en positivo).
  3. Y lo que hará el algoritmo minimax cuando vaya regresando hacia atrás como hacía backtracking, será comunicarle a la llamada recursiva superior cuál es el mejor nodo hoja alcanzado hasta el momento. Cada llamada recursiva tiene que saber a quién le toca jugar, para analizar si el movimiento realizado pertenece a la IA o al otro jugador, ya que cuando sea el turno de la IA nos interesa MAXIMIZAR el resultado, y cuando sea el turno del rival MINIMIZAR su resultado. La forma más fácil de implementar el algoritmo es crear dos funciones, MIN y MAX que se irán llamadas recursívamente la una a la otra para simular el juego por turnos. La del MIN típicamente simulará el movimiento del otro jugador, y la de MAX simulará el movimiento de la IA. Ambas funciones auxiliares se pueden fusionar en una, pero en esta aproximación he preferido dejarlas separadas para que se vea más claro el funcionamiento de este algoritmo. De estas funciones MIN y MAX viene el nombre del algoritmo.

Lo importante de este asunto es que hayas entendido la idea; la implementación básica es más simple de lo que pueda parecer.

Preparando el HTML para el tres en raya

Antes de empezar con la programación de la lógica del juego, tenemos que representar el tablero de alguna forma. La más sencilla es usar HTML y CSS para crear, posicionar y dibujar las celdas. No tiene ninguna complicación, y aquí está el código:

<html>
<head>
    <meta charset="UTF-8">
    <title>Tres en raya</title>
</head>
<style>
    body { background-color:orange;}
    h1 {text-align:center;}
    div#tablero{width:310px;height:310px; padding:0px; border: 7px solid #999; background-color:white; margin: 20px auto; cursor:pointer;}
    div#tablero div{width:100px;height:100px;float:left; margin:0px; font-size: 90px; text-align:center;}
    div#celda1,div#celda2,div#celda3,div#celda4,div#celda5,div#celda6 {border-bottom: 5px solid black;}
    div#celda1,div#celda2,div#celda4,div#celda5,div#celda7,div#celda8 {border-right: 5px solid black;}
    div#tablero > div:hover {background-color:#ddd;}
    div#consola {width:310px;height:30px; padding:7px; border: 5px solid #999; background-color:white; margin: 10px auto; text-align:center; color:darkgreen;}
</style>
<script>
    //Todo el código
</script>
<body>
    <h1>Tres En Raya</h1>
    <div id="tablero">
        <div id="celda1" celda="0" class="celda"></div>
        <div id="celda2" celda="1" class="celda"></div>
        <div id="celda3" celda="2" class="celda"></div>
        <div id="celda4" celda="3" class="celda"></div>
        <div id="celda5" celda="4" class="celda"></div>
        <div id="celda6" celda="5" class="celda"></div>
        <div id="celda7" celda="6" class="celda"></div>
        <div id="celda8" celda="7" class="celda"></div>
        <div id="celda9" celda="8" class="celda"></div>
    </div>
    <div id="consola"></div>
</body>
</html>

Lo único interesante de ésto es que a cada DIV que representa las celdas le he metido un atributo personalizado llamado “celda” que me servirá para saber qué celda he pinchado con el ratón, ya que usaré el evento “click” sobre cada celda para realizar los movimientos del jugador y poner en marcha al sistema.

Antes de comenzar con el código, describiré someramente el funcionamiento interno del juego. No hay tiempo delta ni intervalos, ya que aprovecharé los eventos de ratón para realizar todos los cálculos necesarios. Por ejemplo, cuando el jugador humano pinche sobre una casilla del juego, aprovecharé ese evento click para comprobar si la casilla está vacía, en cuyo caso marcaré la casilla elegida por el jugador en la lógica interna del juego usando el atributo que dije antes “celda”, y comprobaré si el jugador ha ganado la partida. Si no ha ganado, entonces haré que mueva la IA, tras lo cual comprobaré de nuevo si es la IA la que ha ganado la partida. Si nadie ha ganado, y quedan casillas vacías, entonces no haré nada más, y el juego sólo continuará cuando el jugador vuelva a pinchar en otra celda, con lo que se pondrá en marcha otra vez el mismo sistema.

El tablero de juego

En el tutorial de bactracking recursivo no me hizo falta, pero para el tres en raya me facilita mucho la vida usar programación orientada a objetos, para tener claramente diferenciado y separado el código con la lógica del juego, y el código de la representación del tablero de juego.

Para empezar, he creado un par de enumeradores que facilitarán la lectura del código. Un numerador me servirá para representar a los jugadores allí donde lo necesite, y el otro almacenará el estado en el que se encuentra el juego. Los estados pueden ser “jugando”, que quiere decir que se está esperando a que el jugador humano pinche en alguna celda; “esperando”, que quiere decir que es la IA la que está calculando su próximo movimiento (aunque lo hará tan rápido que es posible que su movimiento sea instantáneo), y “terminado”, que como su propio nombre indica, el juego ha terminado. Este estado me servirá para resetear el tablero y comenzar una nueva partida cuando el jugador pinche en cualquier celda.

    var JUGADOR = { HUMANO:1, CPU:2 };
    var ESTADO = { JUGANDO: 0, ESPERANDO: 1, TERMINADO:2 };

A continuación, la definición y constructor de la clase Tablero:

    function Tablero(){
        this.panel=[];

        this.celdas=[];
        for (var i=0;i<9;i++)
        {
            this.celdas[i]=document.getElementById("celda"+(i+1));
        }
    }

El atributo panel contendrá un array de 9 enteros, uno por casilla, que contendrá un cero si la casilla está vacía, un 1 si la casilla está marcada por el jugador humano, y un 2 si la casilla está marcada por la CPU. Usaremos el enumerador JUGADOR descrito antes para meterle valores a este array.

En cuanto al atributo celdas, contendrá punteros a los elementos de HTML DIV que corresponden a cada casilla, necesarios para dibujar el tablero cada vez que lo necesitemos.

    Tablero.prototype.reset=function(){
        this.panel=[0,0,0,0,0,0,0,0,0];
    };

Resetear el tablero sólo requiere poner todos los valores del array a cero.

    Tablero.prototype.marcable=function(posicion){
        return (this.panel[posicion]==0);
    };

Necesitaremos un método para comprobar si una casilla concreta está vacía. Las casillas están numeradas de 0 a 9, por filas de izquierda a derecha y de arriba a abajo.

    Tablero.prototype.marcar=function(turno,posicion){
        this.panel[posicion]=turno;
    };

Por supuesto, necesitamos otro método para marcar una casilla con un valor dados, que corresponderán al jugador que le toque en ese turno.

    Tablero.prototype.esGanador=function(jugador){
        //HORIZONTAL
        var bool=(this.panel[0] == jugador && this.panel[1] == jugador && this.panel[2]==jugador);
        bool=bool || (this.panel[3] == jugador && this.panel[4] == jugador && this.panel[5]==jugador);
        bool=bool || (this.panel[6] == jugador && this.panel[7] == jugador && this.panel[8]==jugador);
        //VERTical
        bool=bool || (this.panel[0] == jugador && this.panel[3] == jugador && this.panel[6]==jugador);
        bool=bool || (this.panel[1] == jugador && this.panel[4] == jugador && this.panel[7]==jugador);
        bool=bool || (this.panel[2] == jugador && this.panel[5] == jugador && this.panel[8]==jugador);
        //DIAGONAl
        bool=bool || (this.panel[0] == jugador && this.panel[4] == jugador && this.panel[8]==jugador);
        bool=bool || (this.panel[2] == jugador && this.panel[4] == jugador && this.panel[6]==jugador);
        return bool;
    };

Este método comprobará si un jugador dado ha ganado la partida. Para ello hacemos la búsqueda a lo bruto, línea a línea; no me he calentado la cabeza en absoluto.

    Tablero.prototype.celdasVacias=function(){
        var n=this.panel.length;
        for (var i=0;i<n;i++)
        {
            if (this.panel[i]==0)
            {
                return true;
            }
        }
        return false;
    };

También necesitaremos un método que compruebe si quedan o no casillas vacías, para saber si el juego puede continuar. Si no se puede, es que el juego se ha terminado con un empate.

    Tablero.prototype.dibujar=function(){
        var n=this.panel.length;
        for (var i=0;i<n;i++)
        {
            if (this.panel[i]==0)
            {
                this.celdas[i].innerHTML='';
            }
            else
            {
                this.celdas[i].innerHTML='<span style="color:'+((this.panel[i]==JUGADOR.HUMANO)?'red':'blue')+';">'+((this.panel[i]==JUGADOR.HUMANO)?'X':'O')+'</span>';
            }
        }
    };

Y por supuesto, un método que dibuje en pantalla el tablero, usando los elementos HTML DIV cacheados en el constructor almacenados en el array celdas. Como vamos a dibujarlos en elementos HTML, para darle color he usado un SPAN y el atributo de CSS color. Todo es muy sencillo.

Creo que ya lo he dicho alguna que otra vez, pero nunca está de más repetirlo por si algún novato está leyendo este tutorial.

Este código:

this.celdas[i].innerHTML='<span style="color:'+((this.panel[i]==JUGADOR.HUMANO)?'red':'blue')+';">'+((this.panel[i]==JUGADOR.HUMANO)?'X':'O')+'</span>';

Corresponde a:

if (this.panel[i]==JUGADOR.HUMANO)
{
this.celdas[i].innerHTML='<span style="color:red;">X</span>';
}
else
{
this.celdas[i].innerHTML='<span style="color:blue;">O</span>';
}

Pero la primera forma es mucho más breve y concisa. Se llama operador ternario y funciona en casi todos los lenguajes de programación.

La lógica del juego

A estas alturas del blog, el código del tres en raya (a escepción del algoritmo minimax, si no lo conoces) no debe suponerte ningún problema, asi que pasaré otra vez a velocidad de crucero por todos sus atributos y funciones para llegar a lo verdaderamente interesante, la IA con minimax.

    function Juego(){
        this.partidas=0;
        this.tablero=new Tablero();
        this.estado=null;
        this.consola=document.getElementById("consola");

        this.reset();
    }
    Juego.prototype.reset=function(){
        this.tablero.reset();
        if (this.partidas%2==1)
        {
            this.estado=ESTADO.ESPERANDO;
            this.mostrarMensaje("Turno del jugador 2","blue");
            this.tablero.marcar(JUGADOR.CPU,Math.floor(Math.random() * 9));
        }
        this.partidas++;
        this.estado=ESTADO.JUGANDO;
        this.mostrarMensaje("Turno del jugador 1","red");
        this.tablero.dibujar();
    };
    Juego.prototype.mostrarMensaje=function(mensaje,color){
        this.consola.innerHTML='<span style="color:'+color+';">'+mensaje+'</span>';
    };

Para manejar la lógica del juego, he creado una nueva clase llamada Juego. El juego sólo tiene cuatro atributos, uno contiene el tablero, otro el estado en el que se encuentra la partida, el tercero es un puntero a un elemento HTML DIV donde escribir mensajes, y el último es un contador de las partidas disputadas, que me servirá para que en las partidas pares, empiece jugando el jugador humanos, y en las impares, la CPU. Esto se ve claramente en el método reset, que reseteará el tablero, y si la partida es impar, hará que mueva la CPU en primer lugar. Y si no lo es, o si ya ha movido la CPU, pondrá el estado del juego al que debe. Por último dibujará el tablero.

Notar que para el primer movimiento de la CPU no he usado minimax, porque siempre eligiría la misma casilla. Para animar un poco la cosa, el primer movimiento de la CPU lo he puesto por puro azar. En realidad la CPU en el peor de los casos, siempre empatará la partida. La victoria sólo es posible cuando el otro jugador la caga; no existe ninguna estrategia ganadora infalible, como bien sabía la computadora de juegos de guerra.

Para sacar un poco de información por pantalla, he creado el método mostrarMensaje, que escribirá en un DIV preparado para ello mensajes informativos acerca del estado del juego (a quién le toca, o quién ha ganado la partida), el cual ya he usado en reset para decir a quién le toca jugar.

    Juego.prototype.logica=function(posicion){
        if (this.estado==ESTADO.JUGANDO)
        {
            if (this.tablero.marcable(posicion))
            {
                this.tablero.marcar(JUGADOR.HUMANO,posicion);

                if (this.tablero.esGanador(JUGADOR.HUMANO))
                {
                    this.estado=ESTADO.TERMINADO;
                    this.mostrarMensaje("¡HAS GANADO!<br/>Click en una celda para comenzar de nuevo.","red");
                }
                else if (!this.tablero.celdasVacias())
                {
                    this.estado=ESTADO.TERMINADO;
                    this.mostrarMensaje("¡EMPATE!<br/>Click en una celda para comenzar de nuevo.","orange");
                }
                else
                {
                    this.estado==ESTADO.ESPERANDO;
                    this.mostrarMensaje("Turno de AI...","blue");
                    this.movimientoAI();

                    if (this.tablero.esGanador(JUGADOR.CPU))
                    {
                        this.estado=ESTADO.TERMINADO;
                        this.mostrarMensaje("¡AI GANA!<br/>Click en una celda para comenzar de nuevo.","blue");
                    }
                    else if (!this.tablero.celdasVacias())
                    {
                        this.estado=ESTADO.TERMINADO;
                        this.mostrarMensaje("¡EMPATE!<br/>Click en una celda para comenzar de nuevo.","orange");
                    }
                    else
                    {
                        this.mostrarMensaje("Turno del jugador 1","red");
                        this.estado==ESTADO.JUGANDO;
                    }
                }
            }
            this.tablero.dibujar();
        }
        else if (this.estado==ESTADO.TERMINADO)
        {
            this.reset();
        }
    };

Este método logica se disparará cuando el jugador pinche en alguna casilla. Primero se comprobará el estado del juego. Si el estado de juego es “esperando”, que es cuando la CPU está calculando su movimiento, no hará nada. Si el estado es “terminado”, se reseteará la partida. Si el estado es “jugando”, entonces es cuando el sistema se pone verdaderamente en marcha.

Para empezar, se comprueba si la casilla etá vacía. Si no lo está, es decir, si ya está marcada, no podemos hacer nada. Si no lo está, entonces la marcamos y comprobamos si el jugador humano ha ganado la partida o no. Si el jugador ha ganado la partida, ponemos el estado a terminado y mostramos un mensaje en pantalla para celebrar la victoria. Si el jugador no ha ganado, y tampoco quedan casillas vacías, es que hemos acabado en empate; terminamos el juego y mostramos otro mensaje. Y si quedan casillas libres, entonces moverá la CPU mediante el método movimientoAI, tras lo cual se volverán a comprobar las condiciones de victoria o empate, pero esta vez sobre el jugador CPU. Por último, se dibujará el tablero en pantalla.

Implementación del algoritmo minimax

Y por fin, empieza lo verdaderamente interesante, que espero que resulte de fácil comprensión.

El algoritmo minimax se encargará de recorrer todo el árbol de soluciones a partir de un estado determinado del tablero (ciertas casillas estarán marcadas con alguno de los símbolos de los jugadores, y otras no). Cuando se alcance un nodo hoja, es decir, un nodo donde la partida ha finalizado, se retornará algún tipo de puntuación a la llamada superior recursiva. Como ya dije al principio. Las posibles finalizaciones de la partida son empate, cuando no quedan casillas vacías y ningún jugador ha ganado. En este caso, se devolverá un 0. Otro nodo hoja puede ser la victoria de alguno de los jugadores. En ese caso, si el jugador victorioso es la CPU devolveremos un 1, y si es el jugador humano, un -1.

Lo que hará el algoritmo minimax, que juega como el jugador CPU, será buscar el nodo hoja con el valor más alto posible, porque lo que le interesa es ganar o al menos empatar la partida.

He aquí la función que pone en marcha el algoritmo:

    Juego.prototype.movimientoAI=function(){
        var posicion=0;
        var n=this.tablero.panel.length;
        var aux, mejor=-9999;

        for (var i=0;i<n;i++)
        {
            if (this.tablero.marcable(i))
            {
                this.tablero.marcar(JUGADOR.CPU,i);
                aux=this.min();
                if (aux>mejor)
                {
                    mejor=aux;
                    posicion=i;
                }
                this.tablero.marcar(0,i);
            }
        }

        this.tablero.marcar(JUGADOR.CPU,posicion);
    };

No es demasiado complicado. Lo único que hacemos es recorrer todas las celdas del tablero, y si no están marcados, las marcamos, y a continuación hacemos la primera llamada recursiva al método MIN del algoritmo minimax. Esta función nos devolverá el valor del nodo hoja mas alto que ha encontrado el algoritmo minimax al ejecutarse partiendo de que la CPU ha marcado esa casilla concreta. Si ese resultado es mejor que el que llevamos almacenado hasta el momento, almacenamos la casilla que habíamos marcado. Por supuesto, antes de probar con otra casilla, hay que desmarcarla porque estamos modificando las casillas del tablero del juego para generar el árbol de soluciones y queremos dejarlo en su estado original.

Hago hincapié en que estamos llamando al método MIN, pues éste algoritmo es el encargado de simular el turno del jugador humano, y lo que nos interesa es minimizar su resultado, es decir, que no gane o por lo menos que empate la partida.

    Juego.prototype.min=function(){
        if (this.tablero.esGanador(JUGADOR.CPU)) return 1;
        if (!this.tablero.celdasVacias()) return 0;
        var n=this.tablero.panel.length;
        var aux,mejor=9999;

        for (var i=0;i<n;i++)
        {
            if (this.tablero.marcable(i))
            {
                this.tablero.marcar(JUGADOR.HUMANO,i);
                aux=this.max();
                if (aux<mejor)
                {
                    mejor=aux;
                }
                this.tablero.marcar(0,i);
            }
        }
        return mejor;
    };

El algoritmo MIN es muy similar. Sabemos que cuando se llame este algoritmo, el último jugador en marcar el tablero fue la CPU, asi que comprobamos si ha ganado o empatado el juego. En esos casos, estaríamos en un nodo hoja, y devolvemos alguno de los valores 1 ó 0 que ya he descrito. Si no es nodo hoja, entonces con un for recorremos las casillas y marcamos la primera que veamos libre, simulando ser el jugador humano, y llamando a continuación al método MAX. Llamamos a MAX porque en el siguiente turno le tocará jugar a la CPU, y nos interesa maximizar su resultado.

¿Y por qué nos quedamos con el valor mínimo? Pues porque estamos simulando el turno del jugador humano, y suponemos que este jugador moverá para GANAR la partida, que es un nodo hoja con el valor -1.

Así pues, notar que el algoritmo minimax supondrá que el rival (en nuestro caso, el jugador humano) siempre hará el mejor movimiento posible, o dicho de otro modo, el movimiento que más nos perjudique (al jugador CPU).

Notar que el último paso del bucle for es desmarcar la casilla marcada en esa vuelta, para dejar el array de casillas tal y como estaba.

    Juego.prototype.max=function(){
        if (this.tablero.esGanador(JUGADOR.HUMANO)) return -1;
        if (!this.tablero.celdasVacias()) return 0;
        var n=this.tablero.panel.length;
        var aux,mejor=-9999;

        for (var i=0;i<n;i++)
        {
            if (this.tablero.marcable(i))
            {
                this.tablero.marcar(JUGADOR.CPU,i);
                aux=this.min();
                if (aux>mejor)
                {
                    mejor=aux;
                }
                this.tablero.marcar(0,i);
            }
        }
        return mejor;
    };

El método MAX es idéntico, salvo que esta vez el último jugador que marcó alguna casilla fue la CPU, asi que comprobamos si ha ganado o empatado la partida. Después recorremos como siempre las casillas del tablero buscando las vacías. Y que esta vez estamos simulando ser la CPU, por lo que buscaremos el nodo hoja con el valor más alto (1, que indica victoria).

Si eres un poco avispado te habrás dado cuenta de que el método movimientoAI y el método MAX son idénticos, pues ambos simulan ser el jugador CPU. Las dos únicas diferencias son que en movimientoAI debe realizar el movimiento escogido final sobre el tablero de juego, una vez todas las llamadas recursivas han terminado de ejecutarse y la línea de ejecución del código ha vuelto a ese método. Y también que en movimientoAI no se comprueba si el jugador humano ha ganado la partida o empatado. Si lo hubiera hecho, el método logica nunca hubiera llamado a movimientoAI.

Y nada más, ya tenemos una inteligencia artificial capaz de vencernos en las tres en raya si te despistas un poco. No serás capaz de ganarle nunca.

Para poner en marcha el juego, como siempre, aprovechamos el evento window.onload:

    window.onload=function(){
        var juego=new Juego();
       
        var celdas= document.getElementsByClassName("celda");
        for (var i = 0; i < celdas.length; i++) {
            celdas[i].onclick=function(e){
                juego.logica(parseInt(this.getAttribute("celda")));
            };
        }

    };

En él creamos una instancia de la clase Juego, y enlazamos el evento click de cada celda del tablero HTML haciendo que llame al método logica de nuestra clase Juego. Para saber qué celda se ha marcado, usamos aquél atributo personalizado “celda” incrustado en cada DIV que representa las celdas; y ya está, fácil, sencillo y para toda la familia.

Poda alfa-beta y profundidad

Cuando el juego es complicado, como un ajedrez, el árbol de soluciones puede llegar a ser inmenso, o incluso infinito, así que ciertos algoritmos minimax tienen un límite de llamadas recursivas. Cuando se alcanza ese límite, y no estemos en un nodo hoja, el algoritmo le dará alguna puntuación al estado actual del juego como si fuera un nodo hoja. Muchas IA’s de ajedrez utilizan ese sistema, y aunque son fáciles de vencer por jugadores curtidos, suelen ser todo un reto para jugadores principiantes. Es evidente que cuanto más profundidad se le de al algoritmo, mejor resultado obtendrá.

La poda alfa-beta también ayuda un poco cuando el arbol de soluciones es demasiado grande. Consiste en podar las ramas del árbol en los cuales estemos seguros de que no se alcanzará un resultado mejor que el que ya tiene el nodo padre. Consiste en pasarle al método minimax una cota mínima ALFA y una cota máxima BETA. Cuando se ejecute el MIN, comprobará si el resultado alcanzado hasta el momento es igual a ALFA, en cuyo caso devolverá ese resultado. En MAX, comparará con BETA.

Por ejemplo, si usáramos la poda ALFA-BETA en nuestro tres en raya, la ALFA sería 1, y la BETA -1. Cuando el algoritmo MIN encontrara un valor de -1, no necesitaría marcar más casillas porque sabemos que es imposible que encuentre un valor mejor. En cuanto al método MAX, su BETA sería 1, asi que en cuanto encontrara dicho valor, no probaría a marcar el resto de casillas vacías que queden.

También existe otra variante, que se basa en reducir los métodos MIN y MAX a uno sólo llamado NEGAMAX, pues básicamente el algoritmo MIN es la negación del MAX y viceversa.

Pero a pesar de todo, el algoritmo minimax cada vez se utiliza menos, en favor de otros algoritmos voraces o de programación dinámica, que buscan soluciones sin tener que recorrer árboles de soluciones al completo, aunque la mayoría de ellos no pueden garantizar encontrar una solución óptima, algo que sí nos garantiza minimax cuando se ejecuta sobre un árbol de soluciones completo sin poda ni mariconadas.

Etiquetas: , , , ,

Enlaces entrantes

Comentarios (15)

  • para cuando algoridmos geneticos 😀

  • Es increible el trabajo que te has currado con este codigo, apenas llevo con html/CSS/Java 2 semanas y me he planteado el reto de hacer yo mismo un 3 en raya pero viendo el tuyo creo que estoy a años luz!, crees que se podria llevar en un lateral un registro de las partidas ganadas/perdidas/empatadas?

  • Yo aprendi con este videotutorial http://www.youtube.com/watch?v=DYC9FXKUkQc

  • ¡Bravísimo!, me ha encantado este tutorial. Gracias por molestarte en hacerlo, te lo agradecemos.
    Cualquier algoritmo de Inteligencia Artificial es de mi interés.
    Me gusta mucho la forma en que puedes programar en Java integrado en HTML.

  • Gracias por el articulo, no único que no me queda claro es que hace esta linea y porque toma ese valor: var aux,mejor=-9999;

  • Pura vida!!! Me ayudo bastante este espacio, llevaba tiempo buscando información sobre esto y no encontraba nada tan bueno como esto

  • Excelente trabajo, me sirve un montón para un tp que estamos haciendo en la materia sistemas inteligentes de caece.
    El nuestro es en prolog, pero el algoritmo es el mismo, va en realidad estamos pensando en utilizar poda lfa beta para el juego de damas estilo checkers. Aun estamos analizando la situación.

    Muchas Gracias

  • Muy excelente la pagina , me ayudo y estuvo cundo mas lo necesitaba 🙂

  • Hola! Te hago una pregunta. ¿Podrías mandarme un zip con el/los archivos que utilizaste? Tengo conocimiento muy básico y no me estaría saliendo crear. Yo estoy copiando y pegando todos los fragmentos del código que pasaste en un documento de Notepad++, y si bien me diseña el tablero, no realiza ninguna función y no detecto dónde estoy fallando.
    Desde ya, muchas gracias!

  • Wow, realmente desconocía sobre este tipo de algoritmos para videojuegos, es increíble la forma en la que se hizo el algoritmo de tal forma que se preveen todos los escenarios posibles de manera que sea la CPU quien pueda tener la ventaja o que evite en toda medida que sea el jugador quien gane. Felicidades por el excelente trabajo!

  • Encontre un error en el algoritmo. SI seleccionan las casillas 0, 8 ,3 el CPU deberia seleccionar la casilla 7, pero no lo hace. Solo hay que agregar — if (this.tablero.esGanador(JUGADOR.CPU)) return; — antes de — aux=this.min(); — de la funcion [movimientoAI] y solucionado.

  • Excelente aporte amigo,

  • EBER JOSE no es un error, asi es como funciona el algoritmo, de igual forma la IA va a ganar haciendo un “fork”, es como si la IA dijera “Igual voy a ganar a si que voy a jugar un rato mas” jajaja.

  • Muy bueno, era lo que estaba buscando para una idea de juego similar….

  • Alguien lo tiene completo que me lo envie? por fvor no me dunciona
    forevercoc2016@gmail.com

¿Tienes algo que decir?

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