I. INTRODUCCIÓN
Como se ha venido hablando en los post anteriores, y en la cátedra de inteligencia artificial 1, los agentes se clasifican de manera diferente según el entorno que los rodee, aquellos agentes que se rodean de un entorno en el que existe al menos un agente del cual dependa su acción, se denominan multiagentes debido a que se encuentran en entornos multiagente.
Un entorno multiagente muy conocido, es aquel en el que se realiza un juego, el agente A, debe esperar del movimiento de B para realizar una acción que le lleve a ganar, esto lo convierte en un agente que se desenvuelve en un entorno competitivo.
Ya hemos visto búsquedas para distintas clases de problemáticas de los agentes, pero, qué ocurre cuando un agente está en competencia con otro, y ambos tienen la medida de rendimiento de ganar, para evaluar esta búsqueda se utiliza lo que se conoce como búsqueda entre adversarios, de la cual explicare más detalladamente a lo largo de este post.
II. OBJETIVO
Aprender sobre la búsqueda entre adversarios, de los agentes que se rodean en entornos multiagente y competitivos, además aprender sobre la teoría de los juegos.
III. MARCO TEÓRICO
3.1. JUEGOS
Los juegos en inteligencia artificial, son aquel entorno en donde los agentes se encuentran en conflicto y ambos jugadores tratan de maximizar su rendimiento.
Existen distintos tipos de juegos clasificados según la Inteligencia artificial, estos son:
Juegos de suma cero.
Minimax o de dos jugadores.
Por turnos.
Deterministas.
De información perfecta, como por ejemplo el Ajedrez.
La inteligencia artificial se enfoca en la teoría de los juegos debido a que en éstos se toman decisiones que afectan al agente, muchas veces estas decisiones son tomadas sin calcular si ésta es la decisión óptima o no.
Los componentes de los juegos están descritos en el gráfico 3.1
Gráfico 3.1. Componentes de los juegos.
3.1.1 MINIMAX
Se denomina Minimax al juego entre adversarios en el que intervienen dos jugadores, MIN y MAX, un ejemplo de éste juego puede ser 3 en raya, o triqui traca o como se lo conozca este juego tan popular.
El objetivo de este algoritmo es encontrar un movimiento o un conjunto de los mismos, que hagan posible que MAX le gane a MIN, quien sería nuestro adversario.
Cuando ocurre un empate el resultado es 0, cuando gana X que es MAX el resultado es +1 y cuando gana MIN el resultado es -1.
3.1.1.1 EJEMPLO DE BÚSQUEDA ENTRE ADVERSARIOS
En un tablero 3x3, El jugado MAX marca sus casillas con “X” y el jugador MIN con “O”. A medida que vayan pasando los turnos, cada jugador llena el tablero y el ganador es aquel que coloca sus fichas en línea.
Elementos del juego:
Estados: tablero y la siguiente ficha a colocar.
Estado inicial: tablero vacío + la primer ficha colocada.
Estados finales: tablero lleno con línea que gana o con un empate.
La forma en la que se puede jugar como ya conocemos es teniendo 9 movimientos posibles por cada casillero, sin embargo no se pueden marcar aquellas que ya estén marcadas.
Como se puede observar en el gráfico 3.2 el dibujar el árbol sería muy extenso, debido al gran número de estados posibles.
Gráfico 3.2. Tic tac toe.
3.2. COMPLEJIDAD DE LOS JUEGOS ENTRE ADVERSARIOS.
Algunos juegos entre adversarios son muy difíciles de graficar en un árbol debido a la gran cantidad de estados posibles, a continuación la tabla 3.1. Tiene algunos juegos y su nivel de complejidad.
Tabla 3.1. Complejidad de los juegos.
IV. CONCLUSIÓN
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.
Existen muchas clases de juegos que pueden ser representados en la búsqueda entre adversarios, el ajedrez y 3 en raya son algunos de los más conocidos.
Minimax, es aquel juego en donde participan 2 jugadores A y B o mejor representado como MIN y MAX, teniendo en cuenta que somos nosotros MAX, por eso cuando MAX gana es un 1 positivo es decir un punto positivo, y cuando MIN gana es un 1 negativo, además de que cuando existe un empate, ninguno tiene puntos.
V. BIBLIOGRAFÍA
Berzal, F. s.f. Búsqueda con adversario: Juegos. (En línea). ES. Consultado el 16 de Jul. 2015. Formato PDF. Disponible en: http://elvex.ugr.es/decsai/iaio/slides/A6%20Games.pdf
Ceccaroni, L. 2007. Búsqueda entre adversarios. (En línea). ES. Consultado el 17 de Jul. 2015. Formato PDF. Disponible en: http://www.cs.upc.edu/~luigi/II/IA-2007-fall/2d-busqueda-entre-adversarios-(es).pdf
Ruíz; Alonso, J; Mateos, F; Hidalgo, M. 2012. Tema 7: Búsqueda con adversario (juegos). (En línea). ES. Consultado el 17 de Jul. 2015. Formato PDF. Disponible en: http://www.cs.us.es/cursos/ia1/temas/tema-07.pdf
Russell, S y Norvig, P. 2008. Inteligencia Artificial Un Enfoque Moderno. 2 ed. España. Pearson Education. p 1242