Pour cette deuxième étape, vous allez implémenter la fonction best_move du fichier solver.py.
La fonction a pour but de calculer le meilleur coup à jouer pour un plateau et un joueur donnés.
Il s'agit ici d'une IA au sens classique du terme.
Pour cette partie du projet, vous êtes invités à travailler sur le résultat de l'étape précédente.
Normalement, les fichiers doivent se situer dans le répertoire projets/tictactoe de votre espace de stockage.
La fonction à implémenter, best_move, a deux paramètres :
board, le plateau de jeu, selon la représentation adoptée dans l'étape précédente.player, le joueur pour qui jouer (1 ou -1).La fonction doit retourner les coordonnées d'une case (sous la forme d'un tuple (x, y)) optimal à jouer, ou None s'il n'y a aucun coup à jouer (si le plateau est rempli).
La fonction doit laisser le plateau de jeu intact, c'est-à-dire que l'état du plateau doit être le même avant et après l'appel à la fonction. Cela n'empêche pas de modifier temporairement au sein de votre fonction l'état du plateau via la fonction play, pour autant que unplay soit appelé après.
Pour implémenter votre fonction, best_move fera appel à la fonction récursive minimax, qui a les mêmes paramètres mais retourne la valeur du jeu (-1, 0 ou 1) en plus du meilleur mouvement à effectuer (ou None si le plateau est plein).
Dans best_move, après l'appel à minimax, vous aurez ainsi comme information le meilleur coup à effectuer et la valeur du jeu.
Il vous restera simplement à retourner de la fonction uniquement le meilleur coup.
La fonction minimax implémentera l'algorithme du Minimax tel que vu en cours. Pour rappel, l'algorithme Minimax est un algorithme récursif qui cherche à déterminer le meilleur coup à jouer et la valeur du jeu qu'il est assurément possible d'obtenir par ce coup.
Lorsqu'il n'y a aucun coup à jouer, la valeur de retour attendue est None pour le coup à jouer et 0 pour la valeur du jeu.
Cependant, lorsqu'il y a un ou plusieurs coups possibles, il faut déterminer lequel est le meilleur.
Pour cela, il faudra calculer le score associé à chaque coup possible et retourner le coup dont le score est le plus élevé (pour le joueur 1) ou le plus bas (pour le joueur -1).
Afin de déterminer le score d'un coup, il faudra le simuler. Pour cela, vous pouvez faire appel à play. Il faudra cependant faire appel à unplay après avoir exploré un coup afin de rétablir l'état du plateau.
Si un coup amène à une victoire, alors son score est forcément de 1 (pour le joueur 1) ou de -1 (pour le joueur -1).
Autrement, si le coup n'amène pas directement à une victoire, il faudra faire un appel récursif à minimax sur le plateau modifié et pour le joueur adverse. Cet appel récursif donnera, entre autres, une valeur pour cette situation de jeu.
Une fois votre fonction best_move implémentée, vous pouvez tester votre IA et jouer contre elle en modifiant le code du fichier main.py.
if __name__ == '__main__':
# Pour faire jouer l'IA en deuxième...
start_ui(None, best_move)Vous pouvez essayer de faire jouer l'IA en premier, en deuxième, contre elle-même voire contre random_move. Vérifiez que tout fonctionne correctement !