- Formalización del problema
- Procedimiento Minimal
- Procedimiento Alfa – Beta
- El juego de ajedrez
- Bibliografía
Problemática de los juegos
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.
| Página siguiente |