PDF de programación - Inteligencia Artificial

Imágen de pdf Inteligencia Artificial

Inteligencia Artificialgráfica de visualizaciones

Publicado el 20 de Agosto del 2018
349 visualizaciones desde el 20 de Agosto del 2018
315,8 KB
16 paginas
Creado hace 18a (01/11/2005)
Instituto Tecnológico de Nuevo Laredo

Ingeniería en Sistemas Computacionales

Inteligencia Artificial

Ing. Bruno López Takeyas

Unidad III

Algoritmo Alfa - Beta

Sergio Alfredo Santos Ramírez
Gerson Antonio García Carrasco
Renato García Jiménez
Isidro Gómez Rodríguez
Gilberto Antonio Anwar Peña Nuño

01100304
01100208
01100209
01100219
01100275

Nuevo Laredo Tamaulipas a 20 de Octubre del 2005

Historia de Juegos

Los juegos provocan una inexplicable fascinación y, la idea de que las
computadoras puedan jugar existe desde que existen las computadoras:

• Siglo XIX, Babbage, arquitecto de computadoras, pensó en programar

su máquina analítica para que jugara al ajedrez.

• '50, Shannon describió los mecanismos que podían usarse en un

programa jugara al ajedrez

• '50, Turing describió un programa para jugar al ajedrez pero no lo

construyó

• '60, Samuel construyó el primer programa de juegos importante y

operativo, el cual jugaba a las damas y podía aprender de sus errores
para mejorar su comportamiento

Los juegos proporcionan una tarea estructurada en la que es muy fácil medir
el éxito o el fracaso. En comparación con otras aplicaciones de inteligencia
artificial, por ejemplo comprensión del lenguaje, los juegos no necesitan
grandes cantidades de conocimiento.

En un primer momento se pensó que se podrían resolver por búsqueda
exhaustiva en el árbol del juego, es decir, un árbol que contenga todos los
movimientos posibles de ambos jugadores. Considerando por ejemplo el
juego de ajedrez, en una partida cada jugador realiza una media de 50
movimientos, con un factor de ramificación medio de 35 posibilidades, por
lo tanto para examinar el árbol de juego completamente se tendrían que
examinar 35100 posibilidades. Resulta evidente que una simple búsqueda
directa no es posible de realizar en la práctica, y por lo tanto es necesario
algún tipo de procedimiento de búsqueda heurística.

Todos los procedimientos de búsqueda pueden verse como procedimientos
de generación y prueba, en donde la comprobación se realiza después de
distintas cantidades de trabajo del generador. En un extremo el generador
proporciona una solución completa a evaluar por el comprobador; en el otro
extremo, el generador genera movimientos individuales cada uno de los
cuales se evalúa por el comprobador.



Algoritmo Alpha Beta

La poda Alpha Beta es una técnica para reducir el número de nodos
evaluados por el algoritmo minimax para juegos de 2 contrincantes. Poda
partes del árbol de búsqueda que son tan buenas para un jugador que el
oponente nunca permitirá que lo alcance.



Donald Knuth y Ronald Moore (1975) fueron los primeros en analizar a
fondo la eficiencia de la poda alfa-beta, en su libro “An analysis of alpha-
beta pruning”. Es posible calcular en un determinado juego una decisión
correcta sin tener que explorar todos los nodos de un árbol de búsqueda. A la
técnica que consideramos en particular se le conoce como poda alfa-beta.

Aplicada a un árbol minimax estándar, produce la misma jugada que se
obtendría con minimax, pero elimina todas las ramas que posiblemente no
influirán en la decisión final. La eficiencia de alfa-beta dependerá del orden
como se exploren los sucesores dentro de un árbol, es mejor primero
explorar aquellos sucesores que aparentemente tienen más posibilidades de
ser los mejores.

Para mejorar el rendimiento desde el punto de vista del tiempo invertido en
realizar una jugada se introduce el concepto de poda de aquellas ramas que
con seguridad nos conducirán a un fracaso conocido sin recorrerlas.

El principio general en el que se basa la poda es el siguiente: considérese un
nodo n del árbol, tal que exista la posibilidad de que el jugador pueda ir a ese
nodo. Si el jugador tuviera una mejor opción m ya sea en el nodo padre de n,
o en cualquier punto de elección posterior, en un juego real nunca se
alcanzará n. Es decir, una vez que se cuenta con suficiente información
sobre n (mediante la exploración de algunos de sus descendientes) que
permita llegar a esta conclusión se procede a podar.



Características Poda Alfa-Beta


• Mejora del Algoritmo Minimax; aplicado en juegos de adversarios por
turnos
• Se aplica en espacios de estados demasiado grandes como para analizar
todos los nodos
• La información es imperfecta; es decir, no se conoce el estado del
contrincante. P. ejem. En juegos donde no se ve el tablero del adversario



Produce la misma jugada que se obtendría con MiniMax, pero elimina todas
las ramas que posiblemente no influirán en la decisión final.

Alfa: valor de la mejor opción encontrada hasta entonces en un punto de
elección a través de la ruta de MAX;

Beta: el valor de la mejor (valor más bajo) opción encontrada hasta entonces
en un punto de opción a lo largo de la ruta MIN.

Conforme se efectúa la búsqueda Alfa-Beta se van actualizando los valores
de alfa y beta y se poda

Omitir la expansión de nodos que por sus valores no pueden ser los mejores
(peores).
Interrumpe la búsqueda en algún nivel y aplica evaluaciones heurísticas a las
hojas (profundidad limitada)

Alfa-Beta permite búsqueda dos veces más profunda.

Ordenamiento de los operadores, resultante del conocimiento o experiencia.
Únicamente importa el orden y no los valores exactos.
La poda no afecta al resultado final.



Poda Alfa-Beta

Para mejorar el rendimiento desde el punto de vista del tiempo invertido en
realizar una jugada se introduce el concepto de poda de aquellas ramas que
con seguridad nos conducirán a un fracaso conocido sin recorrerlas.

El principio general en el que se basa la poda es el siguiente: considérese un
nodo n del árbol, tal que exista la posibilidad de que el jugador pueda ir a ese
nodo. Si el jugador tuviera una mejor opción m ya sea en el nodo padre de n,
o en cualquier punto de elección posterior, en un juego real nunca se
alcanzará n. Es decir, una vez que se cuenta con suficiente información
sobre n (mediante la exploración de algunos de sus descendientes) que
permita llegar a esta conclusión se procede a podar.

En el ejemplo anterior tendríamos el siguiente árbol modificado:



Árbol podado



Si examinamos el árbol en la capa MIN central se ha seleccionado el valor 3
para el primer nodo (izquierda) que es el menor que se puede conseguir en
esa rama, a continuación se mira el segundo nodo de la capa central y se
desciende por su hijo de más a la izquierda que le proporciona un valor de 2,
cómo ese valor proporcionado es menor que el valor proporcionado por el
primer nodo examinado de la capa MIN central (3), sabemos que nunca será
escogido por el padre de ese grupo de nodos de la capa intermedia, si el resto
de hijos del nodo de la capa central proporcionan números más altos que 2
nunca serán seleccionados a ese nivel y si proporcionan un número menor
que 2 el padre de dicho nodo de la capa central tampoco lo seleccionará por
que su hermano de la capa central situado a su izquierda proporciona un 3,

por tanto los hijos que quedan por visitar del nodo central de la capa central
pueden ser podados.

En general, la modificación sobre MINIMAX consiste en realizar una
comparación previa a la evaluación de un nodo en una capa determinada en
función de los resultados obtenidos para los nodos hermanos ya evaluados
en dicha capa. Si la capa es MIN entonces no debo seguir evaluando si lo
que me sale en un nodo es menor que lo que ya tenía de los anteriores. Si la
capa es MAX entonces no debo seguir evaluando si lo que me sale en un
nodo es mayor que lo que ya tenía de los anteriores.

La poda Alfa-Beta se basa en la idea de disponer de dos valores que
conforman una ventana a la cual deben pertenecer los valores de fev(n) para
que sean considerados. En los nodos n MAX, según el algoritmo minimax,
se debe maximizar el valor de los nodos sucesores. En estos nodos, se utiliza
el parámetro α (n) que determina el máximo de los valores de los nodos
sucesores encontrado hasta el momento. Así mismo, como los nodos n MIN
tratan de minimizar el valor de los nodos, utilizan el parámetro β (n) que va
a ser, en cada momento, el mínimo de los valores encontrados de los nodos
sucesores de ese nodo.

Existen dos formas de podar, dependiendo del nodo en el que se está
estudiando. En los nodos MAX, la condición de poda es: α p >= β p-1 es decir,
si el α de un nodo MAX de profundidad p es mayor o igual que el β del nodo
MIN padre (profundidad p-1) se pueden podar los sucesores del nodo MAX
no estudiados todavía. Esto es debido a que, como valor inferior, el nodo
MAX va a devolver ese valor de α (α p). Ya que el nodo superior trata de
minimizar, va a calcular:



con lo que siempre va a elegir el β p-1. Por lo tanto, los nodos no estudiados
todavía en el nodo MAX no es necesario estudiarlos, porque no cambian el
valor β del nodo padre.

Simétricamente, la condición de poda en los nodos MIN es: β p <= α p-1. La
explicación es análoga al caso anterior.

Procedimiento Alfa-Beta (Situación Alfa-Beta Profundidad)

Si situación está considerada como empate, devolver 0
Si Situación es ganadora, devolver mayor-número
Si Situación es perdedora, devolver menor-número
Si profundidad = profundidad-máxima, devolver evaluación
(Situación)
Si nivel-max-p

Para todo ai sucesor de situación y Alfa < Beta

Alfa-Beta=Alfa-Beta (a i, Alfa, Beta, profundidad + 1)
Alfa = max(Alfa, Alfa-Beta)

Devolver Alfa
Si no
Para todo a i sucesor de situación y Beta > Alfa
Alfa-Beta=Alfa-Beta (a i, Alfa, Beta, profundidad + 1)
Beta = min(Beta, Alfa-Beta)
Devolver Beta

Ejemplo:

Con el árbol de la figura, va a realizarse una bú
  • Links de descarga
http://lwp-l.com/pdf13094

Comentarios de: Inteligencia Artificial (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios...
CerrarCerrar
CerrarCerrar
Cerrar

Tienes que ser un usuario registrado para poder insertar imágenes, archivos y/o videos.

Puedes registrarte o validarte desde aquí.

Codigo
Negrita
Subrayado
Tachado
Cursiva
Insertar enlace
Imagen externa
Emoticon
Tabular
Centrar
Titulo
Linea
Disminuir
Aumentar
Vista preliminar
sonreir
dientes
lengua
guiño
enfadado
confundido
llorar
avergonzado
sorprendido
triste
sol
estrella
jarra
camara
taza de cafe
email
beso
bombilla
amor
mal
bien
Es necesario revisar y aceptar las políticas de privacidad