Búsqueda en árboles de juego
La destreza al competir en partidos de Ajedrez, Damas, Othello o go, ha
sido por largo tiempo considerado como un rasgo distintivo de
inteligencia humana.
Es natural que el público en general se muestre interesado en el tipo de
programas que pueden competir en estos juegos y que inclusive muchos
consideran sus logros como una medida del progreso en IA.
Este hecho a ayudado a elevar el STATUS de estos programas al grado
de que la investigación en programas de este tipo se desarrolla en
muchas universidades de prestigio. Los juegos competitivos, por otro
lado constituyen un perfecto laboratorio para experimentar metodologías
complejas para la solución de problemas.
Búsqueda en árboles de juego
La mayoría de los juegos competitivos jugados por las computadoras,
son con dos jugadores y perfectamente informados.
Hay dos jugadores adversarios quienes alternativamente van haciendo
sus movimientos, cada uno de los cuales ce en la talla de su
oponente su propio éxito.
A cada turno, las reglas definen perfectamente los movimientos
legales así como que efectos tendrá con el juego, no dejando
oportunidad al azar.
En contraste con juegos de cartas o backgamon, cada jugador
tiene completa información acerca de la posición de su oponente.
Búsqueda en árboles de juego
Un ARBOL DE JUEGO es una representación explicita de todas las
posibles configuraciones del juego.
El nodo raíz representa la posición inicial del juego, sus sucesores
son las posiciones que el primer jugador puede alcanzar en un
movimiento, sus sucesores son las posiciones resultantes de a
respuesta del segundo jugador.
Los nodos terminales son aquellos que representan GANE, PERDI,
EMPATE. Cada ruta del nodo inicial a un nodo terminal
representa una partida completa en particular.
Por razones que se verán más adelante llammos al primer jugador
MAX y al segundo MIN.
Búsqueda Mini-Max
Procedimiento de etiquetamiento:
Si j es un nodo no terminal MAX entonces:
GANE: si cualquiera de sus
sucesores es un GANE.
Status(j) =
PERDI: si todos sus sucesores
son Perdí.
EMPATE: si cualquiera de sus
sucesores es EMPATE
y no hay ningún GANE.
Búsqueda Mini-Max
Si j es un nodo no terminal MIN entonces:
GANE: si todos los nodos
sucesores es un
GANE.
STATUS(j)=
PERDI: si alguno de sus
sucesores es un PERDI.
EMPATE: si cualquiera de
sus sucesores es
EMPATE y no hay
ningún nodo PERDI.
Búsqueda Mini-Max
Así tenemos que la función STATUS(J) debe interpretarse
como el mejor status terminal que MAX puede alcanzar
en la posición J si juega óptimamente en contra del
oponente perfecto.
Resolver el árbol de juego significa etiquetar el nodo raíz
como G-P-E. Una ESTRATEGIA GANADORA es aquella
que garantiza un GANE a MAX sin importar lo que MIN
juegue.
Lookahead y función de evaluación
En la sección anterior de proceso de etiquetado de
los nodos requiere que el arbol de juego sea
generado completo, algo poco recomendable para
la mayoría de los juegos competitivos: Ej.

Un juego completo de Damas requiere 1040
nodos no terminales [ Samuel, 1959 ].

Un árbol de juego completo del ajedrez
requiere cerca de 10120 nodos.
Búsqueda en árboles de juego
Estos números muestran que es casi absurdo pensar
en obtener siempre un árbol de juego completo.
Una técnica para poder evaluar el valor de un nodo
consiste en utilizar aproximaciones Heurísticas, es
decir utilizar una FUNCION DE EVALUACION, que se
base en características, estadísticas del juego
únicamente.
Una generalización obvia consiste en no evaluar el
tablero inmediatamente, sino después de extender
el juego con algunos movimientos.
Regla del MiniMax
1.- El valor V(J) del nodo J en la frontera de
búsqueda es igual al valor de su Función de
Evaluación Estática e(J).
2.- Si J es un nodo MAX, V(J) es igual al
máximo valor de sus sucesores.
3.- Si J es un nodo MIN, V(J) es igual al mínimo
valor de sus sucesores.
Algoritmo de podado alpha-beta
El Algoritmo de podado alpha-beta es el más
utilizado en aplicaciones a búsquedas en árboles
de juego.
Este algoritmo incrementa la velocidad de
búsqueda del MiniMax mediante el podado de
aquellas ramas que no influyen más en el valor
del nodo raíz.
Función de evaluación
Que podemos evaluar en términos generales:
Material, Movilidad y Estructura.
Material = Piezas mías – Piezas del oponente
Movilidad= #Movs. Míos - #Movs. Oponente
Estructura: Asignar valores a casillas buenas y malas.
Función de evaluación:
Val = K1*Ma+K2*St+Mo
en donde:
K1= Movimiento
10
y
K2= Mov. Prom - K1
10
0
5 -3
3 3
-3 0
2
-2 3
5
2 5
-5 0
1 5
1
-3 0
-5 5 -3
3
2
3 -3 0
-1 -2 0
1
4
5
1
-1 -1
3
-3 2 -2
Descargar

Búsqueda en Arboles de Juego