Es estado de un juego resulta muy fácil de representar, ya que 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.
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 sería lo mejor con base en experiencias pasadas y proceder, sin estar completamente seguro de cuál sería la mejor acción. En este sentido, los juegos se asemejan más al mundo real que a los problemas de búsqueda estándar.
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.
Una función de utilidad
(también conocida como función de resultado) asigna un valor numérico al
resultado obtenido en un juego.
Consideremos el caso general
de un juego con dos participantes: a los que se denominará MAX y MIN, MAX tiene
que determinar la secuencia de jugadas que conduzca a un estado terminal
ganador, y proceder a efectuar la primera jugada de la secuencia. MAX tiene que
encontrar un estrategia que defina la jugada correcta considerando las posibles
jugadas de MIN.
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 lo general no es práctico, ya que se debe generar todo el árbol de juego y aplicar la función de utilidad en cada estado terminal.
Para solucionar esto se sugirió modificar minimax de forma que la función de utilidad se reemplazara mediante una función de evaluación y la prueba terminal se reemplazará por una prueba de suspensión.
Tanto una - la poda alfa - como la otra - la poda beta - son métodos para limitar la búsqueda en los árboles de búsqueda del algoritmo MiniMax, basados en considerar racionalmente que es inútil explorar la totalidad de la estructura del árbol decisional, porque ni a "mí" ni a "mi contrincante" nos va a convenir introducirnos en algunas de las ramificaciones, pues están dominadas ya sea para mí (poda alfa), ya sea para el contrincante (poda beta).
Impredecibilidad
El backgammon es el prototipo del juego que une suerte y destreza. Si bien el jugador de las fichas blancas sabe cuáles son las jugadas permitidas, ignora que obtendrá el jugador de las fichas negras, por lo que ignora cuáles serán las jugadas que se le permiten. Por lo tanto, las blancas no pueden construir un árbol de juego completo como el del ajedrez.
Nodos aleatorios
Un árbol de juego en el backgammon deberá incluir nodos aleatorios. Cada una de las ramas que sale de un nodo aleatorio denota el posible resultado del lanzamiento de un dado.
Valor esperado
El paso siguiente consiste en saber cómo tomar las decisiones correctas. Las posibles posiciones ya no tienen un valor minimax definido, lo único que se puede calcular es un promedio o valor esperado, calculado como un promedio de los posibles resultados del lanzamiento de dados.
Evaluación de posición en juegos que tienen nodos aleatorios
Al igual que en el caso de minimax, se suspende la búsqueda en algún momento y se procede 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.
En realidad, 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. En mínimas, una transformación del orden de los valores de hoja no afecta a la elección de la jugada. Con nodos aleatorios el programa se comporta de manera distinta si se efectúa un cambio en la escala de valores.
Complejidad del valor minimax esperado
Si el programa supiera de antemano cuáles serán los resultados del lanzamiento de los dados que se obtendrán durante el juego, se resolvería el juego de igual manera que si no hubiese dados, lo que minimax puede hacer en un lapso de O(b^m). Dado que el minimax esperado también toma en consideración el lanzamiento de dados, demorará O=(b^m n^m), en donde n es la cantidad de lanzamientos distintos.
El diseñar programas para juegos persigue un propósito doble: comprender mejor cómo escoger una acción en medio de dominios complejos con resultados inciertos y el diseño de sistemas de alto rendimiento para el juego estudiado en particular.
Ajedrez
En 1957 Shanon dijo que luego de 10 años las computadoras serían capaces de derrotar a quien fuese el campeón humano de ajedrez, no fue así, pero se encuentran 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. En los programas que ganaron los Campeonatos de Ajedrez por Computadora de Estados Unidos de la ACM se favorecía el uso de la búsqueda alfa-beta. El primer avance notable en eficiencia se debió no a mejores algoritmos o funciones de evaluación, sino al hardware. El mejor sistema actualmente es Deep Thought 2. Patrocinado por IBM, 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 funcion que le permite seguir la línea de jugadas forzadas aún mas lejos.
La siguiente versión del sistema es Deep Blue, se utiliza un arreglo en paralelo de 1,024 chips VSLI especialmente diseñados para esta aplicación, lo cual le permite explorar el equivalente de 10,000 posiciones por segundo y alcanzar profundidades de 14.
Juegos de fichas o damas
A principios de 1952, Arthur Samuel de la IBM, desarrollo 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. Posteriormente contó con mejoras, un ejemplo es Chinook, ejecutable en computadoras normales utilizando la búsqueda alfa-beta. Ganó el torneo abierto de Estados Unidos de 1992, y se convirtió así en el primer programa que oficialmente contendiera en un campeonato mundial real. Usa bases de datos con evaluación perfecta cuando solo quedan 8 (o menos) fichas , es devastadora al llegar a ese punto. Cubre 443.748.401.247 posiciones.
Othello
Tambien 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
En 1980 el primer programa que tuvo repercusión , “BKG”, derrotó al campeón mundial por 5 a 1 ya que tuvo suerte en los dados. Cometió algunos pocos errores mientras el campeón no cometió ninguno. Desde entonces esos errores fueron disminuyendo. Es un juego de estrategia y el programa imita las estrategias humanas.. En 1992 Gerry Tesauro desarrolla un programa que combina una red neural y el método de aprendizaje de Samuel que está entre los tres mejores jugadores.
Go
Es el juego de mesa más popular en Japón, y sus profesionales necesitan de tanta disciplilna 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 area con posibilidades de obtener los beneficios de profundas investigaciones utilizando métodos de razonamiento más complejos.
