Investigacion Guia3 CC100308

UNIVERSIDAD DON BOSCO

FACULTAD DE INGENIERÍA
ESCUELA DE COMPUTACIÓN

Asignatura: Sistemas expertos e inteligencia artificial.

Grupo: 02L

Docente: Lic. Omar Torres

Actividad: Investigación – guía #3.

Alumno: Emerson Francisco Cartagena Candelario

Carnet: CC100308

San Salvador, 19 de Febrero del 2015

Métodos de búsqueda iteractivas para juegos.
Juegos sin adversario: algoritmo A*
Parajuegos simples unipersonales (por ej. 8-puzzle) puede usarse el algoritmo A*. Este
algoritmo implementa una búsqueda primero el mejor.
Se utiliza una función de evaluación estática f formada por:
f=g+h


La función g es una función de coste de llegar del estado inicial al estado evaluado.



La función h es una estimación del coste de llegar desde el estado evaluado al estado
final u objetivo deljuego.

En cada paso del algoritmo se selecciona el mejor nodo que no se ha expandido hasta el
momento, es decir, aquel que tiene menor valor de función f. Este nodo se agrega a una lista
de nodos explorados y sus nodos sucesores se agregan a la lista de nodos pendientes de ser
explorados.

Búsqueda Minimax
En juegos bipersonales el algoritmo más usado es el denominado Minimax. El procedimiento
debúsqueda Minimax es una búsqueda en profundidad (DFS) de profundidad limitada.
La idea consiste en comenzar en la posición actual y usar el generador de movimientos
plausibles para generar las posibles posiciones sucesivas hasta un cierto límite de niveles. A
continuación se aplica la función de evaluación estática a las posiciones obtenidas y se elige
la mejor posición para el jugadorcorrespondiente, llevando los valores un nivel hacia atrás
para continuar la evaluación en todos los niveles anteriores.
Se supone una función de evaluación estática que devuelve valores elevados para indicar
buenas situaciones y valores negativos para indicar buenas situaciones para el oponente.

Visto de esta manera, la meta es maximizar el valor de la función estática de la siguiente
posición de tablero.El nombre del algoritmo deriva de considerar que, dada una función estática que devuelve
valores en relación al jugador maximizante, éste procura maximizar su valor mientras que su
oponente procura minimizarlo. En un árbol de juego donde los valores de la función estática
están en relación al jugador maximizante, se maximiza y minimiza alternadamente de un
nivel a otro.
El algoritmo Minimax es unprocedimiento recursivo, y el corte de la recursión está dado por
alguna de las siguientes condiciones:


Gana algún jugador



Se han explorado N capas, siendo N el límite establecido



Se ha agotado el tiempo de exploración



Se ha llegado a una situación estática donde no hay grandes cambios de un nivel a
otro

En el algoritmo MINIMAX detallado en breve la función de corte de recursiónSUFICIENTE
(posición, profundidad) sólo considera las dos primeras condiciones de corte.
El algoritmo MINIMAX( posición, profundidad, jugador) usa dos funciones:


GENMOV (posición, jugador): devuelve la lista de movimientos posibles para el
jugador a partir de la posición



ESTÁTICA (posición, jugador): devuelve un número que representa la bondad de la
posición desde el punto de vista dejugador.

A diferencia de los valores mostrados en el ejemplo de la figura 1, la función ESTÁTICA
devuelve valores en relación al jugador actual en vez del jugador maximizante. Por esta
razón, en lugar de realizar maximización y minimización alternativas, siempre se maximiza
el valor que devuelve esta función.

El algoritmo MINIMAX no necesita tratar diferente a los niveles maximizante y minimizante
dadoque invierte los valores de un nivel a otro.
La función Minimax devuelve una estructura con


VALOR: valor propagado de la función estática



CAMINO: camino para llegar a la solución desde la posición

La primera llamada a la función recursiva será:
MINIMAX (posiciónactual, 0, JUGADOR-UNO)

Algoritmo de Poda α–β
La idea básica del algoritmo α–β [3] es podar partes irrelevantes del árbol que...