Ingeniería Artificial: Teoría de juegos

Teoría de Juegos
Índice
●

Introducción

●

Juegos, estrategia y resolución
–
–

Tipos de juegos

–
●

¿Qué es un problema?

Estrategias

Teoría matemática
–
–

 

Sin adversario
Con adversario

 

Teoría de Juegos
Índice
●

Métodos con adversario
–
–

Mejorar el minimax

–

Algoritomo SSS*

–

Algoritmo Scout

–
●

Minimax

Algoritmo MTD(F)Areas Relacionadas
–
–

 

Prisioneros
Gallinas

 

Introducción
●

 

Desde la época de los egipcios se han utilizado las
matemáticas como algo lúdico, así estudiaremos como en
algunos juegos de azar hay estrategias ganadoras, de
suma cero, simétricas, etc.

 

Juegos, estrategias y Resolución
●

¿Qué es un problema?
Un problema es, en este caso, la abstracción deuna serie de
elementos tales como: un objetivo, meta, o estado final a cumplir;
un punto de inicio donde empezaremos a enfocar el problema; y
una serie de movimientos que nos permitirán como mínimo
aproximarnos del estado inicial al final. Y en el mejor de los casos,
nos permitirán salir airosos con la mejor solución del problema.

 

 

Juegos, estrategias y resolución
Tipos dejuegos
No es lo mismo hacer el siguiente movimiento jugando al ajedrez
que decidir si en una apuesta sigues o te plantas, por eso los
vamos a clasificar para luego poder utilizar los algoritmos que
mejor se adapten.
●

¿Qué hay que tener en cuenta?
–

Número de jugadores
●

●

 

Sin adversario
Un adversario

●

N-adversarios

 

Juegos, estrategias y resolución
Tipos dejuegos
●

¿Qué hay que tener en cuenta?
–

Orden de los movimientos
●

●

–

Por azar
Alternativamente

Tipo de conocimiento
●

●

 

Conocimiento perfecto
Conocimiento imperfecto
 

Nota: el hecho de que el azar aparezca se llama determinismo

Juegos, estrategias y resolución
●

¿Qué hay que tener en cuenta?
–

 

Podemos encontrarnos juegos donde un movimientoque
beneficia, perjudica a su vez al adversario (equilibrio
Nash)

 

Juegos, estrategias y resolución
Estrategias
●

●

La idea básica es intentar predecir los posibles movimientos del
adversario y todas las posibiles situaciones, y elegir la mejor. Esto
es “generar el árbol de búsqueda” con las aproximaciones de las
mejores jugadas
Para poder realizar los cálculos necesitamosuna abstracción
codificable del juego:
–
–

Representación del estado ganador
 

–
●

Representación del estado inicial

–

 

Representación del estado

Operadores de movimiento ( según el estado actual )

Teoría matemática
●

 

La teoría de juegos es una rama de las matemáticas que
se ocupa principalmente de la toma de decisiones.
Gracias a sus características, seaplica a todo tipo de
situaciones en las que se plantea un conflicto, en el cual
los contendientes tienen que tomar las decisiones más
favorables a sus intereses sin conocer las que tomarán
sus adversarios

 

Teoría matemática
Métodos utilizados en Juegos Sin Adversario
●

●

Para los algoritmos de juegos unipersonales suelen
utilizarse algoritmos de búsqueda heurística, aunque contiempo y memoria suficiente pueden solucionarse por
fuerza bruta.
Los algoritmos más utilizados son:
–
–

 

Algorimto A* (Hart): best-first
Algoritmo IDA*,
ordenador

según
 

los

recursos

del

Teoría matemática
●

●

 

El algoritmo A* utiliza una función de evaluación f(n) = g(n) + h'(n), donde
h'(n) representa el valor heurístico del nodo a evaluar desde elactual, n,
hasta el final, y g(n), el coste real del camino recorrido para llegar a dicho
nodo, n. A* mantiene dos estructuras de datos auxiliares, que podemos
denominar abiertos, implementado como una cola de prioridad (ordenada
por el valor f(n) de cada nodo), y cerrados, donde se guarda la
información de los nodos que ya han sido visitados. En cada paso del
algoritmo, se expande el nodo...