INSTITUTO POLITÉCNICO NACIONAL

ESCUELA SUPERIOR DE INGENIERIA MECANICA ELECTRICA

UNIDAD “CULHUACAN”

INGENIERIA EN COMPUTACIÓN

PROGRAMACIÓN LOGICA

“JUEGOS”

Grupo: C6M1

10 Octubre de 2003

JUEGOS

5.1 introducción: LOS JUEGOS COMO PROBLEMAS DE BÚSQUEDA

Los juegos han ocupado la atención de las facultades intelectuales del ser humano, en ocasiones en grado alarmante. Juegos de tablero, como el ajedrez y el Go, en parte son interesantes debido a que en ellos se libra una lucha pura, abstracta, sin tener que pasar los trabajos y penas que implica organizar dos ejércitos y, con ellos, librar batallas. Esta característica de abstracción es lo que hace atractivos a los juegos para la IA. Es fácil representar el estado del juego, los agentes generalmente están restringidos a una cantidad bastante reducida de acciones bien definidas. De esta forma, los juegos constituyen una idealización de mundos en los que los agentes hostiles actúan de manera que logren disminuir nuestro bienestar.

Por otra parte, los juegos son uno de los campos de trabajo más antiguos de la I.A. En 1950, casi, en cuanto fue posible programar las computadoras, Claude Shannon, inventor de la teoría de la información, y Alan Turing elaboraron los primeros programas de ajedrez. Desde entonces, se han realizando continuos avances en el juego, al grado de que los sistemas actuales son capaces de desafían a campeones mundiales humanos sin temor de que puedan hacer el ridículo.

Los primeros investigadores eligieron para su trabajo al ajedrez por varias razones. Una computadora capaz de jugar ajedrez seria la prueba viviente de una máquina que podía realizar algo para la que se consideraba era necesario tener inteligencia. Además, la sencillez de las reglas, y el hecho de que el programa pueda acceder totalmente al estado del mundo significa que es fácil representará Juego como una búsqueda a través de un espacio de posibles posiciones de juego. De hecho, la representación en computadora del juego es correcta, en todos sus detalles, a diferencia de la representación del problema de librar una batalla, por ejemplo.

Pero lo que singulariza realmente a los juegos es que por lo común es excesivamente difícil resolverlos. El ajedrez, por ejemplo, tiene un factor de ramificación promedio de 35; las partidas frecuentemente llegan a 50 jugadas por cada contrincante, por lo que el árbol de búsqueda tiene 35100 nodos (aunque haya "sólo" aproximadamente 1040 posiciones legales distintas). Tres en línea (ta-te-ti, gato) resulta aburrido para un adulto precisamente porque es muy fácil saber cuál es la jugada adecuada. La complejidad de los juegos trae aparejado un tipo de incertidumbre totalmente nuevo, no visto hasta ahora; la incertidumbre no es consecuencia de la información faltante, sino debido a que no hay tiempo suficiente para calcular las consecuencias exactas de una jugada. Sólo se intenta deducir lo que seria lo mejor con base en experiencias pasadas y proceder, sin estar completamente seguro de cuál seria la mejor acción. En este sentido, los juegos se asemejan más al mundo real que los problemas de búsqueda estándar que hasta ahora se han estudiado.

Dado que por lo general hay un limite de tiempo, los juegos también penalizan con severidad la ineficiencia. En tanto que la implantación de una búsqueda A*, que es 10% menos eficiente, el costo de su terminación sólo implicará un valor un poco mayor, en el caso de un programa de ajedrez con 10% menos de efectividad en el uso del tiempo disponible posiblemente resulte derrotado, considerando que los demás factores son los mismos. Por ello, la investigación en los juegos ha generado una gran cantidad de interesantes ideas sobre cómo utilizar de la mejor manera el tiempo para obtener buenas decisiones, cuando la obtención de las óptimas es imposible.

La poda nos servirá para ignorar partes del árbol de búsqueda que son irrelevantes para la decisión final; las funciones de evaluación heurística nos permitirán darnos 'una idea de la verdadera utilidad de un estado sin necesidad de realizar una búsqueda completa.

DECISIONES PERFECTAS EN JUEGOS DE DOS PARTICIPANTES

Ahora consideraremos el caso general de un juego con dos participantes,-al que se denominara máx y min. MAX es el que inicia el juego, y los jugadores alternan su participación hasta que concluye el juego. Al final de éste se dan puntos al vencedor (otras veces se asignan castigos al perdedor) . Una definición formal de juego seria la de un tipo de problema de búsqueda integrado por lo siguiente:

• El estado inicial, que incluye la posición en el tablero y una indicación de a quién toca jugar.

• Un conjunto de operadores, quienes definen qué jugadas están permitidas a un jugador.

• Una prueba terminal que define el término del juego. Los estados en donde termina el juego se denominan estados terminales.

• Una función de utilidad (también conocida como función de resultado) asigna un valor numérico al resultado obtenido en un juego. En el caso del ajedrez, los resultados posibles son ganar, perder o empatar, lo que se puede representar mediante los valores numéricos +1, -1 o 0.

Si se tratara de un problema de búsqueda normal, lo único que tendría que hacer max es determinar la secuencia de jugadas que conduzca a un estado terminal ganador (de acuerdo con lo indicado por la función de utilidad), y proceder a efectuar la primera jugada de la secuencia. Desafortunadamente, en esto min también tiene algo que decir. Por lo tanto, max tiene que encontrar una estrategia que lo conduzca a un estado terminal ganador, independientemente de lo que haga min; en la estrategia de lo anterior define la jugada correcta de max considerando todas las posibles jugadas de min.

Empezaremos por mostrar cómo determinar la estrategia óptima (o racional), aun cuando normalmente no haya suficiente tiempo para calcularla.

En la figura 5.1 se muestra parle del árbol de búsqueda correspondiente al juego Tres en línea. En el estado inicial, max puede elegir nueve jugadas posibles. El juego alterna entre las X que pone max y las O que pone MIN, hasta llegar a los nodos hoja correspondientes a los estados terminales: estados en donde un jugador logra poner tres marcas en línea, o cuando se llenan todos los cuadros. El numero de cada nodo hoja indica el valor de utilidad del estado terminal desde el punto de vista de max; los valores altos se consideran buenos para max y malos para min (esta es la razón de la asignación de sus respectivos nombres). Toca a max utilizar el árbol de búsqueda (en especial, la utilidad de estados terminales) para determinar cuál es la mejor jugada.

CAPAS
MINIMAX

Incluso juegos tan simples como Tres en línea son demasiado complejos como para permitir mostrar todo el árbol de búsqueda, por lo que ahora veremos el juego totalmente trivial de la figura 5.2. Las jugadas posibles para max se identifican como A11, A12 y A13. Las posibles respuestas de min a A1 son A11 A12, A13, etcétera. El juego termina luego de que tanto max como min hacen una jugada. (En la jerga de los juegos, se dice que la profundidad del juego es de uno, consta de dos medias jugadas o dos capas.) Las utilidades de los estados terminales de este juego van de 2 a 14.

El algoritmo minimax sirve para determinar la estrategia óptima para max, y decidir así cuál es la mejor jugada. Los algoritmos se componen de cinco pasos:

• Generación de todo el árbol de juego, completamente hasta alcanzar los estados terminales.

• Aplicación de la función de utilidad a cada estado terminal y obtención de su valor respectivo

• Uso de la utilidad de los estados terminales para calcular la utilidad de los nodos del siguiente nivel superior en el árbol de búsqueda. Considérense los nodos de hoja que están en el extremo izquierdo, en la figura 5.2. En el nodo V que está arriba, min puede optar por desplazarse, y lo mejor que MIN puede hacer es escoger a11 que le produce el resultado mínimo 3.

Es decir, aunquela función de utilidad no se pueda aplicar de inmediato a este nodo " se le puede asignar el valor de utilidad 3, suponiendo que min hará lo correcto. Por un razonamiento similar, a los otros dos nodos ", se les asigna el valor de utilidad 2.

• Continuación del respaldo a los valores de los nodos hojas, en dirección a la raíz, una capa a la vez.

• Finalmente, los valores respaldados llegan a la parte superior del árbol; en ese sitio. MAX elige la jugada que le permita obtener el valor más alto. En el nodo " del extremo superior de la figura 5.2, MAX puede optar por tres Jugadas que le llevarán a estados cuya utilidad es 3, 2 y 2, respectivamente. Por lo tanto, la mejor opción de max para iniciar el Juego es a11 A esta ultima se le conoce como decisión minimax, porque permite obtener el máximo de utilidad bajo el supuesto que el oponente jugara enteramente para reducirla al mínimo.

La función del nivel superior, decisión-minimax, escoge una de las Jugadas disponibles, las que a su vez se evalúan mediante la función valor-minimax.

Si la profundidad máxima del árbol es m, y b representa las jugadas permitidas en cada punto, la complejidad en tiempo del algoritmo minimax es 0(bm). El algoritmo es una búsqueda preferente por profundidad (si bien en este caso la implantación se realiza por repetición en vez de utilizar una lista de espera de nodos) por lo que la capacidad de memoria necesitada es lineal en m y b. Desde luego que en los juegos reales es absolutamente impráctico usar el costo de tiempo, sin embargo este algoritmo es útil como punto de partida en el caso de métodos más realistas y en el análisis matemático de los juegos.

5.3DECISIONES IMPERFECTAS

El algoritmo minimax parte del supuesto de que el programa dispone de todo el tiempo necesario para efectuar una búsqueda hasta que logre llegar a los estados terminales, supuesto que por !o general no es práctico. En el primer articulo de Shannon sobre ajedrez, se proponía que en vez de llegar hasta los estados terminales utilizando la función de utilidad, el programa debería suspender antes la búsqueda y aplicar a las hojas del árbol una función de evaluación heurística. En otras palabras, se está sugiriendo modificar minimax de dos maneras: la función de utilidad se reemplaza mediante una función de evaluación eval y la prueba terminal se reemplaza por la llamada prueba-suspensión..

Funciones De Evaluación

Las funciones de evaluación producen una estimación de la utilidad esperada de un juego correspondiente a una posición determinada. Cuando Shannon la propuso, la idea no era nueva. Durante siglos, ajedrecistas (y, desde luego, aficionados a otros juegos) habían concebido diversos métodos para evaluar las posibilidades de ganar de cada participante, basándose en características fácilmente calculables de una posición. Por ejemplo, , en los libros básicos de ajedrez se asigna un valor material a cada una de las piezas: los peones valen 1, un caballo o un alfil, 3; una torre, 5; y la reina, 9. Además "una buena estructura de peones" y "la seguridad del rey", cuyo valor es, por decir algo, de medio peón. En igualdad de condiciones, aquel que tenga una segura ventaja material sobre uno o más peones es muy probable que gane el juego, una ventaja de 3 puntos es suficiente para considerar que se está próximo a la victoria segura. En la figura 5.4 se muestran cuatro posiciones y sus respectivas valoraciones.

Conviene aclarar que el desempeño de un programa para juegos depende considerablemente de la calidad de su función de evaluación. Si ésta no es exacta, llevará al programa a posiciones que aparentemente son "buenas", pero que en realidad resultan desastrosas.

¿Cómo se mide exactamente la calidad?

Primero, la función de evaluación deberá coincidir con la función de utilidad de los estados terminales. Segundo, ¡su cálculo no debe ser muy tardado, se establece un compromiso entre precisión de la función de evaluación y su respectivo costo en tiempo. Tercero, la función de evaluación deberá reflejar con precisión las posibilidades reales de poder ganar.

Qué quiere decir "posibilidades de ganar". Para dar un ejemplo concreto, supóngase que la función de evaluación sólo considera el valor material. Asi, en la posición de inicio, la evaluación es O, puesto que en ambos lados el material es el mismo. La evaluación de todas las posiciones, hasta la primera captura de una pieza, es 0. Si max logra la toma de un alfil sin perder una sola pieza, la evaluación de la posición resultante será de 3. Lo importante es que un determinado valor de la evaluación abarca a varias posiciones diferentes: todas aquellas posiciones en las que max lleva la ventaja de un alfil se agrupan dentro de una categoría a la que se asigna la etiqueta "3".

Resulta ahora claro el porqué de la palabra "posibilidad": la función de evaluación tiene que reflejar la posibilidad de que una posición escogida al azar correspondiente a esa categoría permita ganar (o empatar o perder), con base en experiencias previas.

Lo anterior estaría sugiriendo que la especificación de la función de evaluación se realice a través de las reglas de la probabilidad: si la posición A tiene 100% de posibilidades de ganar, su evaluación debe ser de 1.00; si la posición B tiene 50% de posibilidades de ganar, 25% de perder y 25% de empate, su evaluación es: +1 X .50 + -1 X .2 X + O X .25 = .25. En realidad no es necesario ser tan preciso; los valores reales de la función de evaluación no son importantes, lo que importa es que A obtenga un valor mayor que B.

En la función de evaluación de la ventaja material se parte del supuesto de que el valor de una pieza puede calcularse independientemente de las otras piezas que estén en el tablero. A este tipo de función de evaluación se le denomina función lineal ponderada, que se expresa de la siguiente manera:

W1f1 + w2f2 + ... + wnfn.

en donde las w son los pesos, las f son las características de una posición determinada. Las w serian los valores de las piezas (1 para el peón, 3 para el alfil,

etcétera) y las f serían los números de cada una de las piezas que están en el tablero. Resultara ahora más claro el porqué del valor asignado a una pieza en particular: constituyen el valor más aproximado a la posibilidad de ganar en las categorías individuales.

Suspensión De Una Búsqueda

La forma más directa de controlar la cantidad de búsqueda consiste en definir un limite de profundidad fijo, de manera que la prueba de suspensión concluya en todos los nodos que estén por encima o justo en la profundidad d. La profundidad se escoge de manera que la cantidad de tiempo invertida no exceda lo permitido por las reglas del juego. Un procedimiento un poco más sólido seria el de aplicar la profundización iterativa, como se le definió en el capitulo 3. En el momento que se agota el tiempo, el programa propone la jugada determinada durante la más profunda de las búsquedas hasta entonces llevadas a cabo. Procedimientos como éstos pueden traer aparejadas desastrosas consecuencias debido a la naturaleza aproximada de la función de evaluación. Considérese nuevamente la sencilla función de evaluación para el ajedrez que se basa en la ventaja material. Supóngase que. el programa efectúa la búsqueda hasta el limite de profundidad, y llega a la posición que se muestra en al figura 5.4(d).

De acuerdo con la función material, el blanco lleva ventaja por un caballo y es casi seguro que ganara. Sin embargo, ahora es el tumo de las negras y la reina blanca está perdida puesto que el caballo negro está en posibilidad de tomarla, sin ninguna ganancia para las blancas. Asi pues, en realidad la posición es de triunfo para las negras, lo que sólo se puede ver anticipándose una capa o media jugada más.

La función de evaluación podrá utilizarse sólo en el caso de posiciones que están en reposo, es decir, aquellas cuyos valores es poco probable que sufran grandes fluctuaciones en. un futuro cercano. Por ejemplo, en el ajedrez no se consideran en reposo aquellas posiciones en que se pueden efectuar capturas de piezas a favor en funciones de evaluación en las que sólo se considera la ventaja material.

Se pueden expandir posiciones que no están en reposo hasta obtener posiciones en reposo. A esta búsqueda adicional se le denomina búsqueda de reposo; a veces se le restringe a tomar en cuenta sólo cierto tipo de jugadas, como las de captura de pieza, lo que despeja de inmediato las incertidumbres de una posición.

Es más difícil eliminar el problema de horizonte. Surge cuando el programa enfrenta una jugada del contrincante que causa un grave daño y que finalmente es inevitable. Considérese el juego de ajedrez de la figura 5.5.

Juegan las negras

Figura 5.5 El problema del horizonte. La serie de jaques de la torre negra fuerzan la inevitable Jugada de coronación de las blancas "encima del horizonte" y parecería que esta posición es ligeramente más ventajosa para las negras, cuando en realidad es seguro el triunfo de las blancas.

Las negras tienen una ligera ventaja material, pero si las blancas logran avanzar su peón de la fila séptima a la octava, se convertirá en reina y será muy fácil que las blancas ganen. Las negras podrían anticipar lo anterior a través de una docena de capas, verificando la situación de las blancas en relación con la torre, pero lo que será inevitable es que el peón se convierta en reina.

5.4 poda ALFA-BETA

Supongamos que se ha logrado implantar una búsqueda minimax que cuenta con una función de evaluación razonable para el ajedrez y una razonable prueba de suspensión con una búsqueda de reposo Contando con un programa bien elaborado, y una computadora normal, probablemente se podrán buscar 1000 posiciones por segundo. ¿Qué tan bien jugará el programa? En los torneos de ajedrez, se dispone de unos 150 segundos para cada jugada, por lo que hay tiempo para explorar 150,000 posiciones.

En el caso del ajedrez, el factor de ramificación es de aproximadamente 35, es decir, el programa sólo podrá explorar tres o cuatro capas y su juego tendrá el nivel de ¡novato! Incluso los jugadores humanos promedio pueden anticipar sus jugadas seis u ocho capas: nuestro programa perdería sin mayor dificultad.

Afortunadamente es posible calcular la decisión minimax correcta sin tener que explorar todo los nodos del árbol de búsqueda. Al proceso para evitar la exploración de una de las ramas del árbol de búsqueda se le conoce como poda del árbol de búsqueda. A la técnica que consideraremos en particular se le conoce como poda alfa-beta. Aplicada a un árbol minimax estándar, produce la mismo jugada que se obtendría con minimax, pero elimina todas las ramas que posiblemente no influirán en la decisión final.

Considérese el árbol de juego de dos capas de la figura 5.6.

La búsqueda procede como en el caso anterior: A1, luego A11, A12, A12; el nodo que esta bajo a1 tiene valor minimax de 3. Ahora continuamos con A2 y A21, cuyo valor es de 2. Podemos darnos cuenta ahora de que si ma-x juega A;, min tiene la opción de llegar a la posición que vale 2, así como otras opciones cercanas. Así, ya es posible concluir que la jugada A2 para max es como máximo 2 Como ya sabemos que la jugada A1 vale 3, no tiene caso seguir buscando más debajo de A2. Es decir, en este sitio se poda el árbol de búsqueda, y podemos estar seguros de que dicha poda no repercutirá en el resultado.

El principio general es el siguiente: considérese un nodo n del árbol (véase la figura 5.7). 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 m 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. Sea a el valor de la mejor opción encontrada hasta entonces en un punto de elección a través de la ruta de max y sea  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 de min. Conforme se efectúa la búsqueda alfa-beta se van actualizando los valores de  y  y se poda un subárbol (es decir, concluye la solicitud de repetición) en cuanto se determina que es peor que el valor actual de  y  .

La descripción del algoritmo de la figura 5.8 se divide en las funciones valor-ma-x y valor-min. Las funciones anteriores se aplican a los nodos max y min, respectivamente, aunque el efecto de ambas es el mismo: devolver el valor minimax del nodo, excepto en el caso de nodos que hay que podar (en cuyo caso de todas formas se ignora el valor producido). La función de búsqueda alfa-beta es en sí una copia de la función valor-max, con un código adicional para recordar y responder con la mejor jugada que se haya encontrado.

Eficiencia De La Poda Alfa-Beta

La eficiencia de alfa-beta dependerá del orden como se exploren los sucesores. Esto es muy claro en el caso de la figura 5.6, en la que no es posible podar a3 puesto que se generaron primero Á31 y A32 (las peores jugadas desde el punto de vista de min). Lo anterior parece indicar que es mejor primero explorar aquellos sucesores que aparentemente tienen más posibilidades de ser los mejores.

Knuth y Moore (1975) fueron los primeros en analizar a fondo la eficiencia de la poda alfa-beta. Así como el mejor de los casos explicado en el párrafo anterior, analizaron también el caso en que los sucesores se ordenan aleatoriamente. La complejidad asintótica es 0((b/\og b)d ), al parecer desconsoladora puesto que el factor de ramificación efectivo b/logb no es significativamente menor que b mismo. Por otra parte, la fórmula asintótica es exacta sólo cuando b > 1 000, aproximadamente; es decir, no todos los juegos pueden desarrollarse razonablemente bien al utilizar estas técnicas. En el caso de una b razonable, la cantidad total de nodos explorados será aproximadamente de 0(b3d/4). En la práctica, mediante una función de ordenamiento muy sencilla (como sería el probar primero la captura, luego la amenaza, luego las jugadas de avance y las de retroceso) es posible aproximarse bastante al re-sultado del mejor caso, en vez del resultado aleatorio.

5.5 juegos EN LOS QUE INTERVIENE UN ELEMENTO ALEATORIO

En la vida real, contrariamente a lo que sucede en el ajedrez, diversos elementos extremos impredecibles nos llevan a situaciones imprevistas. Algunos juegos reflejan esta impredecibilidad al incluir un elemento aleatorio como es el lanzamiento de dados. Por ello, nos aproximan un poco más a las condiciones prevalecientes en la realidad, por lo que valdría la pena examinar de qué manera tales elementos afectan un proceso de toma de decisiones.

El backgammón es el prototipo del juego que a una suerte y destreza. Los dados se lanzan al inicio del tumo de uno de los jugadores y se define así una combinación de jugadas permitidas a este juego.

Un árbol de juego en el backgammon deberá incluir nodos aleatorios, además de los nodos max y min. En la figura 5.10 se indica a los nodos aleatorios mediante círculos. Cada una de las ramas que sale de un nodo aleatorio denota el posible resultado del lanzamiento de un dado, a cada uno de ellos lo acompaña dicho resultado y la posibilidad de que ocurra.

Las posibles posiciones ya no tienen un valor minimax definido (que en el caso de los juegos deterministas era la utilidad de la hoja a la que se llegaba por la mejor jugada). Lo único que se puede calcular es un promedio o valor esperado, calculado como un promedio de los posibles resultados del lanzamiento de los dados.

El cálculo de los valores esperados de los nodos es directo. Para los nodos terminales se utiliza la función de utilidad, como en el caso de los juegos deterministas Avanzando un paso en el árbol de búsqueda se llega a un nodo aleatorio. En la figura 5.10 los nodos aleatorios son circuios; fijémonos en el que está identificado como C. Sea d¡ el pasible resultado del lanzamiento de un dado y P (di) la posibilidad o probabilidad de que se obtenga tal resultado. Se calcula la utilidad de la mejor jugada para min correspondiente a cada lanzamiento de dados y se añaden las utilidades, ponderadas con la probabilidad de obtención de un determinado lanzamiento de dados. Si S (C, d,) denota el conjunto de posiciones generadas por la aplicación de jugadas permitidas al lanzamiento de dados P (d,) a la posición de C, se podrá calcular el denominado valor esperado max de C, mediante la fórmula:

esperadomax(C) = " P(d¡) max ;€ s(C,di)(utilidad(s))

Ascendiendo un nivel más a los nodos min V en la figura 5.10), ahora es posible aplicarla fórmula del valor minimax normal, en virtud de haber asignado valores de utilidad a todos los nodos aleatorios.

Evaluación De La Posición En Juegos Que Tienen Nodos Aleatorios

Al igual que en el caso de minimax, la aproximación que obviamente habrá que efectuar en el caso del minimax esperado consiste en suspender la búsqueda en algún momento y proceder a aplicar una función de evaluación a las hojas. Podría pensarse que las funciones de evaluación para juegos tales como el backgammon no son distintas, en principio, de las funciones de evaluación del ajedrez: deberían otorgar calificaciones mayores a las mejores posiciones.

El hecho de que haya nodos aleatorios implica la necesidad de tener más cuidado en la interpretación de los valores de evaluación, una transformación conservadora del orden de los valores de hoja no afecta a la elección de la jugada.

Esto nos permite contar con mucha libertad en el diseño de la función de evaluación: funcionaria en tanto que las posiciones con evaluaciones superiores conduzcan con más frecuencia al triunfo.

En el caso de "los nodos aleatorios se pierde esta libertad”. En la figura 5.11 se muestra lo que sucede: si los valores de hoja son 1, 2, 3, 4, la mejor de las jugadas es Ai; si los valores son 1, 20, 30 400, la mejor es A2. Es decir, el programa se comporta de manera enteramente distinta cuando se efectúa un cambio en la escala de valores de evaluación, con el fin de eliminar la sensibilidad anterior, la función de evaluación sólo deberá ser una transformación lineal positiva de la posibilidad de ganar en una posición determinada.

Complejidad Del Valor Minimax Esperado

Dado que el minimax esperado también toma en consideración todas las posibles secuencias del lanzamiento de dados, se demorará O(bm nm), en donde n es la cantidad de lanzamientos distintos.

La ventaja de alfa-beta es que hace caso omiso de acontecimientos futuros que sencillamente no se van a producir.

Lo que alfa-beta tiene que hacer antes de podar un nodo en el subárbol correspondiente. Aparentemente parece imposible, debido a que el valor de C es el promedio de los valores de sus hijos, y hasta que no se hayan visto todos los lanzamientos de dados, este promedio podría ser nada, debido a que el valor de los hijos no explorados podría ser cualquiera, si se ponen límites a los posibles valores de la función de utilidad, seria posible determinar límites para el promedio.

5.6 LO ÚLTIMO EN PROGRAMAS DE JUEGOS

Ajedrez

El ajedrez es el juego que ha recibido con creces buena parte del interés por los juegos. Si bien no han logrado cumplir lo anunciado por Shanon en 1957 en el sentido de que 10 años después las computadoras serían capaces de derrotar a quien fuese el campeón humano de ajedrez, si se encuentran muy cerca de lograrlo. En el ajedrez de velocidad, las computadoras derrotaron al campeón mundial, Gary Kasparov, tanto en los juegos con duración de cinco minutos como en los de 25 minutos; hasta el momento de escribir estas líneas, en los torneos de juegos de duración completa, las computadoras sólo han logrado ocupar un lugar entre los cien mejores jugadores del mundo. En la figura 5.12 se muestra el puntaje obtenido a través del tiempo por humanos y computadoras campeones.

Algunos programas de principios de los años 70 eran demasiado complicados, contaban con diversos trucos para eliminar algunas ramas de búsqueda, para generar jugadas posibles, etc.; pero en los programas que ganaron los Campeonatos de Ajedrez por Computadora de Estados Unidos de la ACM (iniciados en 1970) se favorecía el uso de la búsqueda alfa-beta directa, complementada por la consulta en libros de aperturas e infalibles algoritmos de fin de juego.

El primer avance notable en eficiencia se debió no a mejores algoritmos o funciones de evaluación, sino al hardware. Belle, la primera computadora especialmente diseñada para jugar ajedrez (Condón y Thompson, 1982) utilizó circuitos integrados para implantar la generación de jugadas y la evaluación de posiciones, lo que permitía la exploración de varios millones de posiciones antes de hacer una sola jugada.

El sistema hitech, también una computadora especialmente para esta aplicación, su objetivo era el rápido cálculo de complejas funciones de evaluación.

Capaz de generar aproximadamente diez millones de posiciones por jugada y utilizando probablemente la más precisa evaluación de posiciones diseñada hasta ese entonces.

El mejor sistema actualmente es Deep Thought 2, donde se utiliza una sencilla función de evaluación, explora casi 5,000 millones de posiciones por jugada, con lo que logra alcanzar profundidades de 10 u 11 y cuenta con una función que le permite seguir la línea de jugadas forzadas aun más lejos (en una ocasión encontró un jaque mate de 37 jugadas). Donde compitió contra el equipo olímpico danés y le ganó 3-1, derrotó a uno de los grandes maestros y con el otro empató.

En la siguiente versión del sistema, Deep Blue, se utiliza un arreglo en paralelo de 1,024 chips, lo cual le permite explorar el equivalente de 10,000 posiciones por segundo (de 1 a 2 billones por cada jugada) y alcanzar profundidades de 14.

Juegos De Fichas O Damas

Arthur Samuel de la IBM, durante sus ratos libres desarrolló un programa para jugar a las damas capaz de obtener por si mismo su función de evaluación mediante lo aprendido a través de miles de juegos ejecutados por el programa mismo.

El programa de Samuel empezó con nivel de novato, pero luego de algunos días de jugar consigo mismo, logró competir al mismo nivel en duros torneos con contendientes humanos. Si se toma en cuenta que el equipo de cómputo con el que trabajaba Samuel (una IBN' 704) contaba con 10 000 palabras de memoria principal, cinta magnética para almacenamiento de largo plazo y un ciclo de tiempo de casi un milisegundo, se podrá apreciar por qué se le considera como uno de los grandes logros de la IA.

Othello

Othello, también conocido como Reversi, posiblemente sea un juego más popular en su versión de computadora que en la de tablero. Su espacio de búsqueda es más reducido que el del ajedrez, por lo general sólo tiene de 5 a 15 jugadas aceptadas, sin embargo la experiencia para la evaluación tiene que obtenerse a partir de cero. Con todo, los programas de Othello en las computadoras normales son mucho mejores que los humanos, quienes por lo general se rehúsan a librar contiendas directas en los torneos.

Backgammon

El elemento de incertidumbre que introduce el lanzamiento de dados en el juego del backgammon hace de la búsqueda un lujo muy costoso. El primer programa que tuvo repercusión, BK.G, utilizaba sólo búsqueda de una capa, aunque la función de evaluación era bastante compleja.

Más recientemente, Gerry Tesauro combinó el método de aprendizaje de Samuel con las técnicas de las redes neurales para crear una nueva función de evaluación. Su programa está considerado sin lugar a dudas entre los tres mejores jugadores del mundo.

Go

Go es el juego de mesa más popular en Japón, y sus profesionales necesitan de tanta disciplina como en el caso del ajedrez. El factor de ramificación se aproxima a 360, por lo que los métodos normales de búsqueda no sirven de nada. Los que ofrecen ciertas posibilidades son los sistemas basados en completas bases de conocimiento de reglas que propongan aquellas jugadas que pudieran ofrecer alguna posibilidad, aunque la calidad de los juegos así realizados todavía es bastante mala. En especial considerando el premio de dos millones de dólares al programa que logre derrotar a uno de los mejores jugadores, Go es un área con posibilidades de obtener los beneficios de profundas investigaciones utilizando métodos de razonamiento más complejos.

5.7 COMENTARIO

Puesto que en la mayoría de los casos es. Muy difícil trabajar el cálculo de decisiones óptimas en los juegos, todos los algoritmos tienen que hacer ciertas idealizaciones y aproximaciones. El método estándar, basado en minimax, las funciones de evaluación y alfa-beta, sólo una forma de hacerlo. Posiblemente debido a que fueron de las primeras propuestas, su diseño recibió tanta atención y es el predominante entre otros métodos en los juegos de torneo Algunos en este campo consideran que lo anterior ha provocado que el juego se haya divorciado de las principales áreas de la investigación en IA: el método estándar ya no tiene mucho que ofrecer en cuanto a nuevos métodos para responder a la interrogantes generales de la toma de decisiones.

Considérese primero a minimax. Es un método óptimo para escoger una jugada de un determinado árbol de búsqueda, siempre y cuando las evaluaciones del nodo hoja sean correctas con exactitud. En realidad, las evaluaciones por lo general son estimaciones burdas del valor de una posición. Para elegir, minimax se basa en el hecho de que todos los nodos identificados-con valores 100, 101, 102 y 100 son en realidad mejores que el nodo identificado con el valor 99. Una manera de resolver el problema anterior es por medio de una evaluación que produzca una distribución de probabilidad correspondiente a todos los valores posibles. De esta manera se puede calcular la distribución de probabilidad del valor del padre utilizando técnicas estadísticas estándar. Desafortunadamente, los valores de los nodos hermanos por lo general guardan estrecha correlación entre si. Por la que el cálculo respectivo puede resultar bastante caro y necesitaría de una detallada información sobre la correlación, información que es difícil obtener.

Este tipo de razonamiento acerca de lo que se obtiene mediante un cálculo se denomina metarrazonamiento (razonar acerca del razonamiento). Tiene que ver no sólo con los juegos, sino con todo tipo de razonamiento en general. Todos los cálculos se realizan con el fin de encontrar mejores decisiones, todas implican costos y todas tienen cierta posibilidad de producir alguna mejora en la calidad de las decisiones efectuadas. En alfa-beta se cuenta con la más sencilla de las clases de metarrazonamiento: un teorema que permite ignorar ciertas ramas de un árbol sin causar una pérdida. Es posible hacer todavía cosas mejores. parten del estado inicial y luego aplican una función de evaluación. Desde luego que ésta no es la manera como juegan los humanos. En el ajedrez, se tiene presente una meta determinada (por ejemplo, capturar la reina del contrincante), objetivo que se utiliza para generar de manera selectiva planes factibles para su logro. Este tipo de razonamiento o planificación enfocado a una meta permite en ocasiones eliminar la búsqueda de combinaciones (véase la parte IV). El programa paradise de David Wiikins (1980) es el único programa de ajedrez que tuvo éxito en el empleo del razonamiento enfocado a una meta. Fue capaz de resolver problemas de ajedrez en los que intervenían combinaciones de 18 jugadas

2