Especialización en Creación y Programación de Videojuegos
CI-6675
Algoritmos y Estructuras Optimizadas para Videojuegos
Realizado por: Ricardo Monascal
Universidad Simón Bolívar Departamento de Computación y Tecnología de la Información
CI-6675 : ALGORITMOS Y ESTRUCTURAS OPTIMIZADAS PARA VIDEOJUEGOS
ESPECIALIZACIÓN EN CREACIÓN Y PROGRAMACIÓN DE VIDEOJUEGOS
Agenda de hoy… • Juegos Combinatorios − Información en un Juego − La suma de un Juego
• Árboles de Juegos − Minimax − Poda Alfa-Beta
• Juegos de Azar • ¡Las Exposiciones se Acercan!
Realizado por: Ricardo Monascal
Universidad Simón Bolívar Departamento de Computación y Tecnología de la Información
CI-6675 : ALGORITMOS Y ESTRUCTURAS OPTIMIZADAS PARA VIDEOJUEGOS
ESPECIALIZACIÓN EN CREACIÓN Y PROGRAMACIÓN DE VIDEOJUEGOS
Juegos Combinatorios • ¿Por qué combinatorio? • Información en un juego − Información perfecta Ej: Ajedrez − Información escondida Ej: Poker − Información probabilista Ej: Backgammon
Realizado por: Ricardo Monascal
Universidad Simón Bolívar Departamento de Computación y Tecnología de la Información
CI-6675 : ALGORITMOS Y ESTRUCTURAS OPTIMIZADAS PARA VIDEOJUEGOS
ESPECIALIZACIÓN EN CREACIÓN Y PROGRAMACIÓN DE VIDEOJUEGOS
Juegos Combinatorios • La suma de un juego − Corresponde al chance que tiene un jugador de ganar o perder, con respecto al otro, en cualquier punto del juego.
• Juegos de suma diferente a cero − La vieja − El dilema del prisionero
Universidad Simón Bolívar Departamento de Computación y Tecnología de la Información
CI-6675 : ALGORITMOS Y ESTRUCTURAS OPTIMIZADAS PARA VIDEOJUEGOS
ESPECIALIZACIÓN EN CREACIÓN Y PROGRAMACIÓN DE VIDEOJUEGOS
Árboles de Juego • Todo juego de información perfecta puede ser representado con un árbol.
Realizado por: Ricardo Monascal
Universidad Simón Bolívar Departamento de Computación y Tecnología de la Información
CI-6675 : ALGORITMOS Y ESTRUCTURAS OPTIMIZADAS PARA VIDEOJUEGOS
ESPECIALIZACIÓN EN CREACIÓN Y PROGRAMACIÓN DE VIDEOJUEGOS
Árboles de Juego • El Algoritmo Minimax − El primer jugador es MAX y quiere ganar (y que el segundo jugador pierda). − El segundo jugador es MIN y quiere ganar (y que el primer jugador pierda).
Realizado por: Ricardo Monascal
Universidad Simón Bolívar Departamento de Computación y Tecnología de la Información
CI-6675 : ALGORITMOS Y ESTRUCTURAS OPTIMIZADAS PARA VIDEOJUEGOS
ESPECIALIZACIÓN EN CREACIÓN Y PROGRAMACIÓN DE VIDEOJUEGOS
Árboles de Juego • El Algoritmo Minimax − Ejemplo: Juego de División de Nim.
Realizado por: Ricardo Monascal
Universidad Simón Bolívar Departamento de Computación y Tecnología de la Información
CI-6675 : ALGORITMOS Y ESTRUCTURAS OPTIMIZADAS PARA VIDEOJUEGOS
ESPECIALIZACIÓN EN CREACIÓN Y PROGRAMACIÓN DE VIDEOJUEGOS
Árboles de Juego • El Algoritmo Minimax − Ejemplo: Juego de División de Nim.
Realizado por: Ricardo Monascal
Universidad Simón Bolívar Departamento de Computación y Tecnología de la Información
CI-6675 : ALGORITMOS Y ESTRUCTURAS OPTIMIZADAS PARA VIDEOJUEGOS
ESPECIALIZACIÓN EN CREACIÓN Y PROGRAMACIÓN DE VIDEOJUEGOS
Árboles de Juego • El Algoritmo Minimax − Si cada decisión tiene b opciones, y el árbol tiene profundidad d, entonces la complejidad en tiempo es O(bd) − Posibles optimizaciones: − Disminuir b: podar del árbol − Disminuir d: Minimax parcial *Necesita una función de evaluación* *Pudiera aplicar profundidad iterativa* − ¡El poderoso Negamax!
Realizado por: Ricardo Monascal
Universidad Simón Bolívar Departamento de Computación y Tecnología de la Información
CI-6675 : ALGORITMOS Y ESTRUCTURAS OPTIMIZADAS PARA VIDEOJUEGOS
ESPECIALIZACIÓN EN CREACIÓN Y PROGRAMACIÓN DE VIDEOJUEGOS
Árboles de Juego • Poda Alfa-Beta − Objetivo: Detener búsqueda innecesarias − Ejemplo: − El nodo A (de tipo MAX) encontró un hijo con valor 4 − El nodo B (de tipo MIN, hijo de A) encontró un hijo con valor 2 − El resto de los hijos de B ya no tienen que explorarse
Realizado por: Ricardo Monascal
Universidad Simón Bolívar Departamento de Computación y Tecnología de la Información
CI-6675 : ALGORITMOS Y ESTRUCTURAS OPTIMIZADAS PARA VIDEOJUEGOS
ESPECIALIZACIÓN EN CREACIÓN Y PROGRAMACIÓN DE VIDEOJUEGOS
Árboles de Juego • Poda Alfa-Beta − α está asociado con nodos MAX y nunca decrece − β está asociado con nodos MIN y nunca crece − Al principio, α = -∞ y β = +∞ − Se podará todo nodo MIN que tenga un valor β menor o igual al valor α de cualquiera de sus ancestros MAX − Se podará todo nodo MAX que tenga un valor α mayor o igual al valor β de cualquiera de sus ancestros MIN
Realizado por: Ricardo Monascal
Universidad Simón Bolívar Departamento de Computación y Tecnología de la Información
CI-6675 : ALGORITMOS Y ESTRUCTURAS OPTIMIZADAS PARA VIDEOJUEGOS
ESPECIALIZACIÓN EN CREACIÓN Y PROGRAMACIÓN DE VIDEOJUEGOS
Árboles de Juego • Poda Alfa-Beta
Realizado por: Ricardo Monascal
Universidad Simón Bolívar Departamento de Computación y Tecnología de la Información
CI-6675 : ALGORITMOS Y ESTRUCTURAS OPTIMIZADAS PARA VIDEOJUEGOS
ESPECIALIZACIÓN EN CREACIÓN Y PROGRAMACIÓN DE VIDEOJUEGOS
Árboles de Juego • Poda Alfa-Beta − En el mejor caso, la complejidad en tiempo de la poda Alfa-Beta es Ω(bd/2) − El peor caso sigue siendo O(bd) − Variantes interesantes: − Negascout − MTD-f
Realizado por: Ricardo Monascal
Universidad Simón Bolívar Departamento de Computación y Tecnología de la Información
CI-6675 : ALGORITMOS Y ESTRUCTURAS OPTIMIZADAS PARA VIDEOJUEGOS
ESPECIALIZACIÓN EN CREACIÓN Y PROGRAMACIÓN DE VIDEOJUEGOS
Juegos de Azar • Consideremos el juego de “la vieja con dado” − Existe un tablero de tamaño m x m − Existe un dado de n lados − El jugador que logre colocar L fichas en una fila (o columna) gana − En cada jugada: − Se reparten n “marcas” en las casillas libres del tablero − La cantidad de marcas en una casilla s es marcas(s) − Se arroja el dado para cada casilla marcada − Si el resultado del dado es menor o igual a marcas(s), se captura la celda − Si n = 2, se puede jugar con una moneda. Realizado por: Ricardo Monascal
Universidad Simón Bolívar Departamento de Computación y Tecnología de la Información
CI-6675 : ALGORITMOS Y ESTRUCTURAS OPTIMIZADAS PARA VIDEOJUEGOS
ESPECIALIZACIÓN EN CREACIÓN Y PROGRAMACIÓN DE VIDEOJUEGOS
Juegos de Azar
Realizado por: Ricardo Monascal
Universidad Simón Bolívar Departamento de Computación y Tecnología de la Información
CI-6675 : ALGORITMOS Y ESTRUCTURAS OPTIMIZADAS PARA VIDEOJUEGOS
ESPECIALIZACIÓN EN CREACIÓN Y PROGRAMACIÓN DE VIDEOJUEGOS
¡Las Exposiciones se Acercan! • Es momento de escoger un tema − Toma de Decisiones − Modelado de Incertidumbre − Paralelismo y Comunicación − Grafos Especializados − ¡Cualquier otro tema interesante!
• ¿Qué debe tener la presentación? − Balance entre teoría, historia y práctica − Al menos un juego que aplique la técnica − Debe durar aproximadamente 30 minutos − La semana que viene concretamos los temas
Realizado por: Ricardo Monascal
Universidad Simón Bolívar Departamento de Computación y Tecnología de la Información
CI-6675 : ALGORITMOS Y ESTRUCTURAS OPTIMIZADAS PARA VIDEOJUEGOS
ESPECIALIZACIÓN EN CREACIÓN Y PROGRAMACIÓN DE VIDEOJUEGOS
¿Preguntas?
Realizado por: Ricardo Monascal
Universidad Simón Bolívar Departamento de Computación y Tecnología de la Información