Implementación del juego Master Mind en Android - solución mediante algoritmos genéticos

Abstract

A genetic algorithm is a search algorithm that consists of a series of steps inspired by the processes of natural evolution, such as reproduction and mutation. In this thesis the game Master Mind (also called Cows and Bulls) for Android was implemented and a genetic algorithm to solve it in Unity. Master Mind is a board game for two players that uses a board with tokens of various colors. The player called Codemaker is in charge of creating a secret code of length W, which consists of a combination of color tokens, and is responsible for rating attempts to discover the secret code. The player called Codebreaker will try to guess the secret code in a maximum of H attempts. The problem of solving Master Mind is to find a combination among a large number of combinations determined by the type of board. It is not possible to try all the combinations until finding the solution because you only have H attempts, so it is necessary to use some method like Genetic Algorithms that does not need to compare all the combinations against the secret code to find it. Although the Genetic Algorithm has only H attempts or opportunities to qualify the secret code against the combinations proposed by the user, the Genetic Algorithm performs more than H attempts or ratings among its population. In this thesis, a Genetic Algorithm was implemented that uses a fitness function to find a consistent combination and present it as a possible solution. In addition, tests were performed to verify its proper functioning.

Un algoritmo genético es un algoritmo de búsqueda que consiste en una serie de pasos inspirados en los procesos de evolución natural, como lo son la reproducción y la mutación. En esta tesis se implementó el juego Master Mind (también llamado Cows and Bulls) para Android y un algoritmo genético para solucionarlo en Unity. Master Mind es un juego de mesa para dos jugadores que utiliza un tablero con chas de varios colores. El jugador llamado Codemaker se encarga de crear un código secreto de longitud W, el cual consiste en una combinación de chas de colores, además se encarga de calificar los intentos por descubrir el código secreto. El jugador llamado Codebreaker intentar adivinar el código secreto en un máximo de H intentos. El problema de resolver Master Mind es encontrar una combinación entre un gran número de combinaciones determinado por el tipo de tablero. No es posible intentar con todas las combinaciones hasta encontrar la solución porque solo se tienen H intentos, por lo que es necesario utilizar algún método como Algoritmos Genéticos que no necesite comparar todas las combinaciones contra el código secreto para encontrarlo. A pesar que el Algoritmo Genético solo tiene H intentos u oportunidades de calificar el código secreto contra las combinaciones propuestas por el usuario, el Algoritmo Genético realiza más de H intentos o calificaciones entre su población. En esta tesis se implementó un Algoritmo Genético que utiliza una función fitness para encontrar una combinación consistente y presentarla como una posible solución. Además, se realizaron pruebas para comprobar su buen funcionamiento.