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.
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.