Une plainte assez fréquente dans les jeux vidéo est que l'intelligence artificielle des adversaires prend de mauvaises décisions. Pour cette raison, dans certains cas, ils trichent directement, mais parfois c'est aussi le contraire, et ils présentent des stratégies très efficaces dans des jeux que l'on peut considérer comme « simples ». L'une des raisons est l'application du théorème Minimax, un algorithme qui a pour objectif de minimiser la perte maximale attendue dans des jeux à deux participants, avec une information parfaite pour les deux parties.
De nombreux jeux cachent des informations aux participants dans le cadre de leur mécanique. Sans aller trop loin, pensez au « brouillard de guerre » des jeux classiques (StarCraft et Civilization viennent à l'esprit). Cette ressource permet à l'intelligence artificielle d'invoquer 20 ou 30 unités par magie sans que vous le sachiez (entre autres choses), et son élimination est une étape essentielle, que ce soit en envoyant des unités explorer, ou en développant des technologies qui annulent son effet (comme les satellites dans Civ).
Mais que se passe-t-il lorsque l'information est parfaite ? Comment se comporte une intelligence artificielle quand il n'y a rien à cacher, et que tous les éléments de la partie sont connus dès le début ? L'une des nombreuses possibilités pour le développeur est l'implémentation du théorème Minimax. La description officielle nous parle d'une « méthode de décision pour minimiser la perte maximale attendue », et cela peut sembler simple en surface, mais mérite une exploration plus approfondie :
Théorème Minimax : des solutions optimales pour les jeux à somme nulle
La chaîne BitBoss fait un excellent travail en résumant l'algorithme Minimax, et le mieux est que cela lui prend moins de quatre minutes. En gros, Minimax fonctionne dans les jeux à somme nulle, c'est-à-dire que notre gain ou avantage devient une perte pour l'adversaire. Les échecs sont un exemple classique de jeu à somme nulle avec information parfaite, mais la vidéo nous emprunte une route plus simple, en utilisant comme référence le morpion.
Chaque phase de la partie peut être définie par un nombre, positif pour un joueur, et négatif pour l'autre. La stratégie de l'algorithme Minimax cherche à sélectionner le meilleur coup disponible, en supposant que l'adversaire sélectionnera également le meilleur coup contre vous. Si une intelligence artificielle Minimax atteint la victoire avec un nombre positif, ses décisions essaieront de suivre le chemin qui favorise ce nombre.
Le graphique nous montre les six derniers coups possibles d'une intelligence artificielle dans une partie de morpion. Quatre d'entre eux expriment une victoire pour l'IA (jaune) avec une condition de 1, et les deux autres pour le joueur humain (bleu), avec -1. Les coups sont analysés de bas en haut, ou d'arrière en avant : comme il ne reste qu'un coup à l'intelligence artificielle, les valeurs pour chacun remontent à l'étape précédente. En suivant la même logique, le joueur humain a deux coups qui lui garantissent un -1, et une troisième qui l'oblige à choisir 1. Par conséquent, l'IA s'assure la victoire en mettant la pression sur cette voie, qui commence par une croix au centre.
Évidemment, c'est un exemple trop simple, et possible uniquement grâce aux limites naturelles du morpion. Si nous transposons la méthode Minimax à des jeux de haute complexité comme les échecs ou le go, le nombre d'états à vérifier croît de manière exponentielle, et l'application de Minimax devient irréalisable. Une solution possible est de limiter la profondeur d'exploration, et en général, c'est plus que suffisant pour donner une raclée aux n00bs.
