Puissance 4

Étape 3

Dans cette étape, nous vous allez concevoir une IA qui allie Minimax avec les simulations de Monte-Carlo de l'étape précédente.

Utiliser directement la technique du Minimax sur le Puissance 4 prendrait beaucoup trop de temps. Même l'optimisation apportée par la méthode Alpha-Beta vue en cours ne suffit pas à elle seule à ramener le temps d'exécution à quelque chose de réalisable.

Pour contrer ce problème, vous allez coupler l'algorithme du Minimax avec les simulations de Monte-Carlo. L'idée de base est simple. On réalisera le Minimax sur une profondeur maximale donnée. Si lors de l'exploration d'une branche on se retrouve à la profondeur maximale et que l'issue du jeu n'est toujours pas déterminée, alors on lancera une simulation de Monte-Carlo pour estimer la valeur du jeu.

Vous avez déjà implémenté la fonction qui permet d'estimer la valeur d'un jeu grâce à la méthode de Monte-Carlo. Il s'agit de la fonction monte_carlo_eval que vous avez créée à l'étape précédente. Il restera simplement à implémenter une variante du minimax.

Pour arriver à une solution satisfaisante, il vous faudra jouer avec les paramètres de profondeur maximale et de nombre d'itérations pour les simulations. En effet, si ces valeurs sont trop grandes le temps d'exécution sera trop long. Si ces valeurs sont trop petites, le résultat sera de moindre qualité.

Une fois ceci réalisé, vous pourrez implémenter la technique Alpha-Beta afin d'optimiser le temps d'exécution de votre IA lors de l'étape suivante. D'autres pistes d'optimisation sont aussi proposées.

Instructions détailées

Dans le fichier solver.py de votre projet de Puissance 4, concevez la fonction minimax_monte_carlo dont le squelette est le suivant :

def minimax_monte_carlo(board, depth, iterations):
    pass

Le paramètre board de la fonction représente le plateau de jeu, depth la profondeur maximale explorable à ce point, et iterations le nombre d'itérations à utiliser pour les simulations de Monte-Carlo.

La fonction doit retourner une paire de valeurs qui indique le meilleur coup à jouer (un numéro de colonne) et la valeur du jeu (un nombre compris entre -1 et 1).

Pour rappel, la méthode du Minimax est une méthode récursive qui se déroule de la façon suivante :

Si le plateau de jeu est plein, le jeu est de valeur 0 et il n'y a aucun meilleur coup (None).

Au contraire, si le jeu n'est pas terminé, on inspecte chaque coup possible du joueur et on calcule la valeur du jeu qui en découle :

• Si le jeu amène à une victoire du joueur, la valeur du jeu est de 1 ou -1 selon le joueur.
• Sinon, on appelle récursivement la fonction sur le nouveau jeu pour en obtenir la valeur. Si la profondeur maximale est atteinte, on utilisera une simulation de Monte-Carlo à la place dans notre variante du Minimax.

La fonction doit ensuite retourner le coup qui amène au meilleur score pour le joueur (le score maximum pour le premier joueur, le score minimum pour le second), ainsi que la valeur du jeu ainsi obtenu.

Remarque : Il est aussi possible d'utiliser la variante Negamax de la méthode du Minimax. La variante n'est pas plus rapide d'exécution mais peut être plus simple à implémenter.

Une fois votre fonction minimax_monte_carlo implémentée, concevez la fonction best_move_minimax qui appelle minimax_monte_carlo avec les valeurs de votre choix pour depth et iterations et qui ne retourne que l'indication du coup à jouer.

def best_move_minimax(board):
    pass

Essayer votre code

Pour essayer l'IA obtenue à cette étaper, modifiez le code du script main.py et faites jouer votre IA contre vous.

if __name__ == "__main__":
    start_ui(best_move_minimax, None)

Il vous suffira ensuite d'exécuter le script afin de lancer une partie.