Où placer ses bateaux à la bataille navale : la carte des probabilités

Il n'existe pas de placement idéal unique à la bataille navale, mais il en existe de clairement mauvais. Dans notre simulation, une flotte couchée le long des bords a coûté environ 6 tirs de plus à un chasseur fondé sur les probabilités, alors que les flottes groupées au centre ou collées en un seul bloc ont été trouvées le plus vite. Un adversaire qui apprend vos habitudes efface tout avantage : à long terme, le mieux est de varier vos cachettes.

Je développe Torpedo, une bataille navale pour iPhone et iPad. Pour construire son adversaire informatique, il nous fallait des chiffres solides : où les bateaux se trouvent le plus souvent, et quelles façons de les cacher tiennent le coup. Nous avons écrit un simulateur, cartographié 5 millions de placements de flotte aléatoires et joué 400 000 parties pour tester cinq styles de placement contre quatre chasseurs différents. Les résultats bruts sont publics. Pour le tir, voyez notre guide comment gagner à la bataille navale.

Où les bateaux se trouvent-ils le plus souvent ?

Dans le jeu classique (bateaux de 5, 4, 3, 3 et 2 cases), les bateaux couvrent le plus souvent le centre de la grille. Sur 4 millions de placements aléatoires valables, la case E5 contenait un bateau dans 21,4 % des cas, et ses voisines F5, E6 et F6 sont statistiquement à égalité avec elle. Les coins n'en contenaient un que dans 8,0 % des cas. La moyenne de la grille est de 17 %, puisque la flotte occupe 17 cases sur 100.

L'explication est géométrique : davantage de positions passent par une case centrale. Comptez toutes les façons de placer un seul bateau de la flotte classique sur une grille vide : vous obtenez 760 positions. Parmi elles, 34 couvrent E5 et seulement 10 couvrent le coin A1. Pour le porte-avions de cinq cases seul, l'écart est de cinq contre un (10 positions par E5, 2 par A1). Nick Berry décrivait le même effet de bord en 2011 dans son analyse DataGenetics : moins de positions atteignent les bords et les coins.

La vraie carte est plus douce que ce décompte. Quand les cinq bateaux sont placés ensemble, ils se gênent, et le rapport entre le centre et un coin tombe de 3,4 sur la grille vide à 2,67 dans les placements réels. Un chasseur fondé sur les probabilités part de cette carte : c'est pour cela que ses premiers tirs vont au milieu.

Pourquoi la flotte de dix bateaux inverse-t-elle la carte ?

La flotte papier de dix bateaux (un bateau de 4, deux de 3, trois de 2 et quatre de 1, sans contact même par un coin), que Wikipédia donne comme courante en Belgique (Wikipédia), produit la carte inverse. Sur 1 million de placements aléatoires valables, ce sont les cases du bord qui contiennent le plus souvent un bateau : C1, H1, A3, J3, A8, J8, C10 et H10, chacune autour de 25,7 %. L'anneau situé une case à l'intérieur du bord est le plus froid (B9 à 14,7 %), et le centre se situe à 18,2 %.

C'est la règle sans contact qui provoque l'inversion. Chaque bateau a besoin d'une bordure d'eau vide autour de lui. Un bateau au bord voit une partie de cette bordure coupée par le bord de la grille : il consomme moins de mer et laisse plus de place aux neuf autres. Bien plus de placements valables mettent donc des bateaux au bord. Le deuxième anneau est froid, très probablement parce qu'un bateau à cet endroit bloque la ligne du bord voisine sans profiter de cette réduction.

C'est la plus grande surprise de nos données. Le simple décompte des positions d'un seul bateau sur une grille vide désigne toujours le centre (36 positions par une case centrale contre 16 par un coin) : toute méthode fondée sur ce décompte ouvre le feu au mauvais endroit avec cette flotte. Si vous jouez à dix bateaux, un chasseur qui connaît la vraie carte commencera par les bords, parce que c'est là que les bateaux se trouvent le plus souvent. Nous n'avons mené le test de placement ci-dessous qu'avec la flotte classique.

Quel placement tient le plus longtemps ? L'expérience

Nous avons testé cinq styles de flotte pour la flotte classique, 20 000 parties pour chaque couple style et chasseur. Chaque flotte a été tirée au hasard parmi tous les placements valables qui respectent le style :

• Aléatoire : n'importe quel placement valable, tiré uniformément au hasard.
• Couchés le long des bords : chaque bateau se trouve entièrement sur l'anneau extérieur de la grille.
• Chaque bateau touche le bord : chaque bateau a au moins une case sur l'anneau extérieur.
• Carré central de 6×6 : tous les bateaux dans le bloc C3 à H8.
• Tous les bateaux collés : les cinq bateaux forment un seul groupe d'un tenant.

Les quatre chasseurs étaient un joueur en chasse et ciblage avec damier, la méthode de référence de la densité de probabilité, le niveau Difficile de l'ordinateur de Torpedo, et son niveau Expert après avoir vu 20 flottes du même style. Le tableau donne le nombre moyen de tirs dont chaque chasseur a eu besoin pour couler toute la flotte. Plus le chiffre est élevé, mieux c'est pour celui qui se cache.

Ce que disent ces résultats

• Les bords battent les chasseurs de probabilités. Une flotte couchée le long des bords a demandé 6,2 tirs de plus au chasseur de probabilités qu'une flotte aléatoire, et 5,9 de plus au niveau Difficile de Torpedo. La part des parties que ce chasseur a terminées en 50 tirs ou moins est tombée de 73,5 % à 42,0 %.
• Les bords ne trompent pas un joueur en damier. La même flotte au bord a été trouvée un peu plus vite par le chasseur en damier (53,4 tirs au lieu de 55,1). Un bateau au bord a moins de cases voisines, donc après une touche il reste moins de mauvaises cases à sonder.
• Toucher le bord est une version affaiblie. Les bateaux qui ne touchent le bord que par un bout ont gagné moins, environ 4 tirs contre le chasseur de probabilités (49,5).
• Le centre est la pire cachette. Une flotte dans le carré central de 6×6 a perdu plus vite qu'un placement aléatoire face à tous les chasseurs, et l'Expert l'a trouvée en 36,3 tirs une fois l'habitude apprise.
• Coller ses bateaux se retourne contre vous. Un seul bloc a été trouvé en 43,3 tirs par le chasseur de probabilités et en 47,2 par le chasseur en damier. Seuls 0,98 % des placements aléatoires forment un groupe d'un tenant : c'est donc un choix délibéré, et un mauvais choix. Avec la règle française courante, où les bateaux ne doivent pas être adjacents (Wikipédia), ce style est de toute façon interdit.

Le meilleur placement dépend-il de l'adversaire ?

Oui, et c'est pour cela qu'aucun placement ne gagne toujours. Face à un ordinateur, ou un ami, qui commence par le milieu et joue les probabilités, une flotte au bord vous fait gagner environ 6 tirs, un gros avantage dans un jeu où le premier qui finit l'emporte. Face à quelqu'un qui balaie la grille en damier, les bords ne vous apportent rien et vous coûtent un tir ou deux.

Nous n'avons pas mesuré de vrais joueurs : prenez ceci comme un repère, pas comme une loi. Le chasseur en damier représente un joueur méthodique, le chasseur de probabilités un joueur qui vise là où les bateaux sont le plus probables. La plupart des joueurs se situent entre les deux.

Le jeu dans le jeu : et si votre adversaire a lu cet article ?

Si votre ami lit cet article, votre flotte au bord devient un handicap. Il tirera d'abord sur les bords, et vous perdrez vos 6 tirs d'avance, probablement plus. C'est exactement ce que fait le niveau Expert de Torpedo : après 20 parties contre un joueur qui colle toujours ses bateaux aux bords, il a coulé la flotte en 46,8 tirs au lieu des 50,7 dont le niveau Difficile a besoin.

La parade consiste à laisser votre adversaire dans le doute :

1. Alternez les styles. Utilisez souvent les bords contre un adversaire fort, mais pas à chaque partie.
2. Glissez des placements entièrement aléatoires. Une flotte aléatoire coûte à peu près autant à tous les chasseurs et ne leur donne aucun schéma à apprendre.
3. Ne vous cachez jamais au centre ni en un seul bloc. Ce sont les seuls styles qui ont perdu face à tous les chasseurs.
4. Surveillez vos propres habitudes. Si votre torpilleur finit toujours dans le même coin, un bon adversaire le remarquera.

Comment une IA de bataille navale choisit-elle où tirer ?

La méthode de chasse la plus forte de nos tests est la densité de probabilité, décrite par Berry en 2011. En clair :

1. Pour chaque bateau ennemi encore à flot, listez toutes les positions qu'il peut occuper sans passer par un tir à l'eau connu ni par un bateau coulé.
2. Pour chaque case, comptez combien de ces positions la couvrent.
3. Tirez sur la case qui a le plus gros total.
4. Après une touche, ne comptez que les positions qui passent par elle : les tirs suivants suivent le bateau touché.
5. Recommencez après chaque tir, puisque chaque réponse élimine des positions.

Cette méthode a coulé la flotte classique en 45,0 tirs en moyenne dans notre simulation, contre 95,4 au hasard. Elle explique aussi pourquoi les flottes au bord lui résistent : son décompte favorise le centre, alors elle y cherche en premier.

Le niveau Difficile de Torpedo fonctionne ainsi. Tant qu'un bateau est touché, il compte les positions qui passent par les touches et les pondère par le carré du nombre de touches qu'elles couvrent ; il choisit ses huit premiers tirs de recherche au hasard parmi les cinq meilleures cases, pour que son ouverture ne se répète pas. Il a obtenu 44,9 tirs en moyenne. Le niveau Expert abandonne l'ouverture au hasard et ajoute une mémoire : après chaque partie, il note où se trouvaient vos bateaux, et pendant sa recherche il multiplie le total de chaque case par un facteur allant jusqu'à 1,6 pour les cases que vous utilisez souvent. Aucun des deux niveaux ne voit votre grille pendant la partie. L'Expert n'apprend votre flotte qu'une fois la partie terminée, comme une personne se souviendrait de votre style.

Les deux niveaux comptent les positions bateau par bateau, ce qui désigne le centre sur une grille vide. Comme le montre la carte à dix bateaux, les bords seraient un meilleur point de départ contre la flotte sans contact.

Le bouton Placement aléatoire de Torpedo donne-t-il un placement vraiment aléatoire ?

Pas tout à fait, et nous préférons le dire. Le placement automatique de Torpedo, utilisé pour la flotte de l'ordinateur et pour le bouton Placement aléatoire, pose les navires un par un, du plus grand au plus petit. Avec la flotte classique, il est donc un peu plus centré qu'un tirage vraiment aléatoire (les cases centrales contiennent un navire dans 22,2 % des cas au lieu de 21,4 %), et presque uniforme avec la flotte de dix bateaux au lieu de favoriser les bords. Les résultats de l'ordinateur changent à peine. Si vous voulez profiter de l'effet de bord décrit ici, placez vos navires à la main.

Pour les règles des deux flottes, voyez notre règle de la bataille navale. Pour tester des placements avec un ami et un crayon, notre bataille navale à imprimer fournit une grille gratuite, et la page des fonctionnalités de Torpedo présente les niveaux de l'ordinateur et les modes de jeu.

Les questions qu’on nous pose