# Inteligencia artificial para videojuegos/Teoría de la decisión

Introduzco la teoría de la decisión con una o dos frases

## Introducción

La Teoría de la Probabilidad resulta útil para modelar la incertidumbre… … ¿cómo podemos aprovechar esta teoría para crear un agente basado en utilidad?
Aquí asumimos que el entorno, además de no determinista y/o parcialmente observable, es episódico. Por tanto el agente elegirá una acción en función de su resultado inmediato-

### IA basada en utilidad

La IA basada en utilidad (en inglés Utility AI) se basa en la Teoría de la Decisión. Podemos decir que es el resultado de Teoría de la Utilidad + Teoría de la Probabilidad.
* El agente maximiza su rendimiento eligiendo la acción que en promedio lleva al estado más útil.
| Acción posible (probabilidad) | Estado resultante (utilidad) | Acción posible (probabilidad) |
| Disparo (0.7) → | Yo sobrevivo, el enemigo muere (+100) | ← Granada (0.8) |
| Disparo (0.25) → | Yo sobrevivo, el enemigo también (-1) | ← Granada (0.05) |
| Disparo (0.04) → | Ambos morimos (-400) | ← Granada (0.1) |
| Disparo (0.01) → | Yo muero, el enemigo sobrevive (-501) | ← Granada (0.05) |

### Teoría de la decisión

El principio de esta teoría es elegir para maximizar la utilidad esperada (UE)
$acci{\acute {o}}n={\underset {a}{argmax}}\,\,\,UE(a|{\boldsymbol {e}})$
donde
$UE(a|{\boldsymbol {e}})=\sum _{s'}P(resultado(a)=s'|a,{\boldsymbol {e}})*U(s')$
Trabajando con la probabilidad de que la acción a conduzca de la evidencia e al estado s’ $P(resultado(a)=s'|a,{\boldsymbol {e}})$
¡Cualquier agente racional sigue este principio! (lo difícil es calcular la probabilidad y la utilidad).
No conocer los estados esperados nos hace ver los posibles resultados... como loterías (lottery, en inglés). Los axiomas de esta teoría son que estas loterías pueden ordenarse por preferencia, son transitivas, continuas, sostenibles, monótonas y descomponibles.

## Función de utilidad

Asigna números reales a loterías. Aunque no hay escalas absolutas, la utilidad se normaliza asignando 0 a lo peor y 1 a lo mejor. La utilidad de un estado S vale p, mismo valor que la probabilidad de una lotería estándar que resulta de igual preferencia para el agente $[p,u\top ;(1-p),u\bot ]$
En realidad, un agente puede no ser neutral y preferir un valor seguro igual o menor a la utilidad esperada promedio de una lotería. Esto se llama aversión al riesgo (en esto se basan los seguros) y lo contrario es propensión al riesgo

### Dinero

La Teoría de la Utilidad es un campo de la Economía y el dinero suele ser un valor seguro importante. Aunque no siempre sea directamente proporcional: ganar tu primer millón de dólares resulta mucho más útil que el segundo...
INSERTAR GRÁFICA HECHA EN GOOGLE DOCS
Estudio de Grayson de 1960 sobre interés inversor en explotaciones petrolíferas (¡es casi logarítmico!)

### Función de utilidad multiatributo

Parte de la Teoría de la Utilidad asume que la utilidad de un estado depende de varios valores (atributos) distintos.
* Podemos decidir en base a todos ellos:
* Podemos combinarlos en uno y decidir en base a él:

## Red de Decisión

Una red Bayesiana a la que se añaden nodos con acciones y utilidades. Sirve para formalizar e implementar sistemas de toma de decisiones.
* Los óvalos son nodos de azar (las variables aleatorias)
* El rectángulo es nodo de decisión, la acción elegida
* El rombo es nodo de utilidad (la función)
AÑADIR GRAFO, DESDE AQUÍ O DESDE GOOGLE DRAW

## Valor de la información

Si fuese posible obtener más información antes de decidir, habría que considerar el valor (utilidad) de dicha información.
* Primero elegir qué información obtener (si es que interesa) y luego, en secuencia, tomar la decisión
${1 \over n}*{(n-1)*C \over n}+{n-1 \over n}*{C \over n*(n-1)}={C \over n}$
* Conocer el valor de la información permite a un agente ser racional haciendo averiguaciones.

## Sistemas expertos

La Teoría de la Decisión se aplicó a muchos problemas reales en los años 50 y 60.
* Ej. Gobierno, Negocios, Ejército, Salud Pública...
* Había un tomador de decisión que establecía las preferencias y un analista de decisión que hacía los cálculos para identificar la mejor acción posible.
* En los 80, el analista pasó a ser una máquina.
Se crearon sistemas expertos, IAs capaz de emular la toma de decisiones de un experto.
* Usaban bases de conocimiento y reglas.
* A partir de los 80 pudieron escalar gracias a una inferencia más eficaz sobre redes de decisión.
Se diseñan mediante un proceso:
* Crear el modelo causal
* Simplificarlo a un modelo cualitativo de decisión
* Asignar probabilidades
* Asignar utilidades
* Verificar y refinar el modelo (comparándolo con el “patrón oro” (gold standard): las opiniones más expertas)
Realizar un análisis de sensibilidad (si un cambio pequeño afecta mucho a la decisión tomada, falta conocimiento)
METER RED DE DECISIÓN GRANDE DE EJEMPLO

## Decisiones complejas

Si podemos realizar varias acciones en secuencia se complica el problema, hablamos de decisiones complejas.
* Se requiere razonamiento probabilista temporal (que no llegamos a estudiar)
* Se pueden encontrar Redes de Decisión con múltiples nodos de decisión, en vez de uno solo
Sin embargo la industria prefiere soluciones rápidas y muy controlables por el diseñador. Al menos por ahora, se usan herramientas más simples para la toma de decisiones...

## Máquina de estados finitos

Una máquina de estados finitos (finite state machine o FSM) es la manera más flexible y popular de modelar el comportamiento en juegos. La toma de decisiones reside en las transiciones.
Existen variantes no determinista Ej. Estocástica de estado múltiple o Jerárquicas (hierarchical FSM o HFSM), para reducir tamaño y reutilizar código.
PONER IMAGEN DE FSM NORMAL, E IMAGEN LIBRE DE HFSM

## Árbol de comportamiento

Para evitar acoplamiento entre los estados de una máquina jerárquica de estados finitos se usa un árbol de comportamiento (behavior tree). Representa intuitivamente la ejecución de un plan (secuencia de acciones).
Es un árbol dirigido. Tiene un nodo raíz, nodos de control de flujo y nodos de ejecución. También puede tener elementos estocásticos.
PONER DIAGRAMA LIBRE DE EJEMPLO
Hay dos nodos de control de flujo:
* Nodo Selector (?), tiene éxito si uno de sus hijos tiene éxito, probando de izquierda a derecha.
* Nodo Secuencia (→), tiene éxito si todos sus hijos tienen éxito, de izquierda a derecha.
Además para desacoplar el contexto los nodos pueden compartir información en una estructura llamada “pizarra” (Ej. tabla de vars.)
PONER OTRO DIAGRAMA DE EJEMPLO, CREO QUE TAMBIÉN LIBRE

## Conclusiones

Concluyendo...
* Decisión = Utilidad + Probabilidad
* Todo agente racional maximiza la utilidad esperada, siendo la función de utilidad la que asigna un valor entre 0 y 1 a las loterías
* Una red de Decisión es una red Bayesiana con acciones y utilidades, y se puede usar para crear sistemas expertos
* La industria prefiere la más práctica máquina de estados finitos o el intuitivo árbol de comportamiento

## Lecciones relacionadas

* Conocimiento incierto
* Razonamiento probabilista

## Participantes

* Federico Peinado
* Diego Mateos
* Lluis Cañellas