Uso de algoritmos genéticos para búsqueda y evaluación de estrategias en HU-NLHE TRABAJO DE FIN DE GRADO Doble Grado en Ingeniería Informática y Matemáticas Ignacio Funke Prieto Dirigido por el Doctor Manuel Núñez Departamento de Sistemas Informáticos y Computación Facultad de Informática Universidad Complutense de Madrid Junio 2015 i Documento maquetado con TEX S v.1.0+. Uso de algoritmos genéticos para búsqueda y evaluación de estrategias en HU-NLHE Trabajo de fin de grado Ignacio Funke Prieto Dirigido por el Doctor Manuel Núñez Departamento de Sistemas Informáticos y Computación Facultad de Informática Universidad Complutense de Madrid Junio 2015 A Enrique y Arantxa Agradecimientos En primer lugar, quiero dar las gracias a mi director, Manuel Núñez, por ha- ber conseguido despertar en mí el interés por el NLHE y por haberme guiado con soltura por el largo pero ameno camino que detallan estas páginas. Innumerables correos y reuniones, algunas de ellas a distancia, han ido dando forma a este Tra- bajo, donde sus aportaciones, mediante intrigantes ideas y consejos de inestimable valor ante las pequeñas piedras que iban apareciendo durante el camino, han sido piezas centrales en su composición. Y quiero dar también las gracias a Marco Antonio y Pedro Pablo Gómez, pro- fesores de esta facultad, por haber desarrollado y puesto a disposición del público TEXiS, una maravillosa plantilla de LATEX para tesis doctorales y trabajos de fin de grado con la que he ahorrado mucho tiempo y esfuerzo durante la composición de este Trabajo en detalles que de otra forma habrían sido verdaderos quebraderos de cabeza. vii Resumen El NLHE es un juego muy atractivo, desde el punto de vista de la inteligencia artificial, pues se trata de un juego de información imperfecta, con una alta com- ponente de azar a corto plazo y caracterizado por un espacio de estados de gran magnitud. Por ello, existen numerosos trabajos de investigación en busca de crear agentes inteligentes que sean capaces de jugar de forma óptima. En este trabajo presentamos una primera aproximación al mundo de la creación de agentes de poker y lo enfocamos a la aplicación de técnicas evolutivas, en concreto, al uso de algoritmos genéticos. Nos centraremos en un escenario más reducido al gene- ral, concretamente, en la variante en la que se restringe el número de jugadores a dos, Heads Up. Además, suponemos que las opciones a tomar en la mano se deciden preflop e imponemos limitaciones en la ronda de apuestas. En este marco, creamos jugadores con capacidades evolutivas que siguen estrategias sencillas y que evolucionamos hasta la solución buscada mediante un mecanismo de torneos. En este tipo de trabajo cobran especial importancia los mecanismos para estudiar gráficamente la exploración de los espacios de jugadores. Como resultado final, es posible concluir que los algoritmos genéticos se comportan bien a la hora de encontrar soluciones eficientes en este marco limitado, pero tienen dificultades a la hora de determinar decisiones óptimas conforme aumenta la complejidad de las decisiones que tienen que tomar los jugadores. Palabras clave: Agentes de poker, Algoritmos genéticos, Heads Up, NLHE, Poker. ix