Decisiones perfectas en juegos de dos participantes
Decisiones imperfectas en juegos de dos participantes
Juegos en los que interviene un elemento aleatorio
Los juegos pueden verse como
problemas de búsqueda en los que dosparticipantes compiten por llegar a un
estado meta.
Complicaciones:
*
El oponente dificulta el problema de decisión, ya que introduce la
incertidumbre (es imposible saber qué va hacer).
*
No hay tiempo para calcular las consecuencias exactas de una jugada.
Decisiones perfectas en juegos de dos participantes
Consideremos
el caso general de un juego con dos participantes, al que llamaremos Max y
Min.
Definición
formal:
*
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 donde
termina el juego se denominan estados terminales.
*
Una función de utilidad asigna un valor numérico al resultado obtenido
en un juego.
Max
tiene que definir una estrategia en la que su jugada considere todas las
posibles jugadas de Min.
Algoritmo
MiniMax (estrategia óptima
para Max)
*
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
la 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 (se asigna un
valor suponiendo que min haga lo correcto)
*
Calcular estos valores de a una capa por vez hasta llegar a la raíz.
*
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 algoritmo
minimax se supone que se dispone de todo el tiempo necesario para efectuar una búsqueda
que llegue a los estados terminales. Esto no
es del todo práctico
Por lo tanto:
*
El programa deberá suspender antes la búsqueda (Prueba-Suspensión).
*
Reemplazar la función de utilidad mediante una función de evaluación
heurística en las hojas
Las funciones de evaluación producen una estimación de la utilidad esperada de un juego correspondiente a una posición determinada. Si esta no es exacta, llevará al programa a posiciones que aparentemente son buenas, pero que en realidad son desastrosas.
Suspensión de una búsqueda
La forma más directa para controlar la cantidad de búsqueda es definir
un limite de profundidad d. Esta profundidad se elige de manera que la cantidad
de tiempo invertido en la búsqueda no exceda el tiempo asignado en el juego
para decidir la próxima jugada
Para acortar aún más los tiempos se va a dejar de explorar ramas que no
van a conducir a la solución. Al proceso de evitar la exploración de una de
las ramas del árbol se lo conoce como poda del árbol de búsqueda.
La poda
Alfa-Beta elimina todas las ramas que posiblemente no influirán en la decisión
final
Juegos en los que interviene un elemento aleatorio
En la vida
real, contrariamente a lo que sucede en el ajedrez, diversos elementos externos
impredecibles nos llevan a situaciones imprevistas.
Algunos
juegos reflejan ésta impredecibilidad al incluir un elemento aleatorio como es
el lanzamiento de dados.
Los dados se
lanzan al iniciar el turno de uno de los jugadores y se define así una
combinación de jugadas permitidas a este jugador. Si bien un jugador sabe cuáles
son sus jugadas permitidas, ignora que obtendrá el jugador rival, por lo que
ignora las jugadas que se le van a permitir. Entonces el primer jugador no podrá
construir un árbol de juego completo como el del ajedrez.
Un árbol
de juego en el backgammon deberá incluir "nodos aleatorios", además
de los nodos max y min. 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.
La
teoría de juegos no es un “juego”. Como hemos visto el resolver este tipo
problematicas encierran una gran complejidad que le permite a la IA aproximarce
a situaciones de las vida real. En un intento de derrotarse a si mismo el hombre
construye agentes que juegan igual o mejor que él mismo pudiendo llegar a decir
que piensan de forma inteligente. Todo los avances en este area pueden ser
aplicados en otros campos, como las búsquedas en Internet.
Podemos decir que la IA utiliza los juegos como un excelente campo de
investigación, con el fin de aplicar los conocimientos adquiridos a situaciones
de la vida real.