Inteligencia Artificial en Videojuegos Javier Alcalá Ciclo de conferencias Game Spirit 2
Definición de Inteligencia Artificial ► ►
La Inteligencia Artificial (IA) intenta simular la inteligencia natural ¿Qué es la inteligencia natural? Según la RAE:
inteligencia (Del lat. intelligentĭa) 1. f. Capacidad de entender o comprender 2. f. Capacidad de resolver problemas 3. f. Conocimiento, comprensión, acto de entender 4. f. Sentido en que se puede tomar una sentencia, un dicho o una expresión 5. f. Habilidad, destreza y experiencia 6. f. Trato y correspondencia secreta de dos o más personas o naciones entre sí 7. f. Sustancia puramente espiritual
Falta mencionar el aprendizaje y la memoria Inteligencia Artificial en Videojuegos – Javier Alcalá
2
Definición de Inteligencia Artificial ► Entonces… ¿qué es la IA?
Según la RAE: inteligencia artificial 1. f. Inform. Desarrollo y utilización de ordenadores con los que se intenta reproducir los procesos de la inteligencia humana
Definición empírica: Test de Turing
?
Inteligencia Artificial en Videojuegos – Javier Alcalá
3
Definición de Inteligencia Artificial ► Test de Turing para humanos: captcha
Inteligencia Artificial en Videojuegos – Javier Alcalá
4
Definición de Inteligencia Artificial ► IA en videojuegos:
Es la simulación de comportamientos de los personajes no manejados por el jugador: NPCs, enemigos, jefes finales, animales…
Inteligencia Artificial en Videojuegos – Javier Alcalá
5
Orígenes de la IA en videojuegos ►
Los primeros sistemas de IA (años 50) se aplicaron a juegos de mesa: damas (Arthur Samuel) y ajedrez (Claude Shannon)
►
En los años 60 se desarrollaron juegos como el Pong o Spacewar! basados en la lógica
Inteligencia Artificial en Videojuegos – Javier Alcalá
6
Orígenes de la IA en videojuegos ► En los 70 surgieron
juegos de 1 jugador contra enemigos que se movían mediante patrones almacenados ► Space Invaders (1978) añadió dificultad creciente y respondía a las acciones del jugador Inteligencia Artificial en Videojuegos – Javier Alcalá
7
Orígenes de la IA en videojuegos ► Pac-Man (1980)
incorporó algoritmos de búsqueda en laberintos
► Dragon Warrior (1990)
fue el primer RPG. Permitía variar las rutinas de la IA de los enemigos durante las batallas
Inteligencia Artificial en Videojuegos – Javier Alcalá
8
Orígenes de la IA en videojuegos ► En los años 90 se produjo un boom de
nuevos géneros y nuevas técnicas de IA
Máquinas de estados finitos Redes de neuronas Computación evolutiva Lógica difusa …
Inteligencia Artificial en Videojuegos – Javier Alcalá
9
Orígenes de la IA en videojuegos ► Battelcruiser 3000AD (1996) incorpora
redes de neuronas
Inteligencia Artificial en Videojuegos – Javier Alcalá
10
Técnicas de IA empleadas ► Juegos de suma cero: Minimax ► Búsqueda de caminos: A* ► Agentes inteligentes ► Maquina de estados finitos ► Redes de neuronas ► Algoritmos genéticos ► Redes evolutivas: rtNeat Inteligencia Artificial en Videojuegos – Javier Alcalá
11
Juegos de suma cero ► Son juegos entre 2 adversarios en los que los
intereses de los jugadores son contrarios: Si uno gana, el otro pierde, aunque puede haber tablas ► Cada jugador conoce las posibles jugadas del
contrario ► No interviene el azar en la elección de la mejor jugada ► Se genera un árbol finito ► Ejemplo: damas, ajedrez, go Inteligencia Artificial en Videojuegos – Javier Alcalá
12
Juegos de suma cero ►
Algoritmo Minimax Se basa en probar todas las posibles jugadas y sus respuestas hasta un nivel máximo
Inteligencia Artificial en Videojuegos – Javier Alcalá
13
Juegos de suma cero Llegado a ese nivel se evalúa el tablero y se da un valor positivo, si es buena la jugada, o negativo, si es mala
1
0
0
Inteligencia Artificial en Videojuegos – Javier Alcalá
0
-1 14
0
Juegos de suma cero Se propaga el valor hasta el nivel 0 Max
0
Min
0
0
1
0
0
Inteligencia Artificial en Videojuegos – Javier Alcalá
0
-1
-1 15
0
Juegos de suma cero ► Algoritmo Minimax
El algoritmo responde con la mejor jugada posible suponiendo que el adversario también elige su mejor jugada ► Optimización con poda alfa-beta
Inteligencia Artificial en Videojuegos – Javier Alcalá
16
Juegos de suma cero ► Partidas históricas de ajedrez:
Kasparov 4 Kasparov 2.5 Kasparov 4 Kasparov 3
Deep Thought 2 DEEP BLUE 3.5 Deep Fritz 4 Deep Junior 3
Inteligencia Artificial en Videojuegos – Javier Alcalá
(1996) (1997) (2002) (2003)
17
Juegos de suma cero ►
Árbol inicial del ajedrez: Juega blancas: ► Peón 1 escaque ► Peón 2 escaques ► Caballo
x8 x8 x4
► 20 movimientos posibles
Juega negras: ► Las mismas posibilidades
A nivel 2 hay 400 posibilidades A nivel 4 hay unas 20.000 posibilidades Crecimiento exponencial ⇒ Desarrollar el árbol completo genera más posibilidades que átomos hay en la galaxia ►
Nuevos retos: Go, a nivel 2 hay unas 130.000 posibilidades
Inteligencia Artificial en Videojuegos – Javier Alcalá
18
Búsqueda de caminos ► También llamado pathfinding ► Son algoritmos que buscan un camino
existente entre un nodo inicial y un nodo final de un grafo ► Se tiene en cuenta un coste entre nodos (distancia, dificultad del terreno…) ► Algoritmos típicos: Dijkstra, escalada, primero el mejor, A* ► El A* nos garantiza el camino óptimo Inteligencia Artificial en Videojuegos – Javier Alcalá
19
Búsqueda de caminos 7
4
3
2
2 1
4 3
2
5
3
3 4
2
5
3 4
7
5 8
Inteligencia Artificial en Videojuegos – Javier Alcalá
2
20
Búsqueda de caminos ► El nivel de un juego se debe diseñar con un
grid o rejilla y ésta se convierte en un grafo
Inteligencia Artificial en Videojuegos – Javier Alcalá
21
Búsqueda de caminos Dijkstra
A*
Comparativa de métodos Inteligencia Artificial en Videojuegos – Javier Alcalá
22
Agentes Inteligentes ► Un agente inteligente es una entidad que
percibe y actúa sobre un entorno de forma razonada
Inteligencia Artificial en Videojuegos – Javier Alcalá
23
Agentes Inteligentes ► Tipos de agentes inteligentes Agentes Inteligentes
Agentes Biológicos
Inteligencia Artificial en Videojuegos – Javier Alcalá
Agentes Hardware
Agentes Software
24
Agentes Inteligentes ► ¿Qué es un agente software?
Es una entidad que percibe su entorno a través de sensores y actúa de forma autónoma y razonada con la mejor acción posible sobre ese entorno mediante actuadores Utiliza el bucle: PPA (Percepción – Planificación – Actuación) Percepción
Planificación
Inteligencia Artificial en Videojuegos – Javier Alcalá
Actuación
25
Agentes Inteligentes ► Sensores:
► Actuadores:
Detectores de obstáculos Micrófonos
0 1 1 1 1 1 0 0
Inteligencia Artificial en Videojuegos – Javier Alcalá
Piernas Brazos Ruedas
Detecta rincón Decide girar a la izquierda
Realiza el giro
26
Agentes Inteligentes ► Propiedades:
Autonomía: actúa por cuenta propia Inteligencia: cerrada o adaptable (aprendizaje) Actividad: ► Reactivo: actúa después de algún suceso producido en el
entorno ► Proactivo: decide actuar antes de que se dé un suceso
Sociabilidad: se comunican con el usuario u otros agentes Cooperación: coopera con otros agentes para realizar tareas más complejas Inteligencia Artificial en Videojuegos – Javier Alcalá
27
Agentes Inteligentes ► Aplicaciones en los videojuegos:
Comportamientos inteligentes ►Agente reactivo: guardián de un castillo ►Agente proactivo: exploradores, atacantes
Simulación de personalidades Exploración de mapas desconocidos Simulación de multitudes
Inteligencia Artificial en Videojuegos – Javier Alcalá
28
Máquinas de Estados Finitos ► Una
máquina de estados finitos es una entidad abstracta formada por estados y transiciones entre dichos estados ► Las transiciones se producen por eventos sucedidos en el entorno ► A su vez, la máquina genera una serie de acciones según el estado actual en el que se encuentre Inteligencia Artificial en Videojuegos – Javier Alcalá
29
Máquinas de Estados Finitos ► Cada estado representa una acción: moverse,
disparar, perseguir, etc. ► Cuando se produce un evento, hay una transición de un estado a otro: no hay enemigos, enemigo a la vista, poca munición, etc. No hay enemigos
No hay enemigos
Patrullar
Inteligencia Artificial en Videojuegos – Javier Alcalá
Enemigo a la vista
Disparar
Enemigo a la vista
30
Máquinas de Estados Finitos ► MEF para un fantasma de Pac-Man Pac-Man cerca
Pac-Man lejos
Pac-Man cerca
Buscar Time out
Inicio Modo comible desactivado Pac-Man alcanza al fantasma
Inteligencia Artificial en Videojuegos – Javier Alcalá
Perseguir Pac-Man lejos Modo comible activado
Pac-Man alcanzado Modo comible activado
Comer
Huir Modo comible activado
31
Redes de Neuronas ► Una Red de Neuronas Artificiales (RNA) es un
sistema computacional que imita las capacidades de los sistemas biológicos utilizando muchos elementos simples interconectados ► Neurona formal
Inteligencia Artificial en Videojuegos – Javier Alcalá
32
Redes de Neuronas ► Características:
Clasifican patrones de entrada Necesitan entrenamiento supervisado con muchos ejemplos Son capaces de generalizar el reconocimiento de patrones Ante una entrada desconocida devuelve la clase más parecida Una vez entrenadas, funcionan en tiempo real Inteligencia Artificial en Videojuegos – Javier Alcalá
33
Redes de Neuronas ► Percetrón simple
Entrada
Salida
► Perceptrón multicapa
Entrada
Inteligencia Artificial en Videojuegos – Javier Alcalá
Salida
Oculta
34
Redes de Neuronas ► Uso en videojuegos
Inteligencia Artificial en Videojuegos – Javier Alcalá
Izquierda
Girar a la izquierda
Frontal
Girar a la derecha
Derecha
Seguir de frente
35
Algoritmos Genéticos ► Si no disponemos de ejemplos para realizar el
aprendizaje, tenemos que emplear mecanismos basados en aprendizaje por ensayo y error ► Los Algoritmos Genéticos (AG) se utilizan en aquellos casos en los que no existe un algoritmo convencional ► Resuelven problemas de optimización ► Se basan en la Teoría de la Evolución de Darwin (El origen de las especies, 1859) ► Son sistemas muy robustos Inteligencia Artificial en Videojuegos – Javier Alcalá
36
Algoritmos Genéticos ►
Principios de la evolución por Selección Natural: 1. Cada individuo tiende a transmitir sus rasgos a su progenie 2. La naturaleza produce individuos con rasgos diferentes, debido a mutaciones 3. Los individuos más adaptados, cuyos rasgos son más favorables para desenvolverse en el medio, tienden a producir más progenie (sobreviven los más adaptados) 4. Durante largos períodos de tiempo se puede acumular la variación produciendo nuevas especies completamente adaptadas a nichos particulares
Inteligencia Artificial en Videojuegos – Javier Alcalá
37
Algoritmos Genéticos ► Componentes de un AG:
Individuo: representado por un cromosoma con la información que queremos optimizar Calidad o fitness: da una medida del grado de adaptación al medio (objetivo, principio 4) Operador selección: con probabilidad de selección de cada individuo proporcional a la calidad (principio 3) Operador emparejamiento o reproducción: que producirá nuevos individuos en la siguiente generación (principio 1) Operador mutación: capaz de alterar el código de los nuevos individuos, incrementando la riqueza genética de la población (principio 2)
Inteligencia Artificial en Videojuegos – Javier Alcalá
38
Algoritmos Genéticos ► Algoritmo: Generar una Población aleatoria de NI individuos Repetir hasta haber realizado N generaciones ►Repetir hasta alcanzar NI individuos
Aplicar operador SELECCIÓN: extrae 2 individuos Aplicar operador EMPAREJAMIENTO: cruza su información genética. Esto genera 2 nuevos individuos Aplicar operador MUTACION a cada individuo generado
Devolver el individuo con mayor calidad de la población
Inteligencia Artificial en Videojuegos – Javier Alcalá
39
Redes Neuronales Evolutivas ► Se combinan las redes neuronales con los
algoritmos genéticos ► Consiste en definir la entrada y la salida de una red neuronal y los algoritmos genéticos se encargan de definir la topología interna y los pesos de cada neurona NEAT (NeuroEvolution of Augmenting Topologies) rtNEAT (real time NeuroEvolution of Augmenting Topologies) Inteligencia Artificial en Videojuegos – Javier Alcalá
40
Redes Neuronales Evolutivas ► Los personajes entrenados con este
sistema se adaptan fácilmente durante el juego a los cambios en el entorno Juego NERO (nerogame.org)
Inteligencia Artificial en Videojuegos – Javier Alcalá
41
I+D en IA para Videojuegos ► Un campo de investigación muy abierto ► Normalmente se basa en combinar varias
técnicas Por ejemplo, máquinas de estados finitos con algoritmos genéticos Se conseguirían comportamientos desconocidos, absurdos, divertidos, que mejoran la experiencia de juego Se trata de evitar esto: Inteligencia Artificial en Videojuegos – Javier Alcalá
42
I+D en IA para Videojuegos ► Hay que procurar que el jugador esté inmerso en
el juego sin aburrirse, adaptando el nivel de los enemigos al nivel del jugador ⇒ Concepto de flujo ► Flujo (Mihaly Csikszenmihali) Es el estado mental operativo en el cual la persona está completamente inmersa en la actividad que está ejecutando Se caracteriza por un sentimiento de enfocar la energía, de total implicación con la tarea y de éxito en la realización de la actividad Inteligencia Artificial en Videojuegos – Javier Alcalá
43
I+D en IA para Videojuegos ► Canal de flujo ∞ (Mucho)
ju f í f as e D sl o ed la na C
Ansiedad
Aburrimiento
(Poco) 0
Habilidades
o
0 (Poca)
Inteligencia Artificial en Videojuegos – Javier Alcalá
∞ (Mucha)
44
Consultas ► Contacto:
[email protected]
► http://aigamedev.com/ ► theory.stanford.edu/~amitp/GameProgramming/ ► http://nerogame.org/ ► “Fluir (Flow). Una psicología de la felicidad”.
Mihaly Csikszenmihali ► interactive.usc.edu/projects/cloud/flowing/ Inteligencia Artificial en Videojuegos – Javier Alcalá
45
Inteligencia Artificial en Videojuegos Javier Alcalá
GRACIAS Ciclo de conferencias Game Spirit 2