INTRODUCCIÓN
Estará dividido en 3 partes, en este
primer post se hablará sobre conceptos básicos y conocimientos previos
necesarios para el entendimiento del tema, en el segundo, con suerte, se hablará sobre aplicaciones básicas en código (Python y Java), para finalizar con una tercera parte en donde realizaremos optimizaciones y profundizaremos en las aplicaciones.
¿Qué es Teoría de Juegos?
En Wikipedia la comunidad define este concepto de la siguiente manera:
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. Sus investigadores estudian las estrategias óptimas así como el comportamiento previsto y observado de individuos en juegos. Tipos de interacción aparentemente distintos pueden, en realidad, presentar estructura de incentivo similar y, por lo tanto, se puede representar mil veces conjuntamente un mismo juego.En palabras coloquiales, comprende el estudio de distintos modelos que permiten a un "agente" decidir qué hacer a continuación, en un ambiente competitivo, para tener los mejores beneficios.
Dentro de la teoría de juegos, el agente no debe preguntarse qué hacer sin tomar en cuenta las estrategias y posibles movimientos futuros de todos los "n" agentes que intervienen en el medio. Es decir, debe evitar preguntas del tipo: "¿Qué hago?", y comenzar a preguntar: "¿Qué hago si el otro hará "x" cosa?".
El fundador formal de la "Teoría de Juegos" no fue otro que el Matemático John Von Neumann, a quien los dedicados al campo de la computación e informática debemos mucho.
Esta clase de teoría fue planeada y galardonada por su aplicación en Economía, así como sus diversas ramas en la Matemática Académica. Sin embargo puede aplicarse en multitud de áreas. Como la temática de este blog no es de economía, hemos de utilizarla para desarrollar IA's de juegos de tableros por turnos, en el cual un algoritmo conocido como "minimax" representa una opción archiconocida por su simpleza y eficiencia.
¿Qué es "Minimax"?
De nuevo, recomiendo la definición y profundización que existe en Wikipedia:Este teorema establece que en los juegos bipersonales de suma cero, donde cada jugador conoce de antemano la estrategia de su oponente y sus consecuencias, existe una estrategia que permite a ambos jugadores minimizar la pérdida máxima esperada. En particular, cuando se examina cada posible estrategia, un jugador debe considerar todas las respuestas posibles del jugador adversario y la pérdida máxima que puede acarrear. El jugador juega, entonces, con la estrategia que resulta en la minimización de su máxima pérdida. Tal estrategia es llamada óptima para ambos jugadores sólo en caso de que sus minimaxes sean iguales (en valor absoluto) y contrarios (en signo). Si el valor común es cero el juego se convierte en un sinsentido.Es básicamente una manera de calcular el mejor movimiento posible, que nos lleve a una ganancia máxima, si suponemos que nuestro oponente hará lo posible por perjudicarnos. Esta técnica está limitada a los ambientes en donde compiten únicamente 2 agentes, y se puede acceder a toda la información necesaria sobre la estrategia del otro. Es de uso adecuado cuando se nos presenta un ambiente determinista, es decir, que no contiene aspectos aleatorios que puedan intervenir en el sistema.
Por ahora esta información servirá de entrada, un abrebocas invitando a profundizar en la teoría y conceptos expuestos para un mejor entendimiento del código. En la parte 2, detallaremos con más detalles el algoritmo a utilizar y comenzaremos a implementar un pequeño juego de "Tic Tac Toe", conocido en mis tierras como "La Vieja".
Links relacionados de lectura recomendada:
http://es.wikipedia.org/wiki/Minimax
http://es.wikipedia.org/wiki/Teor%C3%ADa_de_juegos
http://www.elblogsalmon.com/conceptos-de-economia/que-es-la-teoria-de-juegos
No hay comentarios:
Publicar un comentario