L'algorithme chasse/cible : comment l'IA joue à la Bataille Navale
Lorsque vous affrontez l'ordinateur sur notre Bataille Navale en ligne, vous jouez contre un algorithme soigneusement conçu. L'approche la plus répandue pour programmer une IA de Bataille Navale s'appelle l'algorithme chasse/cible (hunt/target en anglais). Découvrons ensemble comment il fonctionne et pourquoi il est si efficace.
Le principe général
L'algorithme chasse/cible repose sur deux phases distinctes qui alternent au fil de la partie. La première phase, appelée chasse, consiste à rechercher les navires ennemis en tirant sur des cases réparties sur la grille. La seconde phase, appelée cible, se déclenche dès qu'un tir touche un navire : l'IA concentre alors ses efforts pour couler le navire détecté avant de reprendre la chasse.
Phase 1 : la chasse
Tir aléatoire intelligent
Pendant la phase de chasse, l'IA ne tire pas véritablement au hasard. Elle utilise la règle de parité : en ne ciblant que les cases d'une couleur sur l'échiquier (une case sur deux), elle garantit de toucher chaque navire tout en divisant par deux le nombre de cases à explorer. Cette optimisation est cruciale car elle réduit considérablement le nombre moyen de tirs nécessaires.
Carte de densité
Les versions plus avancées de l'algorithme vont encore plus loin. Plutôt que de choisir aléatoirement parmi les cases de parité, l'IA calcule une carte de densité de probabilité. Pour chaque case non encore tirée, elle compte le nombre de positions possibles où un navire restant pourrait se trouver en passant par cette case. Les cases avec le score le plus élevé sont ciblées en priorité. En pratique, les cases centrales obtiennent naturellement un score plus élevé en début de partie, car davantage de navires peuvent y être placés.
Phase 2 : le ciblage
Exploration des cases adjacentes
Dès qu'un tir touche un navire, l'IA bascule en mode cible. Elle ajoute les quatre cases adjacentes (nord, sud, est, ouest) à une file d'attente prioritaire. Le tir suivant sera dirigé vers l'une de ces cases. Si ce deuxième tir touche également, l'IA déduit l'orientation du navire (horizontale ou verticale) et poursuit dans cette direction.
Détermination de l'orientation
Avec deux touches alignées, l'algorithme sait que le navire est orienté soit horizontalement, soit verticalement. Il continue à tirer dans la même direction jusqu'à obtenir un tir à l'eau ou un « coulé ». Si le tir tombe à l'eau sans que le navire soit coulé, l'IA revient à la première touche et explore la direction opposée. Cette logique permet de couler un navire en un minimum de coups.
Gestion des files d'attente
L'un des aspects les plus subtils de l'algorithme concerne la gestion de plusieurs navires touchés simultanément. Il arrive que l'IA touche un deuxième navire alors qu'elle cherche à couler le premier. Dans ce cas, les cases adjacentes du nouveau navire sont également ajoutées à la file. L'IA traite ces cibles par priorité, en se concentrant sur la séquence la plus prometteuse.
Optimisations avancées
Élimination des cases impossibles
Dans certaines variantes de la bataille navale (notamment la version russe), deux navires ne peuvent pas se toucher : une IA conçue pour ce ruleset peut alors marquer toutes les cases adjacentes à un navire coulé comme « impossibles » et accélérer encore la phase de chasse. Dans les règles classiques (Hasbro / Milton Bradley) et dans notre version en ligne, le contact entre navires reste autorisé : cette optimisation ne s'applique pas, l'IA se contente de purger sa file de cibles après un coulé.
Adaptation dynamique de la parité
À mesure que les navires sont coulés, la taille du plus petit navire restant peut changer. Si seuls des navires de 3 cases ou plus subsistent, l'IA peut passer à un espacement de tir de 3 au lieu de 2, réduisant encore le nombre de tirs nécessaires en phase de chasse. Cette adaptation dynamique est l'une des clés d'une IA performante.
Performances de l'algorithme
Un joueur tirant complètement au hasard a besoin en moyenne de 96 tirs pour couler tous les navires. Avec la simple règle de parité, ce nombre tombe à environ 65 tirs. L'algorithme chasse/cible complet, avec carte de densité et optimisations, réduit cette moyenne à environ 42 tirs, soit moins de la moitié du hasard pur. Les meilleures implémentations atteignent même des moyennes proches de 38 tirs. Cette quête de l'algorithme optimal se retrouve dans d'autres jeux de logique, comme le Mastermind et ses algorithmes de résolution, tandis que la reconnaissance de patterns est au cœur des techniques avancées du Démineur.
Comment battre l'IA ?
Connaître le fonctionnement de l'algorithme vous donne un avantage stratégique pour le placement de vos navires. Puisque l'IA privilégie les cases centrales et utilise la parité, vous pouvez tenter de placer vos navires en bordure de grille ou de manière à contourner le motif de parité. Mais attention : une IA avancée finira toujours par vous trouver.
Testez par vous-même l'efficacité de cet algorithme en jouant une partie sur notre Bataille Navale en ligne ! Observez les tirs de l'ordinateur et essayez d'identifier les phases de chasse et de ciblage en action.
