Problemática de los juegos en la inteligencia artificial (página 2)

Partes: 1, 2

La clase
particular de juegos que se
estudiará son los llamados juegos de suma cero con
información perfecta entre dos
jugadores. Estos se caracterizan por las reglas anteriores
bajo las restricciones siguientes:

1. Hay exactamente dos jugadores.
2. Se tiene información perfecta.
3. El pago es completo.

La restricción tres significa que si el jugador A tiene
un pago de p, entonces el pago del otro jugador B será de
–p.

Un juego puede
ser formalmente definido como una clase de problema de
búsqueda con las componentes siguientes:

El estado inicial.
Un conjunto de operadores los cuales definen los
movimientos legales que un jugador puede hacer.
Un criterio de terminación que determina cuando el
juego finaliza.
Una función de utilidad la cual da un valor
numérico al estado resultante de un juego. Por
ejemplo. En el ajedrez puede dar los valores +1, -1 ó
0.

Los dos jugadores son llamados Max y Min. Max juega primero y
luego se turnan en el juego. Si este fuera un problema de
búsqueda normal entonces todo lo que Max tendría
que hacer es buscar una secuencia de movimientos que conducen a
un estado
terminal que le sea ganador (según la función de
utilidad). Sin
embargo, Max no está sólo y Min por su parte
tratará de ganar. Por eso, Max necesita encontrar una
estrategia que le
conduzca a un estado terminal independientemente de lo que Min
haga; la estrategia incluye el movimiento
correcto para Max para cada posible movimiento de Min.

En la práctica resulta imposible tener el árbol
de juego y aplicar la función de utilidad a los nodos
terminales. Para resolver este problema se sustituye el criterio
de terminación por un corte a una profundidad dada y la
función de utilidad por una función de evaluación
heurística que se aplica a las hojas del árbol.

Una función de evaluación calcula un estimado de
la utilidad de una posición desde el punto de vista de uno
de los jugadores, en este caso Max. La idea fue propuesta por
Shannon y se basa en que los jugadores de ajedrez y de
otros juegos han desarrollado maneras de juzgar las posibilidades
de una posición. El resultado del juego depende
extremadamente de la calidad de la
función de evaluación. La función de
evaluación debe estar de acuerdo con la función de
utilidad sobre los estados terminales, y debe ser calculable con
un esfuerzo razonable. Debe haber un compromiso entre la
precisión de la función de evaluación y su
costo en tiempo. Una
tercera característica es que la función de
evaluación debe reflejar con precisión la
oportunidad real de ganar.

Una forma de construir la función de evaluación
es usando la expresión:

W1 * f1 + W2 * f2 + . + Wn * fn

donde w i son los pesos y los fi son los rasgos de una
posición particular.

Por ejemplo en el juego de ajedrez los pesos podrían
ser 1 para el peón, 3 para el alfil, 3 para el caballo, 5
para las torres y 9 para la reina, y las fi serían la
cantidad de cada tipo de pieza.

Turing propuso otra función de evaluación para
el ajedrez: sumar los valores de
las piezas negras (N), sumar los valores de las
piezas blancas (B) y calcular el cociente B/N. En el programa de damas
de Samuel se utilizó un enfoque más sofisticado en
donde la función de evaluación es una
combinación de diversas funciones
simples, estas funciones incluyen la ventaja en piezas, la
capacidad de avance, el control del
centro, movilidad, etc.; y toma la forma:

C1 * VentajaPiezas + C2* Avance + C3* ControlCentro + .

Los Ci se ajustan durante un proceso de
aprendizaje
simple en el cual se incrementaba el peso de aquellos componentes
que habían sugerido movimientos que llevaron a la
victoria, mientras que los pesos de aquellos que habían
conducido a derrotas se decrementaban.

Para el juego del tic – tac -toe
una función de evaluación es:

E(p)= ( número de filas , columnas o diagonales
aún abiertas para Max ) –

( número de filas , columnas o diagonales aún
abiertas para Min ).

Si p es ganador para Max, E(p)= (.

Si p es ganador para Min, E(p)= – (.

Nótese que la precisión del valor que da
la función de evaluación de una posición
como un estimado de las posibilidades que tiene Max para ganar
desde la misma, aumenta mientras más próxima
esté esta de una posición final para el juego, es
decir, la precisión crece al crecer la profundidad del
corte. La profundidad del corte puede se fijada o pude variar
dinámicamente usando un enfoque similar a la
búsqueda iterativa primero en profundidad; sin embargo,
ambos enfoques pueden ser desastrosos. Un criterio adecuado para
decidir si a un nivel dado se puede realizar un corte o no es la
estabilidad de la situación del juego. Es decir, para
realizar el corte debe esperarse un estado de reposo, es decir un
nivel en el que no ocurra ningún cambio tan
drástico al pasar al siguiente nivel. Las posiciones de
este tipo se denominan inactivas.

Procedimiento
Minimal

Hasta aquí se han discutido dos importantes componentes
basados en el
conocimiento de un buen programa de juego: un buen generador
de movimientos y una buena función de evaluación
estática. Ambos incorporan gran cantidad de
conocimientos sobre el juego concreto que
se está jugando. La tercera componente necesaria es un
procedimiento
para propagar los valores calculados con la función de
evaluación para los nodos hojas del árbol de
búsqueda generado hasta un nivel dado hacia la raíz
de dicho árbol. El procedimiento clásico para este
propósito es la regla minimax:

1. El valor V(j) de un nodo j en la frontera del
árbol es igual a su función de
evaluación estática E(j), en otro caso
2. Si j es un nodo Max, V(j) es igual al valor
máximo de todos sus sucesores
3. Si j es un nodo Min, V(j) es igual al valor
mínimo de todos sus sucesores .

Esta regla se basa en el presupuesto de
que las evaluaciones propagadas desde la frontera hasta
la raíz dan un estimado más preciso para esos nodos
que el que se podría obtener aplicándoles
directamente la función de evaluación.

Un procedimiento de búsqueda primero en profundidad
basado en esta regla es el siguiente:

1. Si j es terminal, retornar V( j ) = E( j ).
2. Generar los sucesores de j, j1, j2, j3 .., jb.
3. Evaluar V( j1 ), V( j2 ), V( j3 ), ., V( jb ) de
izquierda a derecha.
4. Si j es un nodo Max, retornar V( j ) = max [ V(j1
), V(j2 ), V(j3 ), ., V(jb )].
5. Si j es un nodo Min, retornar V( j ) = min [ V(j1
), V(j2 ), V(j3 ), ., V(jb )].

Este procedimiento es recursivo, pues en el paso 3 si los ji
no son terminales es necesario aplicarles el procedimiento para
calcular v, y como se ejecuta la evaluación de izquierda a
derecha la búsqueda resultante es primero en
profundidad.

Obviamente no es necesario generar todos los sucesores a la
vez y mantenerlos en memoria hasta que
sean evaluados. La búsqueda se puede ejecutar utilizando
el retroceso (backtracking), de modo que los sucesores son
generados y evaluados uno a uno y el valor del nodo padre se
actualiza cada vez que un hijo se evalúa. El procedimiento
resultante es el siguiente:

1. Si j es terminal, retornar V( j ) = E( j ).
2. for k = 1,2, ., b do :
a. generar jk, el k – ésimo sucesor de j.
b. evaluar V( jk ).
c. si k = 1, set CV( j ) ( V( j1 ). En otro caso,
para k ( 2,

set CV( j ) ( max [ cv( j ), v( jk ) ], si j es un nodo Max,
o

set CV( j ) ( min [ CV( j ), v( jk ) ], si j es un nodo
Min

3. Retornar V( j ) = CV( j ).

La variable CV( j ) representa el valor actual actualizado del
nodo j. El paso 2(b) se ejecuta llamando Minimax
recursivamente.

Note que en ambas versiones del procedimiento minimax la
evaluación de j no se completa hasta que todos sus
sucesores sean evaluados. Consecuentemente este procedimiento
examina todos los nodos terminales. Si la profundidad de corte es
m y hay b movimientos legales en cada punto, entonces la
complejidad en tiempo es O(bm). Para los juegos reales este costo
en tiempo es totalmente impracticable, pero este algoritmo
sirve de base para métodos
más realistas y para el análisis
matemático de los juegos.

El procedimiento minimax es un método
óptimo para seleccionar un movimiento desde un
árbol de búsqueda dado siempre que la
evaluación de los nodos terminales sea exactamente
correcta. En realidad, estas evaluaciones son usualmente crudos
estimados del valor de una posición y puede llevar a
grandes errores. Una forma de enfrentar este problema es usar
distribución probabilística.

Efecto Horizonte.

Si se asigna un valor x a un nodo en la profundidad d, es
posible que si se expande a un nivel más, profundidad d+1,
podría resultar una situación de evaluación
muy diferente. Esto es porque el valor x es una
aproximación del valor real. Desafortunadamente, siempre
es posible mirar un movimiento adelante y encontrar una
evaluación diferente. Esto se conoce como efecto
horizonte.

En el efecto horizonte se puede aplazar un suceso pernicioso
inevitable mediante técnicas
de retraso. Esto se debe a la inserción de movimientos de
retardo que causan que una pérdida inevitable de piezas
sólo ocurra más allá del horizonte del
programa (profundidad de la búsqueda máxima) de
modo que la pérdida es oculta. Por ejemplo, supongamos que
hiciéramos un cambio de piezas en donde el oponente
necesitará dos movimientos para capturar nuestra pieza. En
el siguiente turno del oponente, este hará probablemente
el primero de esos movimientos. Pero entonces, en nuestro turno,
podríamos empezar un ataque en algún otro lugar del
juego. El oponente debe responder al ataque, por lo que no puede
completar el cambio de piezas; pero dicho intercambio aún
está esperando su conclusión. En nuestro siguiente
turno podemos instigar un ataque en otro frente, requiriendo otra
respuesta del oponente. Si la búsqueda se detiene en ese
punto nunca notaremos que la pérdida de una de nuestras
piezas es inevitable.

El efecto horizonte esta muy relacionado con una
cuestión clave en la aplicación del método
de búsqueda. ¿Cómo seleccionar la
profundidad de corte? Debido al efecto horizonte es ideal tener
una profundidad de corte dinámica, la cual se determinará
detectando estados de quietud, reposo o estabilidad. Estos
estados son aquellos cuyo valor no cambia drásticamente
haciendo otro movimiento.

El efecto horizonte es menos aparente en programas con un
procedimiento para encontrar estados de reposo donde realizar el
corte. El efecto horizonte se califica como negativo o positivo.
El efecto horizonte negativo es esencialmente el descrito antes,
es una forma de autoengaño en la cual el programa descubre
una serie de movimientos que retrasan un resultado desagradable,
más allá del horizonte de la búsqueda; en
esencia, es un intento no exitoso de impedir un resultado
desagradable. El efecto horizonte positivo es una forma diferente
de autoengaño en el cual el programa intenta acometer una
consecuencia deseada dentro del horizonte de la búsqueda
aun cuando el resultado podrá ser mucho mejor si se
pospone unos movimientos.

Procedimiento
Alfa – Beta

El procedimiento Alfa – Beta corta las ramas del árbol
de búsqueda que son innecesarias. Para ello establece las
cotas Alfa y Beta cuyos valores sirven de referencia para
realizar los cortes. Estos valores se ajustan
dinámicamente y son trasmitidos top – down como sigue:

Cota – (: La cota de corte para un nodo Min j es una cota
inferior llamada (, igual al valor actual más alto de
todos los antecesores Max de j. La exploración de j puede
ser terminada tan pronto su valor actual CV iguala o cae debajo
de (.

Cota – (: La cota de corte para un nodo Max j es una cota
superior llamada (, igual al valor actual más bajo de
todos los antecesores Min de j. La exploración de j puede
ser terminada tan pronto su valor actual CV iguala o sobrepasa
(.

El procedimiento V(j;(,() evalúa recursivamente v( j )
para los parámetros ( < (. Retorna V( j ) si este valor
está entre ( y (, retorna ( si ( V( j ) (( ) o ( si ( V( j
) ((). Claramente, si J es la raíz de un árbol de
juego su valor minimax será obtenido por V ( j,-(,+().

Procedimiento ( -(: V( j; (, ( ).

1. Si j es terminal, return V ( j ) = E( j ). En
otro caso, sean ji, ., jk los sucesores de j, k ( 1,

Si j es un nodo de Max ir al paso 2, sino ir a 2".

2. Set ( ( max [ (, v( jk; (,() ]
3. Si (((, return (, else continue
4. Si k = b, return (; else k ( k+1 e ir al paso
2.

2". Set ( ( min [(, v( jk; (,() ]

3". Si ((( , return (, else continue

4". Si k = b, return (; else k ( k+1 e ir al paso 2".

La efectividad del algoritmo ( – ( depende del orden en el
cual los sucesores se examinan. Para cualquier conjunto de nodos
hojas existe un ordenamiento tal que el algoritmo no realiza
ningún corte, en ese caso todos los nodos hojas tienen que
ser evaluados, comportándose el algoritmo en su peor
caso.

A pesar de que el algoritmo AlfaBeta es el paradigma de
los algoritmos
para los problemas de
juego y uno de los más elegantes algoritmos de la Inteligencia
artificial, tiene varias limitaciones, entre ellas:

1. Se asume que el estimado que hace la
función de evaluación heurística del
valor del nodo es perfecto, lo cual no es necesariamente
así.
2. Se busca el máximo o mínimo valor de
los estimados hechos usando la función de
evaluación de los nodos, sin embargo, caminos que
conducen a varias buenas alternativas pueden ser preferibles
a caminos que llevan a una alternativa que parece ser
mejor.
3. Todo el conocimiento del juego se resume en un
valor escalar, lo que hace que necesariamente se pierda
información que es potencialmente útil para la
búsqueda.
4. El algoritmo expande los nodos de una manera
primero en profundidad que depende solamente del orden en que
los sucesores de un nodo son generados.
5. Se asume que ambos jugadores usan la misma
heurística.

El juego de
ajedrez

Un programa de ajedrez típico contiene tres elementos:
descripción del tablero, árbol de
corte y búsqueda y evaluación de la
posición.

a) Datos de interés.

Al inicio de un juego de ajedrez cada lado tiene 20
movimientos posibles de modo que hay unas 400 posiciones posibles
diferentes después de los primeros intercambios. El
número de movimientos posibles para cada jugador es de
aproximadamente 50 en el medio juego.

Como se dijo el factor de ramificación (b) para el
juego de ajedrez es de 35 la profundidad del árbol (d) es
de 100.

b) Función de evaluación.

La forma que toma la función de evaluación
estadística para este juego es:

E(p) = a*B + b*R + c*M + d*C + e*P + f*A

El parámetro B es el balance material existente en la
posición, para ello se usan los valores: peón = 1,
caballo = alfil = 3, torre = 5, reina = 10. Por eso si max tiene
ventaja de un alfil y min de un peón se tendría B =
+3 –1 = +2.

R: La seguridad
relativa del rey. El coeficiente b puede variar durante el juego,
volviéndose 0 cuando las piezas principales han sido
sacadas del juego y el rey ayuda el ataque protegiendo sus
propias piezas.

M: La movilidad de las piezas, medida por la cantidad de
casillas para las cuales cada pieza puede moverse: este
número será pesado por un factor dependiendo del
tipo de la pieza.

C: Control del centro. El coeficiente d toma un valor alto en
el medio juego.

P: Estructura de
peones. La contribución positiva la dan los peones
protegidos, avanzados y pasados de max y de los aislados y
desprotegidos de min.

A: Esta es una medida de las posibilidades relativas para
atacar, tomando en cuenta las piezas avanzadas más
allá de la cuarta fila, torres sobre filas o columnas
abiertas, posibles jaques, etc.

c) Método de búsqueda.

Los preferidos son variantes del algoritmo (-( limitado a
profundidad. El modelo general
para todos los programas de ajedrez es el siguiente. Una
búsqueda exhaustiva a todo lo ancho a unas pocas capas de
profundidad. A profundidades más grandes se usa alguna
forma de búsqueda selectiva, típicamente
movimientos poco prometedores se ignoran.