En
entornos competitivos, se debe considerar las acciones que pueden tomar los
contendientes, el no considerar estas posibles decisiones, puede llegar a ocasionar
problemas en lo que se está realizando, por esto se emplean las búsquedas con
adversario, en la cual se decide la mejor jugada en un momento especifico; a
este tipo de búsqueda también es popularmente conocida como un juego, sin tener
en cuenta toda la teoría que está detrás basándose en la inteligencia
artificial, para poder hacer los procesos más óptimos, y hacer el papel de
adversario en cualquier juego.
Los
juegos son un campo tan grande que se desprende toda una teoría de ellos.
Existen varios tipos de juegos, entre ellos están los de 2 jugadores,
movimientos alternos e información perfecta, entre otros.
Los
juegos de suma cero, son aquellos en los cuales la ganancia de uno es la pérdida
del otro, sumando las ganancias de uno, respecto a la perdida de otros, en
cambio los juegos de suma, hacen alusión a aquellos juegos en los que la
ganancia de uno, no representa ninguna pérdida para el otro, esto quiere decir
que cada uno de los puntos ganados, han sido por estrategias bien empleadas a
la hora de jugar, un ejemplo de esto es el futbol, en el cual el marcador de un
equipo es por los goles realizados, y al ganar un partido el puntaje es ganada
por el equipo, más no descontado del otro.
Los
juegos de movimientos alternos, o de dos jugados, son aquellos en los que cada
uno de los jugadores ataca pensando en obtener los mejores resultados, y que
este genere las menores ganancias para su adversario, es a lo que se le llaman
Min y Max. Los juegos de información perfecta es en el que cada movimiento esta
previamente establecido y cada jugador puede saber lo que va a pasar, algunos
ejemplos de este tipo de juegos es el ajedrez o las damas, y contrario a estos,
están los juegos de información imperfecta, en los que entra a jugar un papel
decisivo el azar, y por lo tanto los jugadores no pueden llegar a determinar
que va a pasar con su juego, entro estos esta cualquier juego de cartas, como
lo es el póker, stratego, etc.
Para
la búsqueda con adversario se crearon varios algoritmos, teniendo en cuenta
todos aquellos posibles movimientos y estrategias que se pueden tomar durante
un juego, al pensar en esto, se puede ver son teorías bastante complejas, ya
que los factores de ramificación pueden llegar a ser bastante grandes, tanto
así que no se puede contar con la capacidad suficiente para desarrollar todo el
árbol o grafo necesario para desarrollar completamente alguno de estos juegos,
para esto se crean diferentes variaciones en las cuales como base siempre se
tienen las búsquedas principales en la inteligencia artificial, como lo son la
búsqueda en anchura y profundidad, a estas búsquedas se les agregan características
propias en la búsqueda con adversario, pero siguen teniendo la misma base;
entre estos algoritmos está el Minimax, Alfa/Beta y Megamax, las cuales suelen
ser muy usadas en diversos juegos, que tal vez hemos experimentado o
participado sin tener idea de que utilizan la inteligencia artificial para
realizar las jugadas.
Minimax
es un algoritmo de búsqueda con adversario, pero también suele ser llamado un
algoritmo de decisión, una de las características básicas en este tipo de
juegos y en este algoritmo en especial es la información completa que este
posee, por lo cual cada jugador conoce las jugadas del otro o el estado en el
que se encuentra. Se elige el mejor movimiento para cada jugador, suponiendo
que el contrincante siempre elegirá el peor, de ahí la frase célebre que resume
todo el algoritmo “elegir el mejor movimiento para
ti mismo suponiendo que tu contrincante escogerá el peor movimiento para ti.”
El
algoritmo es representado por medio de árboles, los cuales contienen nodos que
representan la situación del juego, cada vez que se realice un movimiento o se
tome una decisión, el algoritmo generara todo el árbol, suponiendo las
estrategias que va tomar el adversario, para así tener en cuenta tanto los mejores
como los peores caminos, para así poder llegar a la victoria. También se debe
decir que es un procedimiento recursivo, en el cual gana algún jugador, y se
exploran una cierta cantidad de niveles, hasta llegar a un punto establecido
por el mismo algoritmo, para no tomar ciclos infinitos, como si lo hace el algoritmo
de profundidad.
De forma
más clara, se empieza en la posición inicial, y de ahí se pasa determinar cada
uno de los movimientos permitidos por el juego, generando todas las posiciones
posibles, hasta llegar al nivel final –si así el juego lo permite- o llegar un
nivel establecido, si las ramificaciones son demasiadas y no se cuenta con la
capacidad para hacerlo; al llegar a este punto se aplica una función
evaluadora, la cual usa una heurística que tiene la capacidad para determinar
si un movimiento es bueno o malo para cada jugador, después de aplicar la
función el algoritmo elige el movimiento para el jugador, devolviéndose en el
árbol para poder evaluar cada uno de los niveles.
La
función de evaluación se establece de la manera en la que los valores positivos
son para el jugador o la máquina que hace uso del algoritmo, y se desprenden
valores negativos para el adversario como las mejores jugadas para esté, así
utilizando el estos valores para maximizar los valores del jugador, y minimizar
los valores del adversario, esto en el árbol se hace de forma alterna,
avanzando de un nivel a otro, o de un movimiento a otro, durante el juego.
Juegos
como el ajedrez utilizan este algoritmo, pero el problema principal de esté, y
de muchos juegos más, es el hecho que no se puede realizar el árbol completo de
movimientos posibles, ya que su factor de ramificación es gigante, y no existe
la capacidad necesaria para poder efectuar el desarrollo del mismo, y tampoco
se conoce una heurística precisa para que se asegure que el juego va a ser
ganado.
Otro
algoritmo popular en la búsqueda con adversario, es el alfa/beta, que en
realidad es una variante del ya mencionado Minimax, ya que este contiene
grandes problemas al realizar la búsqueda en el árbol, porque los nodos que
este puede llegar a generar pueden ser bastantes, tanto así que no puede ser
posible llegar a generarlos, haciendo uso de hardware en el que se debe situar
el software para así poder tener un buen desarrollo del algoritmo, por todos
los problemas que puede llegar a generar el algoritmo, se creó la variante
alfa/beta, la cual usa un mecanismo bastante parecido al Minimax, pero en este
se reduce el número de nodos a evaluar, eliminando partes del árbol en el que
se considere que no se va llegar a ninguna parte hablando en términos del
juego, esto quiere decir, que se pone en el papel del adversario, y según la
función evaluadora y la heurística que esta trae consigo, elimina aquellos
caminos que considera no van a influir en una decisión final.
El
funcionamiento del algoritmo viene a estar dado por el uso de dos parámetros,
el alfa y el beta, que guía la búsqueda en el árbol. Alfa es la mejor opción en
el recorrido para el máximo valor, y el beta es la mejor opción hasta el
momento, para el valor mínimo, representando el mínimo valor que se le puede
asignar un nodo Max.
Este
algoritmo puede traer problemas por el hecho de no considerar una “mala jugada”,
ya que según muchos jugadores, y lo que ha sido demostrado desde algoritmos, y
grandes batallas entre estos y los mejores jugadores de ciertos juegos en específicos,
es que para llegar a encontrar el mejor camino para un juego, y tomar las
decisiones apropiadas en cuanto a movimientos, se debe pensar en cada posible
mal jugada, para así tener en cuenta el camino que el juego puede tomar desde
esa postura, por lo tanto, el algoritmo no es completo ni optimo, ya que al no
recorrer todo el árbol, puede que no encuentre la mejor solución, o simplemente
no la encuentre.
Negamax
es otro de los algoritmos en búsqueda con adversario, como los ya mencionados,
tiene un funcionamiento en el cual se tienen en cuenta los valores máximos y
mínimos que se puede tomar en el recorrido del juego, haciendo uso de una
función evaluadora, en la cual se pueden determinar los mejores o peores
movimientos; la generación del árbol para según haya sido establecido, si hay
demasiados niveles o si en caso contrario el juego es corto y se puede llegar a
desarrollar los niveles en su totalidad.
Existen
varias búsquedas con adversario, solo se han mencionado tres, pero existen
muchas variantes de los ya mencionados, tomando en su mayoría de caso el Minimax
como la base para ellos, siendo este el más usado en la mayoría de juegos; se
sabe que la inteligencia artificial ha avanzado bastante en la investigación de
toda la teoría de juegos, consiguiendo derrotar, por ejemplo, al mejor jugador
de ajedrez del mundo con la Deep blue que es una súper computadora desarrollada
hace casi unos 20 años, desde ese momento, hemos visto como la tecnología ha
avanzado, creando cada vez cosas mejores, y una mayor innovación, en cuanto a
juegos, haciendo uso de una gran variedad de búsquedas.
