Problème
Minimax est la façon dont les programmes de jeu choisissent leurs coups : supposez que les deux joueurs jouent parfaitement, notez chaque partie terminée et remontez les scores dans l'arbre de jeu. Le joueur au trait choisit l'enfant au meilleur score pour lui.
Le plateau est une chaîne de 9 caractères lue ligne par ligne (indices 0-8), avec "X", "O" ou "." pour une case vide. X joue toujours en premier : c'est donc à X de jouer quand les deux ont le même nombre de marques, et à O sinon.
Notez une partie terminée du point de vue du joueur au trait : +1 pour une victoire, 0 pour un match nul, -1 pour une défaite. Renvoyez la case vide dont le coup a le meilleur score minimax ; si plusieurs sont aussi bonnes, renvoyez le plus petit indice.
Implémentez best_move(board).
Entrée
board : Une position valide où personne n'a encore gagné et où au moins une case est vide.
Sortie
Renvoyez l'indice (0-8) du meilleur coup.
Contraintes
board contient exactement 9 caractères, chacun X, O ou .
La position peut apparaître dans une vraie partie, personne n'a gagné et au moins une case est vide
Exemples
Entrée :
board = "XX.OO...."
Sortie attendue :
expected = 2Entrée :
std::string board = "XX.OO....";
Sortie attendue :
long long expected = 2;Entrée :
string board = "XX.OO....";
Sortie attendue :
long expected = 2;Explication
X et O ont deux marques chacun, donc X joue. Jouer en 2 complète la ligne du haut et gagne immédiatement (+1).
Entrée :
board = "X..OO...X"
Sortie attendue :
expected = 5Entrée :
std::string board = "X..OO...X";
Sortie attendue :
long long expected = 5;Entrée :
string board = "X..OO...X";
Sortie attendue :
long expected = 5;Explication
X joue. O menace de compléter la ligne du milieu en 5. Tout autre coup laisse O gagner (-1), alors que bloquer en 5 mène à un match nul (0) : la réponse est donc 5.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Détermine à qui c’est le tour à partir des nombres de X et O, puis évalue récursivement chaque coup légal.
Indice 2
Attribue un score aux plateaux terminaux du point de vue du joueur courant, et choisis le coup qui maximise cette valeur.
Indice 3
Si plusieurs coups sont ex æquo, garde l’indice de la première case vide, et vérifie les victoires avant d’envisager d’autres coups.
Complexité attendue
temps O(9!), espace supplémentaire O(9)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.