Pour l'étape 2 de ce projet, vous allez concevoir une heuristique pour déterminer la valeur d'une position au puissance 4 grâce à la technique des simulations de Monte-Carlo.
random_playoutCommencez par implémenter dans le fichier solver.py la fonction random_playout. La fonction a le squelette suivant :
def random_playout(board):
passLa fonction doit permettre de jouer une partie aléatoire depuis un certain board.
On partira du principe que le board représente une position de jeu où aucun des joueurs n'a réussi à gagner.
À chaque étape, on choisira un coup au hasard parmi les coups possibles.
La fonction retournera un 1 si la partie se termine en une victoire du joueur 1, un -1 si la partie se termine en une victoire du second joueur et un 0 en cas de partie nulle.
Indice : Vous pouvez implémenter cette fonction de manière récursive ou à l'aide d'une boucle. Une boucle pourra être légérement plus rapide.
Attention : La fonction doit faire en sorte de laisser le board intact après avoir terminé la partie.
Si vous utilisez une boucle pour votre implémentation, il faudra donc mémoriser la liste des coups joués et appeler la méthode unplay sur ces coups et dans l'ordre approprié.
monte_carlo_score_moveEnsuite, implémentez dans le fichier solver.py la fonction monte_carlo_score_move dont le squelette est présenté ci-dessous.
def monte_carlo_score_move(board, column, iterations):
passOn partira du principe que la colonne indiquée est un coup valide étant donné l'état du jeu.
Le but de la fonction est de retourner un score entre -1 et 1 pour indiquer à quel point jouer un jeton dans une colonne donnée est favorable pour tel ou tel joueur. Un score proche de 1 indique un coup favorable pour le premier joueur et un score proche de -1 un coup favorable pour le second.
Si le coup est immédiatement gagnant, alors la réponse est immédiatement 1 ou -1, selon le joueur à qui le tour était de jouer.
Cependant, si le coup n'est pas immédiatement gagnant, il faudra calculer un score à l'aide de simulations.
Pour cela, vous devrez faire appel un nombre iterations de fois à la fonction random_playout et aggréger les résultats en un score entre -1 et 1.
monte_carlo_evalEnsuite, dans le même fichier, implémentez la fonction monte_carlo_eval, dont le but sera de retourner la meilleure colonne à jouer (identifiée par son numéro) et le score de ce coup.
def monte_carlo_eval(board, iterations):
passS'il n'y a aucun coup possible à jouer, on s'attend à None comme meilleur coup et à 0 comme valeur du jeu.
Le paramètre iterations indique le nombre d'itérations à effectuer au maximum pour chacun des coups.
best_move_monte_carloFinalement, implémentez la fonction best_move_monte_carlo dont le but est, étant donné uniquement un board, de retourner un bon coup à jouer, ou None si aucun coup n'est possible.
def best_move_monte_carlo(board):
passVotre fonction fera très certainement usage de monte_carlo_eval.
Le nombre d'iterations que vous utiliserez pour monte_carlo_eval est à fixer. Un nombre trop petit et le score sera peu fiable, un nombre trop grand et les simulations prendront trop de temps. À vous de juger quelle valeur est la plus adéquate.
Pour essayer votre IA basée uniquement sur les simulations de Monte-Carlo, modifiez le code du script main.py et faites jouer votre IA contre vous.
if __name__ == "__main__":
start_ui(best_move_monte_carlo, None)Il vous suffira ensuite d'exécuter le script afin de lancer une partie.