1996 | ReviewPaper | Buchkapitel
Solving MasterMind using GAs and simulated annealing: A case of dynamic constraint optimization
verfasst von : J. L. Bernier, C. Ilia Herráiz, J. J. Merelo, S. Olmeda, A. Prieto
Erschienen in: Parallel Problem Solving from Nature — PPSN IV
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
MasterMind is a game in which the player must find out, by making guesses, a hidden combination of colors set by the opponent. The player lays a combination of colors, and the opponent points out the number of positions the player has found out (black tokens) and the number of colors that are in a different place from the hidden combination (white tokens). This problem can be formulated in the following way: the target of the game is to find a string composed of l symbols, drawn from an alphabet of cardinality c, using as constraints hints that restrict the search space. The partial objective of the search is to find a string that meets all the constraints made so far the final objective being to find the hidden string.This problem can also be located within the class of constrained optimization, although in this case not all the constraints are known in advance; hence its dynamic nature.Three algorithms playing MasterMind have been evaluated with respect to the number of guesses made by each one and the number of combinations examined before finding the solution: a random-search-with-constraints algorithm, simulated annealing, and a genetic algorithm. The random search and genetic algorithm at each step plays the optimal solution i.e., the one that is consistent with the constraints made so far, while simulated annealing plays the best found within certain time constraints. This paper proves that the algorithms that follow the optimal strategy behave similarly, getting the correct combination in more or less the same number of guesses; between them, GA is better with respect to the number of combinations examined, and this difference increases with the size of the search space, while SA is much faster (around 2 orders of magnitude) and gives a good enough answer.