Pour cette deuxième étape, vous allez implémenter des fonctions dans le but de déterminer le prochain code à jouer pour deviner au plus vite la solution au Mastermind.
all_solutionsLa première fonction à implémenter est all_solutions. La fonction a deux paramètres, size et colors. Le paramètre size indique la longueur du code et colors le nombre de couleurs. La fonction doit retourner la liste de tous les codes possibles de la longueur donnée et utilisant les couleurs indiquées.
def all_solutions(size, colors):
passIl est possible d'implémenter cette fonction relativement simplement de manière récursive sur la taille des codes.
Attention cependant au fait qu'il existe bien un code de longueur 0, le code [] !
filter_solutionsLa fonction suivante est filter_solutions.
Le but de cette fonction est d'éliminer toutes les solutions qui ne sont pas compatibles avec la réponse donnée à un code proposé.
La fonction a trois paramètres :
solutions, une liste de solutions possiblescandidate, un code essayépegs, le nombre de pions rouges et de pions blancsLa fonction doit retourner une nouvelle liste qui contiendra uniquement les solutions de solutions qui sont compatibles avec le code essayé (candidate) et les pions indiqués (pegs).
def filter_solutions(solutions, candidate, pegs):
passbest_moveReste ensuite la fonction best_move à implémenter. La fonction a un unique paramètre, solutions, qui liste les solutions encore possibles.
Le but est de retourner une de ces solutions.
Il y a plusieurs façons de procéder. Ci-dessous sont listées quelques méthodes.
La méthode la plus simple est de simplement jouer à chaque coup une des solutions possible... au hasard. Les résultats obtenus sont de façon assez surprenante assez bons !
La méthode suivante est une méthode pas tout à fait optimale, mais qui donne de très bons résultats en pratique : Essayer le code qui au pire des cas élimine le plus possible de solutions restantes à chaque étape.
Pour cela, on attribue un score à chaque code possible de proposer. Le score correspond au nombre de solutions assurément éliminées si le code était proposé.
Pour calculer le score d'un code, on examine toutes les solutions possibles restantes et on calcule le nombre de pions rouges et blancs obtenus dans ce cas. On compte ensuite le nombre de solutions restantes éliminées. On ne garde comme score final pour le code proposé que le nombre minimum de solutions éliminées. Il s'agit la du nombre de solutions assurément éliminées par le code.
Une fois le score de chaque code possible calculé, on retourne celui avec le plus haut score.
Cette méthode est relativement complexe à utiliser et peut être relativement lente.
La troisième méthode est une méthode basée sur une simulation de Monte-Carlo. Comme pour la méthode précédente, on cherche à calculer un score pour chaque code à possible à proposer. On retourne ensuite le code dont le score est le plus élevé.
Pour calculer le score d'un code C, on répète la procédure suivante un nombre n de fois : On choisit au hasard une solution A et une solution B parmi les solutions possibles, puis on compare les pions obtenus si A est la bonne solution aux pions obtenus si B est la bonne solution. Dans le cas où les pions obtenus dans les deux sont différents, on incrémente le score du code C.
Ainsi, les codes qui en moyenne éliminent le plus de solutions restantes seront plus souvent proposés par cette méthode.
Suivant le nombre d'itérations n choisi, cette méthode peut être très rapide à exécuter.
Finalement, une façon de procéder pour obtenir un coup optimal consiste à appliquer la technique du Minimax (voire d'Alpha-Beta) au Mastermind. Dans ce cas, le score est le nombre de coups joués dans la partie avant d'avoir deviné le code. Le joueur qui détermine le code essaie de le maximiser, le joueur qui cherche le code doit le minimiser. Cette technique peut être difficile à implémenter et très longue à exécuter.