El Juego TicTacToe (Gato) mediante Arboles de Decisiones
-
Upload
jose-enrique-alvarez-estrada -
Category
Documents
-
view
8.887 -
download
10
Transcript of El Juego TicTacToe (Gato) mediante Arboles de Decisiones
![Page 1: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/1.jpg)
Análisis y Simulaciónde Decisiones
José Enrique Alvarez Estrada
Basado en un material elaborado por el Prof. Luigi Ceccaroni
![Page 2: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/2.jpg)
Juegos
La teoría de juegos es un área de la matemática aplicada que utiliza modelos para estudiar interacciones en estructuras formalizadas de incentivos (los llamados juegos) y llevar a cabo procesos de decisión
![Page 3: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/3.jpg)
Juegos
• Los juegos más simples que se estudian en Toma de Decisiones son aquellos:– De suma cero (lo que uno gana, el otro lo pierde y
viceversa)– De dos jugadores (jugador MAX, jugador MIN)– Por turnos– De información perfecta (ajedrez, damas, tres en raya,
etc.) – O de información imperfecta (poker, stratego, bridge...)
– Deterministas
![Page 4: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/4.jpg)
Juegos
• Los juegos son interesantes porque son demasiado difíciles de resolver.
• El ajedrez, por ejemplo, tiene un factor de ramificación promedio de 35 y los juegos van a menudo a 50 movimientos por cada jugador:– grafo de búsqueda: aproximadamente 1040 nodos
distintos– árbol de búsqueda: 35100 o 10154 nodos
• Como en el mundo real, se requiere de tomar alguna decisión (la jugada) cuando es infactible calcular la decisión óptima.
![Page 5: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/5.jpg)
5
Decisiones óptimas en juegos
• Un juego puede definirse formalmente mediante:– Un estado inicial– Una función sucesor, que devuelve una lista
de pares (movimiento, estado)– Una prueba terminal, que determina cuándo
termina el juego (por estructura o propiedades o función utilidad)
– Una función utilidad
5
![Page 6: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/6.jpg)
Búsqueda exhaustiva
![Page 7: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/7.jpg)
Búsqueda exhaustiva• Aproximación trivial: generar todo el árbol
de jugadas.• Se etiquetan las jugadas terminales,
dependiendo de si gana MAX o MIN, con un valor de utilidad de, por ejemplo, “+1” o “-1”.
• El objetivo es encontrar un conjunto de movimientos accesible que dé como ganador a MAX.
• Se propagan los valores de las jugadas terminales de las hojas hasta la raíz.
• Incluso un juego simple como tic-tac-toe es demasiado complejo para dibujar el árbol completo
![Page 8: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/8.jpg)
Búsqueda exhaustiva
![Page 9: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/9.jpg)
Búsqueda exhaustiva
![Page 10: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/10.jpg)
Búsqueda exhaustiva• Aproximación heurística: definir una
función que nos indique lo cerca que estamos de una jugada ganadora (o perdedora).
• En esta función interviene información del dominio.
• Esta función no representa ningún coste, ni es una distancia en pasos.
• El algoritmo busca con profundidad limitada.
• Cada nueva decisión por parte del adversario implicará repetir parte de la búsqueda.
![Page 11: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/11.jpg)
Ejemplo: tic-tac-toe
e = PMAX
- PMIN
donde:
– e = función utilidad
– PMAX
= número de filas, columnas y diagonales completas disponibles
para MAX
– PMIN
= número de filas, columnas y diagonales completas disponibles
para MIN
• MAX juega con ✘ y desea maximizar e
• MIN juega con O y desea minimizar e
• Valores absolutos altos de e: buena posición para el que tiene que mover
• Controlar las simetrías
• Utilizar una profundidad de parada (en el ejemplo: 2)
![Page 12: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/12.jpg)
tic-tac-toe: jugada #1
![Page 13: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/13.jpg)
tic-tac-toe: jugada #1
juega MAX
![Page 14: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/14.jpg)
tic-tac-toe: jugada #1
6-5=1
juega MIN
![Page 15: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/15.jpg)
tic-tac-toe: jugada #1
6-5=1 5-5=0
![Page 16: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/16.jpg)
tic-tac-toe: jugada #1
6-5=1 5-5=0 6-5=1
![Page 17: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/17.jpg)
tic-tac-toe: jugada #1
6-5=1 5-5=0 6-5=1 5-5=0
![Page 18: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/18.jpg)
tic-tac-toe: jugada #1
6-5=1 5-5=0 6-5=1 5-5=0 4-5=-1
![Page 19: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/19.jpg)
tic-tac-toe: jugada #1
MIN = -1
6-5=1 5-5=0 6-5=1 5-5=0 4-5=-1
![Page 20: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/20.jpg)
tic-tac-toe: jugada #1
MIN = -1
6-5=1 5-5=0 6-5=1 5-5=0 4-5=-1
juega MAX
![Page 21: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/21.jpg)
tic-tac-toe: jugada #1
MIN = -1
6-5=1 5-5=0 6-5=1 5-5=0 4-5=-1 5-4=1
juega MIN
![Page 22: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/22.jpg)
tic-tac-toe: jugada #1
MIN = -1
6-5=1 5-5=0 6-5=1 5-5=0 4-5=-1 5-4=1 6-4=2
![Page 23: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/23.jpg)
tic-tac-toe: jugada #1
MIN = -1
6-5=1 5-5=0 6-5=1 5-5=0 4-5=-1
MIN = 1
5-4=1 6-4=2
![Page 24: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/24.jpg)
tic-tac-toe: jugada #1
MIN = -1
6-5=1 5-5=0 6-5=1 5-5=0 4-5=-1
MIN = 1
5-4=1 6-4=2
juega MAX
![Page 25: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/25.jpg)
tic-tac-toe: jugada #1
MIN = -1
6-5=1 5-5=0 6-5=1 5-5=0 4-5=-1 5-6=-1
MIN = 1
5-4=1 6-4=2
juega MIN
![Page 26: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/26.jpg)
tic-tac-toe: jugada #1
MIN = -1
6-5=1 5-5=0 6-5=1 5-5=0 4-5=-1 5-6=-1 6-6=0
MIN = 1
5-4=1 6-4=2
![Page 27: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/27.jpg)
tic-tac-toe: jugada #1
MIN = -1
6-5=1 5-5=0 6-5=1 5-5=0 4-5=-1 5-6=-1 6-6=0 6-6=0
MIN = 1
5-4=1 6-4=2
![Page 28: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/28.jpg)
tic-tac-toe: jugada #1
MIN = -1
6-5=1 5-5=0 6-5=1 5-5=0 4-5=-1 5-6=-1 6-6=0 6-6=0 5-6=-1
MIN = 1
5-4=1 6-4=2
![Page 29: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/29.jpg)
tic-tac-toe: jugada #1
MIN = -1
6-5=1 5-5=0 6-5=1 5-5=0 4-5=-1 5-6=-1 6-6=0 6-6=0 5-6=-1 4-6=-2
MIN = 1
5-4=1 6-4=2
![Page 30: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/30.jpg)
tic-tac-toe: jugada #1
MIN = -1
6-5=1 5-5=0 6-5=1 5-5=0 4-5=-1 5-6=-1 6-6=0 6-6=0 5-6=-1 4-6=-2
MIN = 1 MIN = -2
5-4=1 6-4=2
![Page 31: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/31.jpg)
tic-tac-toe: jugada #1
MIN = -1
6-5=1 5-5=0 6-5=1 5-5=0 4-5=-1 5-6=-1 6-6=0 6-6=0 5-6=-1 4-6=-2
MIN = 1 MIN = -2
5-4=1 6-4=2
![Page 32: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/32.jpg)
tic-tac-toe: jugada #1
MIN = -1
MAX = 1
6-5=1 5-5=0 6-5=1 5-5=0 4-5=-1 5-6=-1 6-6=0 6-6=0 5-6=-1 4-6=-2
MIN = 1 MIN = -2
5-4=1 6-4=2
![Page 33: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/33.jpg)
tic-tac-toe: jugada #1
MIN = -1
MAX = 1
6-5=1 5-5=0 6-5=1 5-5=0 4-5=-1 5-6=-1 6-6=0 6-6=0 5-6=-1 4-6=-2
MIN = 1 MIN = -2
5-4=1 6-4=2
Por tanto, la mejor jugada de MAX es
![Page 34: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/34.jpg)
tic-tac-toe: jugada #1
MIN = -1
MAX = 1
6-5=1 5-5=0 6-5=1 5-5=0 4-5=-1 5-6=-1 6-6=0 6-6=0 5-6=-1 4-6=-2
MIN = 1 MIN = -2
5-4=1 6-4=2
tras lo cual MINdebería jugar
![Page 35: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/35.jpg)
tic-tac-toe: jugada #2
![Page 36: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/36.jpg)
tic-tac-toe: jugada #2
juegaMAX
![Page 37: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/37.jpg)
tic-tac-toe: jugada #24-2=2
juegaMIN
![Page 38: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/38.jpg)
tic-tac-toe: jugada #24-2=2
3-2=1
![Page 39: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/39.jpg)
tic-tac-toe: jugada #24-2=2
3-2=1
5-2=3
![Page 40: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/40.jpg)
tic-tac-toe: jugada #24-2=2
3-2=1
5-2=3
2-2=0
![Page 41: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/41.jpg)
tic-tac-toe: jugada #24-2=2
3-2=1
5-2=3
2-2=0
4-2=2
![Page 42: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/42.jpg)
tic-tac-toe: jugada #24-2=2
3-2=1
5-2=3
2-2=0
4-2=2
3-2=1
![Page 43: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/43.jpg)
MIN = 0
tic-tac-toe: jugada #24-2=2
3-2=1
5-2=3
2-2=0
4-2=2
3-2=1
![Page 44: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/44.jpg)
MIN = 0
tic-tac-toe: jugada #24-2=2
3-2=1
5-2=3
2-2=0
4-2=2
3-2=1
juegaMAX
![Page 45: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/45.jpg)
MIN = 0
tic-tac-toe: jugada #24-2=2
3-2=1
5-2=3
2-2=0
4-2=2
3-2=1
4-3=1
juegaMIN
![Page 46: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/46.jpg)
MIN = 0
tic-tac-toe: jugada #24-2=2
3-2=1
5-2=3
2-2=0
4-2=2
3-2=1
4-3=1 3-3=0
![Page 47: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/47.jpg)
MIN = 0
tic-tac-toe: jugada #24-2=2
3-2=1
5-2=3
2-2=0
4-2=2
3-2=1
4-3=1 3-3=0 5-3=2
![Page 48: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/48.jpg)
MIN = 0
tic-tac-toe: jugada #24-2=2
3-2=1
5-2=3
2-2=0
4-2=2
3-2=1
4-3=1 3-3=0 5-3=2 3-3=0
![Page 49: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/49.jpg)
MIN = 0
tic-tac-toe: jugada #24-2=2
3-2=1
5-2=3
2-2=0
4-2=2
3-2=1
4-3=1 3-3=0 5-3=2 3-3=0 4-3=1
![Page 50: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/50.jpg)
MIN = 0
tic-tac-toe: jugada #24-2=2
3-2=1
5-2=3
2-2=0
4-2=2
3-2=1
4-3=1 3-3=0 5-3=2 3-3=0 4-3=1 4-3=1
![Page 51: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/51.jpg)
MIN = 0
MIN = 0
tic-tac-toe: jugada #24-2=2
3-2=1
5-2=3
2-2=0
4-2=2
3-2=1
4-3=1 3-3=0 5-3=2 3-3=0 4-3=1 4-3=1
![Page 52: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/52.jpg)
MIN = 0
MIN = 0
tic-tac-toe: jugada #24-2=2
3-2=1
5-2=3
2-2=0
4-2=2
3-2=1
4-3=1 3-3=0 5-3=2 3-3=0 4-3=1 4-3=1
juegaMAX
![Page 53: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/53.jpg)
MIN = 0
MIN = 0
tic-tac-toe: jugada #24-2=2
3-2=1
5-2=3
2-2=0
4-2=2
3-2=1
4-2=2
4-3=1 3-3=0 5-3=2 3-3=0 4-3=1 4-3=1
juegaMIN
![Page 54: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/54.jpg)
MIN = 0
MIN = 0
tic-tac-toe: jugada #24-2=2
3-2=1
5-2=3
2-2=0
4-2=2
3-2=1
4-2=2 4-2=2
4-3=1 3-3=0 5-3=2 3-3=0 4-3=1 4-3=1
![Page 55: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/55.jpg)
MIN = 0
MIN = 0
tic-tac-toe: jugada #24-2=2
3-2=1
5-2=3
2-2=0
4-2=2
3-2=1
4-2=2 4-2=2 5-2=3
4-3=1 3-3=0 5-3=2 3-3=0 4-3=1 4-3=1
![Page 56: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/56.jpg)
MIN = 0
MIN = 0
tic-tac-toe: jugada #24-2=2
3-2=1
5-2=3
2-2=0
4-2=2
3-2=1
4-2=2 4-2=2 5-2=3 3-2=1
4-3=1 3-3=0 5-3=2 3-3=0 4-3=1 4-3=1
![Page 57: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/57.jpg)
MIN = 0
MIN = 0
tic-tac-toe: jugada #24-2=2
3-2=1
5-2=3
2-2=0
4-2=2
3-2=1
4-2=2 4-2=2 5-2=3 3-2=1 4-2=2
4-3=1 3-3=0 5-3=2 3-3=0 4-3=1 4-3=1
![Page 58: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/58.jpg)
MIN = 0
MIN = 0
tic-tac-toe: jugada #24-2=2
3-2=1
5-2=3
2-2=0
4-2=2
3-2=1
4-2=2 4-2=2 5-2=3 3-2=1 4-2=2 4-2=2
4-3=1 3-3=0 5-3=2 3-3=0 4-3=1 4-3=1
![Page 59: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/59.jpg)
MIN = 0
MIN = 0
MIN = 1
tic-tac-toe: jugada #24-2=2
3-2=1
5-2=3
2-2=0
4-2=2
3-2=1
4-2=2 4-2=2 5-2=3 3-2=1 4-2=2 4-2=2
4-3=1 3-3=0 5-3=2 3-3=0 4-3=1 4-3=1
![Page 60: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/60.jpg)
MIN = 0
MIN = 0
MIN = 1
MAX = 1
tic-tac-toe: jugada #24-2=2
3-2=1
5-2=3
2-2=0
4-2=2
3-2=1
4-2=2 4-2=2 5-2=3 3-2=1 4-2=2 4-2=2
4-3=1 3-3=0 5-3=2 3-3=0 4-3=1 4-3=1
4-3=1
![Page 61: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/61.jpg)
MIN = 0
MIN = 0
MIN = 1
MAX = 1
tic-tac-toe: jugada #24-2=2
3-2=1
5-2=3
2-2=0
4-2=2
3-2=1
4-2=2 4-2=2 5-2=3 3-2=1 4-2=2 4-2=2
4-3=1 3-3=0 5-3=2 3-3=0 4-3=1 4-3=1
4-3=1
4-3=1
![Page 62: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/62.jpg)
MIN = 0
MIN = 0
MIN = 1
MAX = 1
tic-tac-toe: jugada #24-2=2
3-2=1
5-2=3
2-2=0
4-2=2
3-2=1
4-2=2 4-2=2 5-2=3 3-2=1 4-2=2 4-2=2
4-3=1 3-3=0 5-3=2 3-3=0 4-3=1 4-3=1
4-3=1
3-3=0
4-3=1
![Page 63: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/63.jpg)
MIN = 0
MIN = 0
MIN = 1
MAX = 1
tic-tac-toe: jugada #24-2=2
3-2=1
5-2=3
2-2=0
4-2=2
3-2=1
4-2=2 4-2=2 5-2=3 3-2=1 4-2=2 4-2=2
4-3=1 3-3=0 5-3=2 3-3=0 4-3=1 4-3=1
4-3=1
3-3=0
4-3=1
3-3=0
![Page 64: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/64.jpg)
MIN = 0
MIN = 0
MIN = 1
MAX = 1
tic-tac-toe: jugada #24-2=2
3-2=1
5-2=3
2-2=0
4-2=2
3-2=1
4-2=2 4-2=2 5-2=3 3-2=1 4-2=2 4-2=2
4-3=1 3-3=0 5-3=2 3-3=0 4-3=1 4-3=1
4-3=1
3-3=0
4-3=1
3-3=0
3-3=0
![Page 65: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/65.jpg)
MIN = 0
MIN = 0
MIN = 1
MAX = 1
tic-tac-toe: jugada #24-2=2
3-2=1
5-2=3
2-2=0
4-2=2
3-2=1
4-2=2 4-2=2 5-2=3 3-2=1 4-2=2 4-2=2
4-3=1 3-3=0 5-3=2 3-3=0 4-3=1 4-3=1
4-3=1
3-3=0
4-3=1
3-3=0
3-3=0
3-3=0
![Page 66: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/66.jpg)
MIN = 0
MIN = 0
MIN = 1
MIN = 0MAX = 1
tic-tac-toe: jugada #24-2=2
3-2=1
5-2=3
2-2=0
4-2=2
3-2=1
4-2=2 4-2=2 5-2=3 3-2=1 4-2=2 4-2=2
4-3=1 3-3=0 5-3=2 3-3=0 4-3=1 4-3=1
4-3=1
3-3=0
4-3=1
3-3=0
3-3=0
3-3=0
![Page 67: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/67.jpg)
MIN = 0
MIN = 0
MIN = 1
MIN = 0MAX = 1
La mejor jugada de MAX es pues tras lo cual MIN podría jugar 0 XX
0 0 XX
tic-tac-toe: jugada #24-2=2
3-2=1
5-2=3
2-2=0
4-2=2
3-2=1
4-2=2 4-2=2 5-2=3 3-2=1 4-2=2 4-2=2
4-3=1 3-3=0 5-3=2 3-3=0 4-3=1 4-3=1
4-3=1
3-3=0
4-3=1
3-3=0
3-3=0
3-3=0
![Page 68: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/68.jpg)
0 0 XX
0 0 X XX
X 0 0 XX
0 0X XX
0 0 XX X
0 0 XX X
X 0 00 XX
X 0 0 XX 0
X 0 0 XX 0
X 0 0 X 0X
2-1=1
3-1=2
2-1=1
3-1=2
MIN = 1
MIN = -∞∞
MIN = -∞∞
MIN = -∞∞ MIN = -∞∞
MAX = 1
La mejor jugada de MAX es pues:
X 0 0 XX
Ejemplo: tic-tac-toe
• Por convención:– las jugadas ganadoras se evalúan a “+∞∞”– las jugadas perdedoras se evalúan a “-∞∞”
![Page 69: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/69.jpg)
Minimax
• Valor-Minimax(n): utilidad para MAX de estar en el estado n asumiendo que ambos jugadores jueguen óptimamente.
![Page 70: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/70.jpg)
Minimax
• Valor-Minimax(n):– Utilidad(n), si n es un estado terminal
– maxs Sucesores(n)∈ Valor-Minimax(s), si n es un estado MAX
– mins Sucesores(n)∈ Valor-Minimax(s), si n es un estado MIN
![Page 71: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/71.jpg)
Algoritmo minimax
• Calcula la decisión minimax del estado actual.
• Usa un cálculo simple recurrente de los valores minimax de cada estado sucesor.
• La recursión avanza hacia las hojas del árbol.
• Los valores minimax retroceden por el árbol cuando la recursión se va deshaciendo.
![Page 72: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/72.jpg)
Algoritmo minimax
• El algoritmo primero va hacia abajo a los tres nodos izquierdos y utiliza la función Utilidad para descubrir que sus valores son 3, 12 y 8.
A
B
![Page 73: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/73.jpg)
Algoritmo minimax
• Entonces el algoritmo toma el mínimo de estos valores, 3, y lo devuelve como el valor del nodo B.
A
B
![Page 74: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/74.jpg)
Algoritmo minimax
• Realiza una exploración primero en profundidad completa del árbol de juegos.
• Si la profundidad máxima del árbol es m, y hay b movimientos legales en cada punto, entonces la complejidad :– en tiempo es O(bm);– en espacio es
• O(bm) si se generan todos los sucesores a la vez;• O(m) si se generan los sucesores uno por uno.
• Juegos reales: los costos de tiempo son inaceptables, pero este algoritmo sirve como base para el primer análisis matemático y para algoritmos más prácticos.
![Page 75: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/75.jpg)
Algoritmo minimaxfunción Decisión-Minimax(estado) devuelve una acción variables de entrada: estado, estado actual del juego v ← Max-Valor(estado) devolver la acción de Sucesores(estado) con valor v
función Max-Valor(estado) devuelve un valor utilidad si Test-Terminal(estado) entonces devolver Utilidad (estado) v ← -∞ para un s en Sucesores(estado) hacer v ← Max(v, Min-Valor(s)) devolver v
función Min-Valor(estado) devuelve un valor utilidad si Test-Terminal(estado) entonces devolver Utilidad (estado) v ← ∞ para un s en Sucesores(estado) hacer v ← Min(v, Max-Valor(s)) devolver v
![Page 76: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/76.jpg)
Poda alfa-beta
• Problema de la búsqueda minimax: el número de estados que tiene que examinar es exponencial con el número de movimientos.
• El exponente no se puede eliminar, pero se puede dividir en la mitad.
• Es posible calcular la decisión minimax correcta sin mirar todos los nodos en el árbol.
• La poda alfa-beta permite eliminar partes grandes del árbol, sin influir en la decisión final.
![Page 77: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/77.jpg)
Minimax con poda α-βa
cb e = min(-1, ?) = -1
-1 (gana MIN) ?
No tiene sentido seguir buscando los otros descendientes de c.
a
cb
g
f
d
e
0.03
-0.1 -0.05
e= max (-0.1, -0.05) = -0.05
En c: e= min(-0.05, v(g)) por lo tanto en a: e = max(0.03, min(-0.05, v(g))) = 0.03Se pueden pues podar los nodos bajo g; no aportan nada.
?
El valor de la raíz y la decisión minimax son independientes de los valores de las hojas podadas.
![Page 78: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/78.jpg)
a
cb
id
0.03
he
gf
-0.1
max
min
max
min
max
e(e) = min(-0.1,v(g))Como la rama b ya da un 0.03, Cualquier cosa peor no sirve=> No hay que explorar ge(d) = max(e(e), h)=> Sí hay que explorar h...
La búsqueda minimax es primero en profundidad: en cualquier momento sólo se consideran los nodos a lo largo de un camino del árbol.
Minimax con poda α-β
![Page 79: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/79.jpg)
Poda alfa-beta• Los dos parámetros alfa y beta describen los
límites sobre los valores que aparecen a lo largo del camino:– α = el valor de la mejor opción (el más alto) que se
ha encontrado hasta el momento en cualquier punto del camino, para MAX
– β = el valor de la mejor opción (el más bajo) que se ha encontrado hasta el momento en cualquier punto del camino, para MIN
• La búsqueda alfa-beta actualiza el valor de α y β según se va recorriendo el árbol y termina la recursión cuando encuentra un nodo peor que el actual valor α o β correspondiente.
![Page 80: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/80.jpg)
Poda alfa-beta: ejemplo
![Page 81: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/81.jpg)
Poda alfa-beta: ejemplo
![Page 82: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/82.jpg)
Poda alfa-beta: ejemplo
![Page 83: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/83.jpg)
Poda alfa-beta: ejemplo
![Page 84: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/84.jpg)
Poda alfa-beta: ejemplo
![Page 85: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/85.jpg)
MAX
Vi
{α, β}Si Vi ≥ β poda βSi Vi > α modificar α
Retornar α
{α, β}Si Vi ≤ α poda αSi Vi < β modificar β
Retornar β
MIN
Vi
Las cotas α y β se transmiten de padres a hijos de 1 en 1 y en el orden de visita de los nodos.
Poda alfa-beta
![Page 86: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/86.jpg)
Minimax con poda α-βFuncion valorMax (g,α,β) retorna entero Si estado_terminal(g) entonces retorna(evaluacion(g)) si no Para cada mov en movs_posibles(g) α=max(α,valorMin(aplicar(mov,g),α,β)) si α≥β entonces retorna(β) fPara retorna(α) fsifFuncion
Funcion valorMin (g,α,β) retorna entero Si estado_terminal(g) entonces retorna(evaluacion(g)) si no Para cada mov en movs_posibles(g) β=min(β,valorMax(aplicar(mov,g),α,β)) si α≥β entonces retorna(α) fPara retorna(β) fsifFuncion
El recorrido se inicia llamando a la función valorMax con α=-∞ y β=+∞.En la función valorMax α es el valor que se actualiza.En la función valorMin β es el valor que se actualiza.
![Page 87: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/87.jpg)
A
CB
ED
3
{-∞, +∞}
A
CB
ED
3 5
3{-∞, 3}
A
CB
D
3
HF
{3, +∞}
G
JI
LK
{3, +∞}
{3, +∞}
{3, +∞}
0
Se puede podar I ya que es un nodo min y el valor de v(K) = 0 es < α = 3
{alpha = -∞, beta = +∞}
{-∞, 3}{-∞, +∞}
{3, +∞}
![Page 88: El Juego TicTacToe (Gato) mediante Arboles de Decisiones](https://reader034.fdocumento.com/reader034/viewer/2022052118/557abdf0d8b42a642f8b4be4/html5/thumbnails/88.jpg)
A
CB
D
3
HF
{3, +∞}
G
J
{3, +∞}
{3, +∞}
5
5
A
CB
D
3
HF
{3, +∞}
G
J
{3, 5}
5
5
NM 7
Podemos podar G pues es un nodo max y el valor de M (7) > β = 5
A
CB
D
3
HF
4
J
4
{3, 5}
5
54