PDF de programación - Elección de estrategias ganadoras en el juego de béisbol aplicando el Equilibrio de Nash

CENTRO DE INVESTIGACIÓN Y DE ESTUDIOS AVANZADOS

DEL INSTITUTO POLITÉCNICO NACIONAL



Unidad Zacatenco



Departamento de Computación



Elección de estrategias ganadoras en el juego de béisbol aplicando el

Equilibrio de Nash



Tesis que presenta

Arturo Yee Rendón



Para obtener el Grado de

Maestro en Ciencias en Computación



Director de la Tesis: José Matías Alvarado Mentado



México, D.F.



Agosto 2010

i







Los abajo firmantes, integrantes del jurado de examen de grado que sustentara el Sr. Arturo

Yee Rendón, declaramos que hemos revisado la tesis titulada:



ELECCIÓN DE ESTRATEGIAS GANADORAS EN EL JUEGO DE BÉISBOL

APLICANDO EL EQUILIBRIO DE NASH



Y consideramos que cumple los requisitos para obtener el Grado de Maestría en Ciencias en

Computación, firmamos la presente en la Ciudad de México, D.F., el mes de Julio de 2010.

Atentamente



Dr. José Matías Alvarado Mentado



Dr. Sergio Víctor Chapa Vergara



Dr. Luis Gerardo de la Fraga



Dra. Sonia G. Mendoza Chapa



iii



Agradecimientos

Al Centro de Investigación y de Estudios Avanzados del Instituto Politécnico
Nacional


Al Consejo Nacional de Ciencia y Tecnología
CVU: 261089



Agradezco al Dr. José Matías Alvarado Mentado por su apoyo y orientación en
este trabajo de tesis



A mis lectores, Dra. Sonia Guadalupe Mendoza Chapa, Dr. Luis Gerardo de la
Fraga y Dr. Sergio Víctor Chapa Vergara por su valiosa aportación a mi trabajo



v







A mis padres:



Manuel Yee González

y

Manuela Rendón Sánchez



A mis hermanos:



Cristo Manuel Yee Rendón

Ana Julia Yee Rendón

Zumey Yee Rendón

Bruce Yee Rendón



A mi esposa:



María Irene Torres Silvas

Por todo su cariño y amor que me ha brindado.



vii



Resumen

El Equilibrio de Nash (EN) es un concepto fundamental en Teoría de Juegos para formalizar

la cooperación entre los jugadores de un equipo con el objetivo de ganar el partido en disputa.

Para ganar en equipo, se requiere tanto el diseño de estrategias colectivas como combinación

positiva de las estrategias individuales. El EN permite caracterizar las estrategias colectivas tales

que a ningún jugador, individualmente, le resulte atractivo actuar de manera diferente a lo que la

estrategia colectiva indica. El EN es un concepto fundamental para formalizar la coordinación de

los jugadores, de tal manera que cada uno de ellos actúe para potenciar el beneficio del equipo y

además dejar cerrada la posibilidad de que algunos de los jugadores tuviera la opción de actuar de

otra manera, individualizada, sino quiere ir en perjuicio de si mismo.

En este trabajo se aplica el EN para identificar estrategias ganadoras en el juego de béisbol,

tanto en momentos en que el equipo juega a la ofensiva como a la defensiva. El objetivo es

identificar las situaciones y condiciones durante el desarrollo de un juego, tal que resulte

conveniente aplicar el modelo de EN para identificar las estrategias ganadoras del equipo.

En juegos de múltiples jugadores, el análisis de estrategias es de alto grado de complejidad,

razón por la cual se hace relevante computarizar eficientemente el cálculo del EN para realizar

tales análisis de estrategias en estos tipos de juegos.

Este trabajo se enfocó en el análisis y el estudio de las estrategias del juegos de béisbol, estas

estrategias fueron analizadas a través del EN, el cual permitió realizar razonamiento estratégico a

fin de encontrar las mejores estrategias colectivas para ser aplicadas durante el partido. A partir

de los resultados de este trabajo, se comprobó que el EN es uno de los conceptos más importantes

en Teoría de Juegos para el análisis de juegos no cooperativos.



ix



Abstract

Nash Equilibrium (NE) is a central concept in Game Theory, essential to formalize

cooperation among players on a team with the goal to win the game in dispute. Winning as a

team requires the design of collective strategies as a positive combination of individual strategies.

The NE allows to characterize the collective strategy such that any player, individually, is

attracted to act differently from what the collective strategy indicates. The NE is a fundamental

concept to formalize the coordination of players, so that each one acts to enhance the benefit of

the team and it closes leaving the possibility that players have the option to act otherwise,

individually, but wants adversely to affect itself.

This works applies the NE to identify winning strategies in the game of baseball, in both

cases, when the team plays offensively and defensively. The objective is to identify situations and

conditions during the course of a game, such that it is appropriated to apply the NE model to

identify winning strategies of the team.

In multiplayer games, strategy analysis presents a high degree of complexity, as it becomes

relevant, to efficiently compute the NE for such analysis of strategies in these games.

This work focused on the analysis and the study of the strategies of baseball games, these

strategies were analyzed by the EN, which allowed for strategic thinking to find the best

collective strategies to be implemented during the game. From the results of this work, we found

that the NE is one of the most important concepts in Game Theory to analyze non-cooperative

games.



xi



Índice general

Resumen ....................................................................................................................... ix

Abstract ......................................................................................................................... xi

Índice Figuras .............................................................................................................. xv

Índice Tablas .............................................................................................................. xvii

1

Introducción ................................................................................................. 1

1.1. Planteamiento del problema .............................................................. 1

1.2. Motivación ......................................................................................... 2

1.3. Objetivos ............................................................................................ 3

1.4. Arquitectura general del proyecto ..................................................... 4

2

Antecedentes ................................................................................................ 7

2.1. Teoría de Juegos ................................................................................ 7

2.2. Conceptos básicos.............................................................................. 8

2.3. Tipos de juegos ................................................................................ 10

3

Modelado formal del béisbol ..................................................................... 17

3.1. Descripción ...................................................................................... 17

3.2. Gramática libre de contexto ............................................................. 18

3.3. Autómata de pila .............................................................................. 23

3.4. Generador de jugadas ...................................................................... 26

3.5.

Jugadas de sacrificio ........................................................................ 29

3.6.

Jugadas clásicas del béisbol ............................................................. 30

3.7. Análisis cualitativo de las estrategias del béisbol ............................ 33



xiii



xiv



4

Equilibrio de Nash .................................................................................... 37

4.1. Antecedentes ................................................................................... 37

4.2. Formalización ................................................................................. 41

4.3. Estado del arte ................................................................................. 43

4.4. Autómatas de estado finito .............................................................. 48

4.5. Algoritmo del Equilibrio de Nash y análisis de perfiles ................. 50

5

Matrices de rentabilidad ............................................................................ 55

5.1. Análisis cuantitativo de estrategias ................................................. 55

5.2. Construcción de las matrices .......................................................... 56

5.3. Perfiles de juego .............................................................................. 57

6

Pruebas y análisis de resultados ................................................................ 59

6.1. Resultados de aplicar jugadas de sacrificio .................................... 59

6.2. Equilibrio de Nash aplicado a las estrategias del béisbol .............. 62

7

Discusión de resultados y trabajos relacionados ....................................... 69

7.1. Explicaciones y comentarios de las simulaciones .......................... 69

7.2. Análisis de costo de carreras usando el Equilibrio de Nash .......... 70

7.3. Trabajos relacionados ..................................................................... 70

8

Conclusiones y trabajo f