Búsqueda

Algoritmos de búsquedas con adversario

MINIMAX:

Es un algoritmo recursivo y de decisión, que consiste en elegir el mejor movimiento para la maquina, teniendo en cuenta que el adversario escogerá una jugada que lo desfavorecerá. Para elegir la mejor opción este realiza un árbol de búsqueda con los posibles movimientos, luego es recorrido según un estado.

El árbol es generado hasta un cierto nivel, también utiliza una función de evaluación estática en cada nodo hoja que indica valores positivos, negativos o neutros de los posibles movimientos para luego elegir la mejor opción.

Las jugadas son alternas entre máximos (Max) y mínimos (Minx) hasta llegar al final del juego o una determinada profundidad, los valores altos son buenos para Max y los bajos son buenos para Min.

Este algoritmo se implementa en juegos de dos participantes, de suma cero y de información completa. También es completo y optimo.

Image2080

fig. 1 Algoritmo minimax [10]

NEGAMAX

Es un algoritmo basado en minimax, pero está es más compacta.

No utiliza las funciones de Max y Min, en vez de estos utiliza la siguiente función matemática que traduce en una búsqueda de la Máxima, permitiendo la posibilidad de simplificar el código:

max(a,b) == – min(-a, -b)

Maneja valores positivos para la maquina y negativos para las del adversario.

negamax

Fig. 2 Algoritmo negamax[5]

ALFA/BETA

Es un algoritmo para mejorar a minimax, utilizando una técnica de ramificación y poda que abandona un cierto movimiento si se sabe si es peor que el mejor encontrado en ese momento. Se piensa que no es necesario dedicar tiempo calculando que tan malo es, y se sigue buscando soluciones mejores que la que se tiene.

Se utiliza un limite inferior y uno superior llamados umbrales alfa y beta, donde alfa es la cota inferior y beta es la cota superior, contienen valores que determinan si vale la pena explorar un camino.

Las ramas que se podaran serán las que estén fuera del limite de alfa y beta, y el demás espacio se le llama ventana de búsqueda, es aquí donde encontramos la solución. Existen algunas condiciones para los cortes como:

  • En un nivel de minimización, los sucesores con un valor más grande que el límite superior serán cortados.
  • En un nivel de maximización, los sucesores con un valor más pequeño que el límite inferior serán cortados.

Este algoritmo es de información incompleta y no es completo ni optimo ya que se dejan de explorar los nodos que se han podado y allí podría encontrarse otra solución.

poda

Fig. 3 Algoritmo alfa/beta[8]

Biografía

[1]Caparrini, F. and Work, W. (n.d.). Minimax: Juegos con adversario – Fernando Sancho Caparrini. [online] Cs.us.es. Available at: http://www.cs.us.es/~fsancho/?e=107.

[2]Guerra Marrero, A. (2010). Algoritmo Minimax, un jugador incansable | Razón Artificial. [online] Razonartificial.com. Available at: http://razonartificial.com/2010/08/algoritmo-minimax-un-jugador-incansable/ .

[3]Plasencia Prado, C. (n.d.). El algoritmo Minimax y su aplicación en un juego. [online] DevCode Tutoriales. Available at: https://devcode.la/tutoriales/algoritmo-minimax/.

[4]López Takeyas, B. (n.d.). Minimax. [online] Available at: http://www.itnuevolaredo.edu.mx/takeyas/apuntes/Inteligencia%20Artificial/Apuntes/IA/Minimax.pdf.

[5]Valocchi.it. (n.d.). LaMoSca: l’algoritmo NegaMax. [online] Available at: http://www.valocchi.it/lamosca/negamax.html.

[6]Es.wikipedia.org. (2013). Negamax. [online] Available at: https://es.wikipedia.org/wiki/Negamax [Accessed 29 Apr. 2017].

[7]A.F., P. (2008). Algoritmos de juegos. [online] Departamento de Lenguajes y Sistemas Informáticos UPC – FIB. Available at: http://www.gran-angular.net/wp-content/uploads/2008/07/algoritmos-de-juegos.pdf.

[8]tesis.uson. (n.d.). Capitulo3. [online] Available at: http://tesis.uson.mx/digital/tesis/docs/20586/Capitulo3.pdf.

[9]López Takeyas, B. (n.d.). Alfa-Beta. [online] Tecnológico Nacional de Mexico. Available at: http://www.itnuevolaredo.edu.mx/takeyas/Apuntes/Inteligencia%20Artificial/Apuntes/IA/Alfa-Beta.pdf.

[10] Algoritmo minimax (n.d) [image] Available at: http://www.monografias.com/trabajos15/masp-ensenianza/masp-ensenianza/Image2080.jpg

 

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s