« Análisis Formal de Co… « || Inicio || » Ejercicios Lógica Dif… »

Ejercicios Minimax

Última modificación: 10 de Septiembre de 2016, y ha tenido 725 vistas

These icons link to social bookmarking sites where readers can share and discover new web pages.
  • BarraPunto
  • Del.icio.us
  • Digg
  • email
  • Facebook
  • Google
  • LinkedIn
  • PDF
  • Reddit
  • Slashdot
  • Twitter
  1. Implementad una estrategia ganadora completa en el juego del Nim en su versión más simple: se juega entre 2 jugadores, se tienen 9 cerillas, alternadamente cada jugador puede retirar 1, 2 o 3 cerillas, pierde el que retire la última cerilla.
  2. Implementad una estrategia ganadora para el juego del Nim en su versión de montones: se juega entre 2 jugadores, se tienen \(N\) montones con cerillas, cada jugador alternadamente puede quitar todas las cerillas que quiera, pero solo de un montón, gana el jugador que se lleve la última cerilla.
  3. A partir del modelo que se proporciona en el temario, introduce los cambios necesarios para conseguir implementar la poda alfa-beta.
  4. Implementad un jugador del 3 en raya que haga uso de Minimax. Hacedlo usando heurísticas sobre una profundidad máxima prefijada, y diseñando variantes que hagan uso de podas.
  5. Implementad un jugador de conecta4 haciendo uso de Minimax xon heurísticas y poda. 
  6. Consideramos el siguiente juego: dos contrincantes, A y B, manejan cada uno una ficha en un tablero como muestra la figura adjunta. Los dos jugadores mueven por turno, empezando por A. Cada jugador pueden mover su ficha a un espacio vacío adyacente a la posición que ocupen (en cualquier dirección). Si el adversario ocupa un espacio adyacente, entonces un jugador puede saltar sobre el adversario al siguiente espacio vacío, si existe. Por ejemplo, si A está sobre 3 y B está sobre 2, entonces A puede mover su ficha para ocupar el espacio 1. El juego termina cuando un jugador alcanza el extremo opuesto del tablero. Si A alcanza el espacio 5 en primer lugar, el valor de utilidad para A será \(+\infty\), si B alcanza el espacio 1 en primer lugar, el valor de utilidad de A será \(-\infty\).
    • Define una función de evaluación \(e(s)\) para un estado \(s\) cualquiera.
    • Aplica el algoritmo Minimax con límite de profundidad hasta el nivel 6, empezando con la posición de la figura anterior (empezando con el nodo raíz con etiqueta max de nivel 0, las hojas de nivel 6 también tendrán etiqueta max) y donde el primer movimiento lo hace A. Especifica los valores calculados para cada nodo y determina la mejor jugada para A.
  7. Considera el árbol en figura siguiente de un juego de dos personas, donde los círculos son nodos max y los cuadrados son nodos min. Aplica el algoritmo minimax con poda alfa-beta, propaga los valores de evaluación hasta el nodo raíz, marca la mejor jugada para max, y marca todos los subárboles que se podan.
  8. Dos jugadores, \(J_1\) y \(J_2\), se plantean competir sobre un circuito de ciudades con las siguientes reglas: 1) El recorrido del circuito se hace por tramos, partiendo de la ciudad marcada como Salida. 2) Los jugadores alternativamente eligen el tramo a recorrer entre aquellos que parten de la ciudad en la que se encuentran. Una vez elegido el tramo, ambos conductores lo recorren y se apunta los kilómetros del tramo el conductor que lo eligió. Es decir, si \(J_1\) empieza el recorrido y decide ir a B, se apuntará 30 kilómetros. A continuación el contrario debe elegir, partiendo de B, entre ir a C o a D, y se apuntará los kilómetros que separen ambas ciudades. 3) Un conductor no puede ir a una ciudad por la que ya haya pasado, por lo que la competición acaba cuando el jugador al que le toca moverse no puede hacerlo. 4) Gana el jugador que haya acumulado más kilómetros con los tramos recorridos. Se pide:
    • Da una representación eficiente para los estados del juego.
    • Desarrolla el árbol de búsqueda Minimax hasta nivel 4 (dos jugadas para cada jugador). Genera los sucesores de un nodo en orden alfabético, es decir, el primer sucesor del nodo Salida sería A y el segundo B.
    • Define una función de evaluación adecuada para los nodos hoja, y propaga sus valores a través del árbol. ¿Qué jugada haría \(J_1\)?
    • ¿Qué partes del árbol no se expandirían si se aplicara la poda?

« Análisis Formal de Co… « || Inicio || » Ejercicios Lógica Dif… »