El Algoritmo Minimax y Poda Alfa-Beta

1.1.       INTRODUCCIÓN

Como hemos venido mencionado en la anterior publicación sobre búsquedas entre adversarios, existen algoritmos que hacen uso de estrategias optimas que los guien a estados objetivos, entre estos algoritmos tenemos al algoritmo minimax, este algoritmo es fundamental para contrincantes óptimos en problemas de juegos, el cual basa su teoría de las investigaciones de Claude Shannon y Alan Turing en el año de 1950.

Otro algoritmo que se utiliza en este tipo de problemas de búsquedas entre adversarios es el algoritmo Poda Alfa-Beta que es una versión mejorada del algoritmo Minimax que no necesita hacer un recorrido de todos los nodos para poder obtener una decisión óptima.

En esta publicación hablaremos sobre el algoritmo Minimax y el algoritmo Poda Alfa-Beta, sus principales características y que tipo de decisiones optimas utilizan en juegos multi-jugadores.

1.2.       OBJETIVO 

Conocer cómo funcionan los algoritmos entre adversario Minimax y Poda Alfa-Beta y en base a qué factores toman decisiones para problemas con juegos.

2.     MARCO TEÓRICO

2.1.       El Algoritmo Minimax

El algoritmo minimax es una de los algoritmos de las búsquedas de adversarios, cuyo objetivo es minimizar la perdida contra adversarios en juegos, para ello hace uso de un cálculo recurrente de cada uno de sus estados sucesores para elegir el mejor movimiento. Este algoritmo hace uso de búsqueda en profundidad para explorar el conjunto de jugadas posibles es decir explora todo el árbol de juegos.

Entre las principales características que posee este algoritmo tenemos:

·         Facilidad de problemas complejos con reglas simples.

·         Pruebas contra humanos escalables

·         Existencia de un solo ganador

·         Exploración de N capas

·         Tiempo de exploración agotado

·         Situaciones estáticas sin cambios significativos

Este algoritmo principalmente está enfocado en problemas matemáticos de juegos en donde los costos de los tiempos son poco prácticos.

Imagen 1: Algoritmo Minimax

1.1.       Decisiones Optimas en Juegos Multi-Jugador

En la actualidad muchos de los juegos son populares se orientan a más de dos jugadores, lo que intenta el algoritmo minimax es proporcionar una idea de cómo enfocar su estrategia utilizando las funcionalidades del mismo. Para explicar de una mejor manera pondré un ejemplo con tres jugadores en donde cada tendrá asignado un nodo, este para poder obtener el estado terminal tendrá que hacer uso de la función de utilidades la cual nos va a devolver un vector de utilidades, seguido de esto tendremos que analizar los estados no terminales para reconocer los movimientos que nos conducirán hacia un estado terminal con utilidades, se podría decir que el valor hacia atrás de un nodo será el vector de utilidades de cualquier estado sucesor que tiene el valor más alto para cada jugador.

Imagen 2: Ejemplo de juego con tres jugadores

1.1.       El algoritmo Poda Alfa-Beta

El algoritmo poda Alfa-Beta como ya lo habíamos mencionado anteriormente es una técnica mejorada del algoritmo Minimax en la cual es posible calcular un estado objetivo sin la necesidad de recorrer todos los nodos del árbol de juegos, este tipo de algoritmo suele utilizarse para cualquier tipo de árbol de búsqueda en profundidad y para subárboles enteros. Este algoritmo al igual que el Minimax hace uso de la búsqueda en profundidad asi que para poder encontrar un resultado solo tendremos que considerar los nodos a lo largo de un solo camino.

Entre las principales características que posee este algoritmo en comparación con el Minimax tenemos:

·         Omisión de expansión de nodos que por sus valores no pueden ser los mejores.

·         No afecta al resultado final.

·         Permite búsquedas el doble de profundas que el Minimax

·         Importancia de orden y no de valores exactos

Hay que tener en cuenta que para poder podar en un árbol que utiliza este algoritmo se debe recorrer el orden ya fijado, los valores de Max (Alfa) son los del límite inferior y los de Min (Beta) son los limites superiores. Esto quiere decir que en los niveles maximizantes solo Beta puede podar y en los niveles minimizantes solo alfa puede podar.

Imagen 3: Algoritmo Poda Alfa-Beta

CONCLUSIONES
Estos algoritmos son de suma importancia para los problemas de arboles de juegos, cada uno a sido diseñado para que los agentes puedan desenvolverse sin dificultades, el algoritmo Minimax  trata de minimizar la perdida contra adversarios en juegos, para ello hace uso de un cálculo recurrente de cada uno de sus estados sucesores para elegir el mejor movimiento mientras que el algoritmo Poda Alfa-Beta es una version mejorada del algortimo Minimax la cual no necesita explorar todos los nodos para encontrar una solucion optima para problemas de juegos.

BIBLIOGRAFIAS

Russell, S., Norvig, P. 2008. Inteligencia Artificial Un Enfoque Moderno. Segunda Edición. Pearson Education. España

Búsqueda entre Adversarios

1.1.       INTRODUCCIÓN

Haciendo memoria de las anteriores publicaciones sobre inteligencia artificial los agentes se clasifican de diversas maneras según el entorno en el que se encuentren, estos tipos de agentes los cuales se desenvuelven en un entorno en el que existe al menos un agente del cual dependa sus acciones, se los conoce como multiagentes.

Para entender de mejor manera lo que es un entorno multiagente les explicare con el siguiente ejemplo de un juego en el cual tenemos un agente A el cual debe esperar el movimiento del agente B para poder realizar una acción que dé como resultado una ganancia, haciendo que nuestro agente se desenvuelva en un entorno de competitividad.

Como ya había mencionado anteriormente existen diversos tipos de búsquedas que se aplican dependiendo del tipo de agente, ¿pero qué sucede cuando un agente compite con otro y ambos poseen una medida de rendimiento en la cual tienen que ganar? Bueno para poder evaluar este tipo de situaciones tenemos que utilizar lo que se conoce como búsqueda entre adversarios y los diversos algoritmos existentes que utilizan este tipo de búsquedas.

1.2.       OBJETIVO 

Conocer sobre las búsquedas entre adversarios y las diversas estrategias de búsqueda para problemas con juegos.

2.     MARCO TEÓRICO

2.1.       Juegos

Uno de los primeros pasos de la inteligencia artificial fue establecer la teoría de juegos, estos en la inteligencia artificial representan a un entorno en donde se encuentren dos agentes que traten de maximizar su rendimiento pero que a su vez solo uno de ellos debe ganar.

Entre los tipos de juegos que se pueden enlistar según la inteligencia artificial tenemos los siguientes:

·         Juegos de suma cero

·         Minimax o de dos jugadores

·         Por turnos

·         Deterministas

·         De información perfecta.

Una de las principales razones que hace que la inteligencia artificial se interese en la teoría de los juegos es porque en estos se toman decisiones que afectan de manera directa al agente, en muchos casos estas decisiones se realizan sin haber calculado si es la mejor decisión o simplemente es una decisión más.

2.2.       Decisiones Optimas en Juegos

Para realizar decisiones optimas en juegos analizaremos el caso dos agentes que para explicarlo de mejor manera y para entender la temática que le sigue los llamaremos MIN y MAX, en este ejemplo témenos que MAX mueve primer, y que luego de esto se mueve cada uno por turnos hasta que el juego termine, al finalizar el juego se le concederá puntos al agente que gane mientras que al agente que no logre ganar se le penalizara.

Es importante conocer que los juegos cuentan con varios componentes que los definen entre ellos tenemos:

Imagen 1: Juego de Tic-Tac-Toe

2.3.       Estrategias Optimas

Ya conocemos los típicos problemas de búsqueda normal en donde un agente trate de encontrar una solución óptima que lo conduzca hacia un estado objetivo, ¿pero en qué se diferencia este tipo de búsqueda de las búsquedas que se realizan en los juegos? Bueno en los juegos tendremos a dos agentes que compiten por ganar, en donde uno de los dos deberá encontrar una estrategia que le permita responder ante los posibles movimientos del otro agente, expresado de otra forma una estrategia optima es aquella que nos conduce a un resultado tan bueno que cualquier otro tipo de estrategia de búsqueda cuando nos encontramos al frente de un agente infalible.

Imagen

Un ejemplo claro de este tipo de estrategias seria el del juego Tic-Tac-Toe en donde dibujar un árbol para conocer todos los posibles movimientos resultar demasiado complejo.

Existen diversos algoritmos que utilizan estrategias óptimas para poder obtener un mejor resultado como es el caso del algoritmo Minimax pero lo que hace especial este algoritmo es que es fundamental contra aquellos agentes óptimos.

CONCLUSIONES

La búsqueda en adversarios fue creada por los investigadores de la inteligencia artificial, para resolver los problemas de agentes que se encuentran en entornos multiagente, y que son competitivos o cooperativos, en el caso de los juegos, ambos agentes requieren ganar, pero solamente puede haber uno que gane, y la se debe realizar esa búsqueda hasta que se consiga ese objetivo.

BIBLIOGRAFIASRussell, S., Norvig, P. 2008. Inteligencia Artificial Un Enfoque Moderno. Segunda Edición. Pearson Education. España

Agentes de Búsqueda Online y Ambientes Desconocidos

1.1.       INTRODUCCIÓN

Desde sus inicios la inteligencia artificial a intentando crear agentes que sepan cada vez más resolver un problema, para esto es fundamental definir cómo solucionar estos inconvenientes, por lo cual se instauraron las búsquedas que fueron capaces de brindar soluciones a estos, pero, así como no todo es perfecto y que cada entorno es totalmente diferente se decidió realizar diversos tipos de búsquedas para cada tipo de agente.

Las búsquedas online y offline tratan de optimizar el rendimiento de un agente de modo que este se comporte de manera acorde a sus medias de rendimiento, una búsqueda offline es aquella en la que el agente ya posee cierta información sobre el entorno en el cual se va a desenvolver, lo que es todo lo contrario a las búsquedas online en las que el agente no dispone de información previa sobre el entorno en el cual se desenvolverá.

En esta publicación les voy a hablar sobre las búsquedas online, como estas son indispensables para los agentes, que problemas presentan este tipo de búsquedas, los diferentes tipos que posee esta búsqueda y los algoritmos que utiliza de manera local para llevar a cabo problemas de búsquedas informadas.

1.2.       OBJETIVO 

Conocer acerca de las búsquedas online y ambientes desconocidos para conocer qué tipo de agentes las utilizan.

2.     MARCO TEÓRICO

2.1.       ¿Qué Es La Búsqueda Online?

También denominada búsqueda en línea, esta búsqueda la utilizan todos aquellos agentes que se encuentren en un entorno en donde necesiten explorar para saber cómo desenvolverse, este tipo de búsqueda es todo lo contrario a las búsquedas offline en donde los agentes necesitaban de información para poder llevar a cabo su función. Si nos remontamos a las primeras publicaciones de inteligencia artificial podemos recordar al agente aspirador el cual para poder desenvolverse necesitaba de información, esto quiere decir que este era un agente offline sin embargo si este agente se desenvolviera en un entorno en donde no tiene conocimiento previo podríamos decir que está haciendo uso de las búsquedas online.

Como ya he mencionado este tipo de búsquedas son utilizadas por agentes que desconocen su entorno, esto hace que sean una de las búsquedas más utilizadas, para entenderlo de una mejor manera les explicare con un ejemplo en donde tenemos a un agente que es colocado en una oficina, este pese a que no conoce su entorno deberá explorarlo para poder desenvolverse, a este tipo de búsquedas también se le conocen como búsquedas explorativas.

Imagen 1: Agente con búsqueda online explorando una oficina

1.1.       Problemas Con La Búsqueda Online

Como ya conocemos el objetivo de un agente es llevar a cabo su objetivo al más bajo costo posible, pero pese a esto las búsquedas online presentan algunos problemas con estas acciones, la competitividad intenta comparar el costo del camino que el agente deberá tomar para realizar su búsqueda, en este caso el agente deberá ya conocer el camino que deberá recorrer.

Un punto importante que tenemos que entender es que ningún algoritmo que haya sido desarrollado es perfecto y que en ciertas ocasiones el agente podrá llevarnos hacia un callejón sin salida, un ejemplo claro de esto sería un agente que se encuentre en frente de una puerta este no podría atravesarla si no conoce como abrirla.

1.2.       Agentes De Búsqueda En Línea

Una vez que ya conocemos que son los agentes en línea y que problemas pueden presentar estos tipos de búsquedas, los compararemos con los agentes offline para mostrar de mejor manera cuales son las ventajas que tiene implementar este tipo de búsquedas en los agentes.

Imagen 2: Comparción entre la búsqueda Online y la Offline

1.1.       Búsqueda Local En Línea

Ya que conocemos cuales son las ventajas que tienen este tipo de búsquedas tenemos que conocer que también se pueden realizar de manera local, uno de los principales algoritmos de búsquedas locales en línea es el algoritmo de ascensión de colinas, este puede guardar en memoria un estado actual.

Un problema que podemos tener con este tipo de búsqueda es que no se permite el reinicio aleatorio, sin embargo, puede ser considerado usar los denominados caminos aleatorios, estos caminos seleccionan de manera aleatoria una de las acciones disponibles dentro de un estado actual del agente.

Una de las importancias del uso de estos caminos aleatorios dentro de este tipo de búsquedas es que al final este algoritmo encontrara un objetivo al terminar la exploración.

1.2.       Aprendizaje En La Búsqueda En Línea 

El aprendizaje es continuo en este tipo de búsquedas ya que el agente que se encuentre en un ambiente desconocido siempre estará en contacto con el entorno que lo rodea, haciendo que este aprenda de las percepciones que pueda encontrar y realizar una acción determinada, para esto el agente creara un mapa de direcciones con todas las posibles acciones que puede realizar sobre el entorno.

CONCLUSIONES
La búsqueda online es una alternativa de búsqueda para aquellos agentes que tienen que enfrentarse a ambientes desconocidos, estos conceptos son muy importantes para la inteligencia artificial, ya que gran parte de los tipos de agentes que existen, son aquellos que se enfrentan a situaciones desconocidas, sean estas complejas o difíciles de resolver.

BIBLIOGRAFIAS

Russell, S., Norvig, P. 2008. Inteligencia Artificial Un Enfoque Moderno. Segunda Edición. Pearson Education. España