Parfois on tombe sur le net sur des articles traitant des jeux de société connus et datant de plusieurs décennies. Des articles vantant les mérites des jeux auxquels vos grands parents jouaient déjà et qui ont tout de même assez mal vieilli (oui, j'apporte cette précision car certains jeux qui ont quelques siècles de vie n'ont vraiment rien à leur envier).

Bref, souvent rien d'intéressant dans ce type de lecture.

Et puis, nous sommes tombés sur ça :

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, à La bataille navale. 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.

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.

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.

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...