Problemática de los juegos en la inteligencia artificial

La clase de juegos considerada es la que incluye los juegos donde intervienen dos jugadores con información completa. Hay dos jugadores adversarios quienes alternan sus movimientos, cada uno ve las fallas de su oponente y sus propios éxitos.

En cada turno las reglas del juego definen los movimientos legales y que efecto tendrá cada movimiento posible. Los juegos comienzan a partir de un estado inicial especificado y termina en una posición que puede ser declarada ganadora, perdedora o tabla.

La problemática de los juegos siempre ha atraído el interés de los investigadores en IA. Entre los resultados más importantes están los siguientes. En 1951 Alan Turing escribió el primer programa de computadora capaz de jugar un juego completo de ajedrez; este programa nunca corrió realmente sobre una computadora. Al principio de los sesenta Arthur Samuel tuvo éxito al construir el primer programa importante y operacional para jugar; este programa jugaba a las damas y podía aprender de sus errores. Se han desarrollado diversas máquinas jugadoras de ajedrez, entre ellas la Deep Thought 2 que a mediados de esta década alcanzó un ELO de 2600 (Kasparov alcanzó 2805). El 10/02/96 el programa Deep Blue derrotó a G. Kasparov, este programa valora 50 000 millones de posiciones en tres minutos.

Entre las razones que explican este interés están:

• Proporcionan una tarea estructurada en la que es muy fácil medir éxito o fracaso.
• Las estrategias aplicables son útiles para resolver problemas complejos en diversos dominios de la vida real.
• Resulta conveniente hacer buenos programas de juegos que sirvan para medir la fortaleza de humanos.

Desde la perspectiva de un problema de búsqueda se tiene un árbol de juego que es una representación explícita de todos los posibles caminos de una partida. El nodo raíz es la posición inicial del juego, sus sucesores son las posiciones que el primer jugador puede alcanzar, los sucesores de estos nodos son las posiciones resultantes de la réplica del segundo jugador, y así sucesivamente. Los nodos terminales u hojas representan posiciones ganadoras, perdedoras o tablas. Cada camino de la raíz a un nodo terminal representa una partida completa del juego. El problema está en las dimensiones de este árbol de juego; por ejemplo, en el juego de ajedrez se ha determinado que el factor de ramificación promedio es de alrededor de 35 y que en un juego promedio cada jugador realiza 50 movimientos, por tanto para examinar el árbol del juego completo es necesario examinar 35100 posiciones.

Por lo tanto, es evidente que un programa que realice una búsqueda a ciegas no podrá seleccionar ni siquiera su primer movimiento. Es necesario algún procedimiento de búsqueda heurística. La técnica utilizada es la siguiente: desarrollar una parte del árbol de juego hasta una profundidad determinada en función de la potencia de cálculo disponible y de la estabilidad de la posición, evaluar estáticamente las posiciones alcanzadas y luego propagar hacia la raíz del árbol estos valores. Se utilizan diferentes ardides algorítmicos que permiten evaluar seriamente las jugadas posibles explorando solamente un pequeño porcentaje del árbol de búsqueda. El procedimiento de propagación hacia la raíz de los valores estimados para las hojas del árbol más conocido es el MINMAX, y el ardid más viejo para simplificar el árbol es el Alfa – Beta.

Formalización del problema.

Las seis reglas que definen un juego desde la perspectiva de la Teoría de juegos son:

1. Hay al menos dos jugadores.
2. El juego comienza por uno o más jugadores tomando una decisión entre las alternativas especificadas.
3. Después que el primer movimiento se realiza una cierta situación resulta del mismo. Esta situación determina quien hará el próximo movimiento y cuales son sus alternativas.
4. Las selecciones hechas por los jugadores pueden o no ser conocidas.
5. Si un juego se describe en términos de movimientos sucesivos, entonces hay una regla de terminación.
6. Cada juego termina en una cierta situación. Cada jugador recibe un pago.

Con respecto a la regla cuatro, si todos los jugadores conocen todas las alternativas posibles para un jugador en particular en cualquier momento, el juego se denomina juego de información perfecta.

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)= a.
Si p es ganador para Min, E(p)= – a.

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 – a: La cota de corte para un nodo Min j es una cota inferior llamada a, 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 a.

Cota – b: La cota de corte para un nodo Max j es una cota superior llamada b, 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 b.

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

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

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 a ß max [ a, v( jk; a,b) ].

3. Si a³b, return b, else continue

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

La efectividad del algoritmo a – b 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 a-b 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.

Bibliografía

Rafael Bello, Presentación Power Point, Inteligencia Artificial, Universidad Central de Las Villas, Cuba, Abril 2005.

Rafael Bello, Métodos de Solución de Problemas de la Inteligencia Artificial, Universidad Central de Las Villas, 2007.

Ivan Bratko, Prolog programming for Artificial Intelligence. Addison-Wesley Publishing Company, Reading, Mass.,1986.