Comment (presque) toujours gagner à la bataille navale

You sunk mydestroyer/Andrew Malone Via FlickrCC Licence by

You sunk mydestroyer/Andrew Malone Via FlickrCC Licence by

La bataille navale n'est pas qu'une question de hasard. Un calcul de probabilités garantit de couler la flotte de son adversaire en un minimum de coups.

Avec la sortie de Battleship, on s’attend naturellement à une petite montée en flèche des ventes du jeu de la bataille navale (Battleships en VO). Les lecteurs s’en souviennent sans doute, les règles du jeu sont simples: chaque joueur déploie cinq navires –un porte-avions, un cuirassé, un croiseur, un sous-marin et un destroyer– sur une grille de dix cases sur dix et doivent tenter de couler les navires de l’adversaire en donnant l’abscisse et l’ordonnée des cases où ils pensent que les navires se trouvent.

Une bonne partie des joueurs tend à considérer que ce jeu est une question de chance, en visant des cases au hasard. Mais existe-t-il une meilleure stratégie? Si un de vos amis vous lance un défi à la bataille navale pendant les vacances, y a-t-il un moyen d’augmenter vos chances de victoire?

Eh bien oui. Nick Berry, consultant en technologie et président de DataGenetics, entreprise d’exploration de données basée à Seattle a méticuleusement établi plusieurs stratégies qui permettent d’améliorer vos chances de couler les navires de votre adversaire avant qu’il ne coule les vôtres. Ces méthodes ont été testées. Berry a créé des algorithmes sur ordinateur qui ont utilisé ses stratégies sur des centaines de millions de simulations afin de calculer leurs taux de réussite.

66 coups au hasard pour couler une flotte

Berry a commencé par tester la stratégie la plus courante, qu’il a baptisée Chasse/Cible. L’ordinateur débute en mode Chasse –c’est à dire tire au hasard jusqu’à ce qu’il trouve une cible. Lorsqu’il a touché, il s’acharne sur les cases adjacentes. Une fois le navire coulé, la chasse reprend jusqu’à l’acquisition d’une nouvelle cible. Dans les simulations de Berry, il faut en moyenne 66 coups pour couler la flotte ennemie. Cette approche fonctionne, mais elle fait la part très belle au hasard.

navale

Traduction: Initialement, l’algorithme débute en mode Chasse, tirant des coups au hasard. Au tour 3, il touche quelque chose et passe en mode Cible. Les quatre directions cardinales (N, S, E, O) sont toutes explorées comme localisations potentielles puisqu’adjacentes à une position connue. Tirant au nord (N) au tour suivant, l’ordinateur touche à nouveau sa cible. Les localisation N, E et W sont ainsi ajoutées au bouquet de «cibles potentielles» (Contrairement à S, déjà visité).

Pour améliorer la méthode Chasse/Cible, Berry a conçu une tactique combinant le mode Chasse avec le concept de parité mathématique. Voilà, grossièrement, l’idée: imaginez que la grille est colorée comme un échiquier, avec des carrés blancs et bleus. Le plus petit des navires (le destroyer), couvre deux cases et se trouve donc, obligatoirement, sur deux cases, une bleue et une blanche. Si l’on ne tire que sur les cases bleues, on frappe donc n’importe quel navire au moins une fois. Cette méthode permet alors de diviser par deux le nombre de cibles sur le plateau lorsque l’on est en mode Chasse. (Dès que l’on touche, on passe alors en mode Cible en attaquant les cases bleues et blanches jusqu’à ce que le navire soit complètement coulé.) Cette stratégie réduit légèrement le nombre de coups nécessaires pour couler la flotte de l’ennemi, 65 en moyenne.

Calculer la densité de probabilité des navires

La méthode la plus efficace conçue par Berry utilise une fonction de densité de probabilité, qui prend en considération les différentes manières dont les cinq navires peuvent être déployés sur le plateau. L’algorithme de Berry considère toutes les configurations possibles des cinq navires et calcule la probabilité, pour chaque case, d’être ou non occupée par un navire. Au départ du jeu, les navires peuvent naturellement se trouver n’importe où –les probabilités sont donc équivalentes pour chaque case.

Mais au fur et à mesure, on élimine de plus en plus de cases et l’on réduit d’autant le nombre de configurations –le porte-avions, long de cinq cases, ne peut se trouver sur un espace de quatre cases. Un joueur humain ne peut calculer les probabilités avec autant de précision que le modèle de Berry, mais peut garder cette stratégie à l’esprit. En considérant la longueur de chaque navire encore en lice et en tirant dans les zones où il peut se trouver, le taux de réussite est grandement amélioré. Lorsque l’ordinateur de Berry utilise cette méthode, il réduit le nombre de coups nécessaires pour l’emporter à une moyenne de 44.

La bataille navale demeure naturellement un jeu de hasard. Lorsque j’en ai discuté avec Berry, il a bien insisté sur le fait qu’il n’existe aucune méthode permettant à une machine ou à un humain de l’emporter à chaque fois. Cette part de hasard intrinsèque (à laquelle s’ajoute la part d’erreurs humaines) m’a sauté aux yeux lorsque j’ai tenté, successivement, les trois approches, Chasse/Cible, Chasse/Cible avec parité et Chasse/Cible avec parité et une tentative d’approche avec la densité de probabilité, me permettant de couler la flotte ennemie en 38, 41 et 55 coups respectivement. J’ai remporté deux des trois parties.

Berry, qui a travaillé durant près de dix ans au sein du département des jeux de Microsoft (aujourd’hui responsable de la production de la Xbox) s’est essayé à l’analyse de nombreux jeux de plateau classiques. Vous pourrez trouver ses différentes stratégies pour l’emporter au Risk, à Candyland (un jeu de parcours pour les petits) et à Serpents et Echelles sur son blog.

Aisha Harris
Stagiaire à Slate.com

Traduit par Antoine Bourguilleau

Partager cet article