Post on 13-Jan-2016
description
7/18/2019 Búsqueda Entre Adversarios
http://slidepdf.com/reader/full/busqueda-entre-adversarios-56967070eea0b 1/14
ESCUELA SUPERIOR POLITÉCNICA AGROPECUARIA DEMANABÍ MANUEL FÉLIX LÓPEZ
CARRERA INFORMÁTICA
SEMESTRE SÉPTIMO PERÍODO ABRIL-SEPT/2015
TEMA:
BÚSQUEDA ENTRE ADVERSARIOS
MATERIA:
INTELIGENCIA ARTIFICIAL II
AUTORA:
LUISA KATERINE FARIAS CHICA
FACILITADORA:
ING. HIRAIDA SANTANA
MISIÓN
Formación de profesionales íntegros que conjuguen ciencia, tecnología y valores en
su accionar, comprometidos con la sociedad en el manejo adecuado de programasy herramientas computacionales de última generación.
VISIÓN
Ser referente en la formación de profesionales de prestigio en el desarrollo deaplicaciones informáticas y soluciones de hardware.
CALCETA, JUNIO 2015
7/18/2019 Búsqueda Entre Adversarios
http://slidepdf.com/reader/full/busqueda-entre-adversarios-56967070eea0b 2/14
Hasta este momento hemos tratado de los entornos en los
que nuestro agente inteligente busca la solución a un
problema, basándose en métodos sin información y método
con información, pero en estos métodos que analizamos se
trataba de entornos con un solo agente.
A continuación debemos comenzar a tratar con entornos
multiagentes en los que nuestro agente inteligente
interacciona con otro u otros agentes inteligentes, esto
plantea dos tipos de entornos, Colaborativo, Competitivos.
En los primeros, los agentes colaboran para llegar a un
objetivo común, pero implica que deben observarse
mutuamente para no estorbarse, ni que uno de ellos repita
uno de los trabajos del otro.
Adquirir conocimientos sobre la búsqueda entre adversario.
7/18/2019 Búsqueda Entre Adversarios
http://slidepdf.com/reader/full/busqueda-entre-adversarios-56967070eea0b 3/14
En IA, los juegos son, por lo general, una clase más
especializada (que los teóricos de juegos llaman juegos de
suma cero, de dos jugadores, por turnos, determinista, de
información perfecta).
Implican entornos deterministas, totalmente observables en
los cuales hay dos agentes cuyas acciones deben alternar y
en los que los valores utilidad, al final de juego, son siempre
iguales y opuestos (suma cero).
Por ejemplo, si un jugador gana un juego de ajedrez (+ 1), el
otro jugador necesariamente pierde (- 1). Esta oposición entre
las funciones de utilidad de los agentes hace la situación
entre adversarios.
Los juegos han ocupado las facultades intelectuales de la
gente (a veces a un grado alarmante) mientras ha existido lacivilización. Para los investigadores de IA, la naturaleza
abstracta de los juegos los hacen un tema atractivo a
estudiar.
Por ejemplo:
Ajedrez
Ganador (+1)
Perdedor (-1
7/18/2019 Búsqueda Entre Adversarios
http://slidepdf.com/reader/full/busqueda-entre-adversarios-56967070eea0b 4/14
Consideraremos juegos con dos jugadores: MAX y MIN
MAX mueve primero, luego por turno hasta que el juegose termina.
Al final del juego se conceden puntos al ganador y
penalizaciones al perdedor.
El juego puede definirse como una clase de problemas de
búsqueda:
Estado inicial
Función sucesor
Test terminal
Función utilidad
El estado inicial y los movimientos para cada lado definen el
árbol de juegos.
Una solución óptima sería una secuencia de movimientos que
conducen a un estado objetivo (un estado terminal que es
ganador).
7/18/2019 Búsqueda Entre Adversarios
http://slidepdf.com/reader/full/busqueda-entre-adversarios-56967070eea0b 5/14
Considerando un árbol de juegos, la estrategia óptima puede
determinarse examinando el valor minimax de cada nodo,
que escribimos como el VALOR-MINIMAX(n).
El valor minimax de un nodo es la utilidad (para MAX) de estar
en el estado correspondiente, asumiendo que ambos
jugadores juegan óptimamente desde allí al final del juego.
Además el valor minimax de un estado terminal es solamentesu utilidad. MAX preferirá moverse a un estado de valor
máximo, mientras que MIN prefiere un estado de valor
mínimo.
Estado inicial: tablero vacío + ficha de salida
Función Sucesor:
• 9 movimientos posibles, uno por casilla
• Aplicable si la casilla no está ocupada
• Estado resultante: colocar la ficha que toca en la casilla
especificada
Test terminal: tableros completos o con línea ganadora
Función Utilidad:
• 1 si es ganador para MAX
• 0 si es tablas (empate)
• -1 si es ganador para MIN
7/18/2019 Búsqueda Entre Adversarios
http://slidepdf.com/reader/full/busqueda-entre-adversarios-56967070eea0b 6/14
Los nodos terminales se etiquetan por sus valores de
utilidad.
El primer nodo de min, etiquetado B, tiene tres sucesores
con valores 3, 12 y 8 , entonces su valor minimax es 3
Del mismo modo, los otros dos nodos de min tienen un
valor minimax de 2.
El nodo raíz es un nodo MAX; sus sucesores tienen valores
minimax de 3, 2 y 2; entonces tiene un valor minimax de3.
Podemos identificar también la decisión minimax en la
raíz: la acción a1 es la opción óptima para MAX porque
conduce al sucesor con el valor minimax más alto.
7/18/2019 Búsqueda Entre Adversarios
http://slidepdf.com/reader/full/busqueda-entre-adversarios-56967070eea0b 7/14
Juegos populares
permiten más de dos jugadores.
Tenemos que sustituir
el valor para cadanodo con un vector
de valores.
Un juego de tres
jugadores con jugadores A, B y C, un
vector ( vA, vB, vC)
Para los estados
terminales, este
vector dará la utilidad
del estado desde elpunto de vista de
cada jugador.
7/18/2019 Búsqueda Entre Adversarios
http://slidepdf.com/reader/full/busqueda-entre-adversarios-56967070eea0b 8/14
Problema de la búsqueda minimax: el número de estados
que tiene que examinar es exponencial con el número de
movimientos.Es posible calcular la decisión minimax correcta
sin mirar todos los nodos en el árbol.
La poda alfa-beta permite eliminar partes grandes del árbol,
sin influir en la decisión final.
7/18/2019 Búsqueda Entre Adversarios
http://slidepdf.com/reader/full/busqueda-entre-adversarios-56967070eea0b 9/14
El mejor movimiento de MAX en la raíz es a1, porque conduce
al sucesor con el valor minimax mas alto, y la mejor respuesta
de MIN es b1, por que conduce al sucesor con el valor
minimax mas bajo.
a) La primera hoja debajo de B tiene el valor 3. De ahí B,
que es un nodo MIN, tiene un valor de cómo máximo 3.
7/18/2019 Búsqueda Entre Adversarios
http://slidepdf.com/reader/full/busqueda-entre-adversarios-56967070eea0b 10/14
b) La segunda hoja debajo de B tiene el valor 12; MIN
evitara este movimiento, entonces el valor de B es
todavía como máximo 3
c) La tercera hoja debajo de B tiene el valor 8;
d) hemos visto a todos los sucesores de B, entonces el
valor de B es exactamente 3.
7/18/2019 Búsqueda Entre Adversarios
http://slidepdf.com/reader/full/busqueda-entre-adversarios-56967070eea0b 11/14
e) Ahora podemos deducir que el valor de la raíz es al
menos 3., por que MAX tiene una opción digna de 3 en
la raíz
f) La primera hoja debajo de C tiene el valor 2. De ahí, C
que es un nodo MIN, tiene un valor de cómo máximo 2.
Pero sabemos que B vale 3, entonces MAX nunca
elegiría C. Por lo tanto, no hay ninguna razón en mirar a
los otros sucesores de C. Este es un ejemplo de la poda
Alfa-Beta.
g)
Este es un ejemplo de la poda Alfa-Beta.
7/18/2019 Búsqueda Entre Adversarios
http://slidepdf.com/reader/full/busqueda-entre-adversarios-56967070eea0b 12/14
h) La primera hoja de D vale 14, entonces D vale como
máximo 14. Como es mayor que 3 hay que seguirexplorando
i) La segunda hoja debajo de D vale 5, D como máximo
valdrá 5 pues es un nodo MIN. Como 5 podría ser el
valor de D hay que seguir explorando
7/18/2019 Búsqueda Entre Adversarios
http://slidepdf.com/reader/full/busqueda-entre-adversarios-56967070eea0b 13/14
j) El tercer y ultimo sucesor de D vale 2, D vale
exactamente 2.
k) La decisión de MAX entonces es moverse a B dando un
valor de 3
7/18/2019 Búsqueda Entre Adversarios
http://slidepdf.com/reader/full/busqueda-entre-adversarios-56967070eea0b 14/14
Luego de lo aprendido sobre la búsqueda entre adversarios
llegamos a la conclusión que lo antes mencionado es muy
interesante para la vida de un jugador ya que si observamos
los arboles de búsqueda de solución para un entorno con dos
agentes jugando por turnos podemos ver que el árbol de
soluciones cambia con cada juagada o movimiento del
adversario. En esta búsqueda tiene varias estrategias de
exploración las cuales el tipo de entorno es la estrategia
minimax, en la cual se emplean dos funciones para evaluar
cada nodo, min evalua los movimientos del primer jugador y
max los del segundo, el valor de cada nodo y la forma de
seleccionarlos corresponden a la evaluación de cada agente
para las funciones min y max esto es lo que llegamos
entender con la clase explicada.
Russell, S. y Norvig, P. 2004. INTELIGENCIA ARTIFICIAL. UN
ENFOQUE MODERNO. PEARSON EDUCACION. 2 ed. Madrid.
Berzal, F. 2012. Búsqueda entre adversarios. (En línea).
Consultado 05 Jun. de 2015. Formato: PDF. Consultado http:
http://sistemasumma.com/2010/10/09/busqueda-con-
adversarios/.