Stratégies en cuirassé

Question

Dans le jeu de la bataille navale, quelles sont les meilleures stratégies pour

1. Placer les navires
2. Tirer sur d'autres navires

Veuillez également fournir une explication de vos stratégies. TIA

Les règles sont les suivantes :

• Les deux joueurs placent leurs navires sur une grille de 10x10.
• Les navires doivent être placés de manière à ce que adjacent à un navire n'est que de l'eau .
• La réaction de l'adversaire à chaque tir est l'une des trois suivantes : HIT, MISS ou SUNK .
• Chaque joueur dispose des navires suivants :
  • 1 navire de longueur 5
  • 2 navires de longueur 4
  • 3 navires de longueur 3
  • 4 navires de longueur 2

Answer 1

La stratégie de placement découle de la stratégie optimale de tir, commençons donc par le tir.

Pour tirer, procédez comme suit :

1. Commencez dans une partie aléatoire du tableau. Passez à l'étape 2.

2. Vérifiez toutes les N cases à partir de votre point de départ, où N est le plus petit navire adverse restant (N = 2 pour commencer). Si vous avez déjà une grille de recherche établie dans une autre partie du plateau, vous devez utiliser la même grille de recherche dans cette partie du plateau. Vous devez explorer dans une direction aléatoire chaque fois que vous élargissez votre grille de recherche. Si vous ne touchez pas, restez à l'étape 2. Si vous trouvez, passez à l'étape 3.

3. Vérifiez les cases adjacentes à celle que vous avez touchée. Lorsque vous découvrez la direction d'un navire, continuez à vérifier dans cette direction jusqu'à ce que vous couliez un navire. Une fois que vous avez coulé un navire, retournez à l'étape 1. Notez qu'il existe un cas rare où deux navires peuvent être parallèles, donc si vous avez deux touches avec des manques de chaque côté, vérifiez l'autre direction.

Par exemple, avec N = 3, vous essayez de balayer un motif comme celui-ci :

X . . X . . X
. X . . X . .
. . X . . X .
X . . X . . X
. X . . X . .
. . X . . X .

Il s'agit du modèle le plus clair (le plus petit nombre de suppositions totales) qui est garanti pour trouver tous les navires.

Dans ces conditions, la meilleure chose que vous puissiez faire en plaçant vos navires est de faire en sorte qu'aucun d'entre eux ne se touche (certaines variantes de la bataille navale l'interdisent dans les règles, mais même si c'est autorisé, vous ne devriez pas le faire). Le problème avec les navires qui se touchent est que lorsque l'adversaire frappe un de vos navires, il vérifiera autour de ce coup pour trouver le reste du navire, et peut donc trouver votre navire contigu par accident.

D'autres conseils pour le placement des navires ne sont utiles que si l'adversaire effectue une recherche sous-optimale, mais ils sont tout de même là :

1. Placez vos navires loin les uns des autres ; en particulier, assurez-vous que vos trois plus petits navires sont éloignés les uns des autres. La version la plus simple de la recherche systématique consiste à commencer dans une zone du plateau et à balayer à partir de là sans jamais se remettre à zéro (un joueur retournerait de l'étape 3 à l'étape 2 plutôt qu'à l'étape 1). En plaçant vos navires loin les uns des autres, vous pouvez presque garantir que votre adversaire devra fouiller la majeure partie du plateau. Il est particulièrement important d'avoir les petits navires éloignés les uns des autres pour exploiter ce comportement, car couler les petits navires est le plus grand avantage pour un chercheur (une fois que vous avez coulé tous les navires d'une certaine taille, vous pouvez augmenter le N de votre grille de recherche).

2. Évitez le coin autour de la 1A. Les humains sont mauvais pour choisir au hasard, donc le coin 1A est l'endroit le plus probable où les gens vont commencer à chercher.

3. Mettez les navires dans un mélange de le long des bords de la planche et au milieu. Une fois de plus, on exploite le fait que les humains sont mauvais pour choisir au hasard, et qu'ils exploreront probablement dans une direction particulière, soit vers le bord, soit vers le milieu, mais pas les deux.

4. Placez vos vaisseaux de manière à minimiser le nombre de diagonales qu'ils partagent. De cette façon, vous maximisez vos chances que l'adversaire manque un de vos navires s'il essaie de faire un grand balayage (comme N = 4) pour commencer, ce qui l'oblige à parcourir à nouveau tout le plateau. Voir ci-dessous pour un exemple, où le même placement de trois petits navires garantit qu'au moins un navire sera manqué par un balayage N = 4 (@ = navire non touché, # = navire coulé, X = manqué).

     1 2 3 4 5 6
    1 # # . . X . 
    2 . X . . @ X
    3 . . X . @ .
    4 . @ @ X . . 
    5 X . . . X .
    6 . X . . . X
   
      1 2 3 4 5 6
    1 # # . . . X 
    2 . . X . @ .
    3 . . . X @ .
    4 X @ @ . X . 
    5 . X . . . X
    6 . . X . . .
   
      1 2 3 4 5 6
    1 @ @ X . . . 
    2 . . . X # .
    3 X . . . # .
    4 . # # . . X 
    5 . . X . . .
    6 . . . X . .

Answer 2

Je dirais que la stratégie optimale pour le tir est de viser à détruire les plus gros navires en premier afin de couvrir la plus grande partie du plateau aussi vite que possible. Je suggère de commencer avec un écart de 4 et de le réduire au fur et à mesure que vous coulez les plus gros navires.

Vous trouverez ci-dessous un exemple où l'on commence par un écart de 3 entre les prises de vue et où on le complète ensuite par un écart de 1 entre les prises de vue.

X . . . X . .
. X . . . X .
. . X . . . X
. . . X . . .
X . . . X . .
. X . . . X .

X . O . X . O
. X . O . X .
O . X . O . X
. O . X . O .
X . O . X . O
. X . O . X .

Je le suggère pour plusieurs raisons.

• Vous avez toujours la possibilité de frapper et de couler les petits navires.
• Si vous commencez du côté opposé de l'échiquier par rapport à leurs navires, vous perdrez beaucoup de temps.
• Vous couvrirez la planche beaucoup plus rapidement.
• En commençant par des blocs de 4, vous pouvez couvrir rapidement l'ensemble du tableau, puis revenir et terminer le tableau en comblant les trous pour éliminer 5 positions en un seul coup.

Remarque : je ne vous suggère pas où commencer sur la planche, mais seulement le modèle à suivre.

Answer 3

Un algorithme fort pour un ensemble de règles légèrement différent :

Navires Can être placés les uns à côté des autres.

---

DataGenetics a écrit un article amusant sur la résolution de la bataille navale il y a quelques années. Si leur algorithme n'est pas optimal, il en est au moins extrêmement proche. L'auteur a combiné le concept de parité avec les fonctions de densité de probabilité. Autrement dit, il suffit de tirer sur chaque i-ème carré de la grille, où i dépend de la taille du plus petit vaisseau. Et au fur et à mesure que le nombre de tirs augmente, certains endroits sont plus susceptibles de contenir des vaisseaux que d'autres, en fonction du nombre de configurations de rotation et de translation possibles pour un vaisseau donné, compte tenu de l'espace restant.

Je pense qu'il serait intéressant de tenter d'optimiser la disposition de la flotte en fonction de leur stratégie. Peut-être est-il possible de disposer les navires de telle sorte que la fonction de densité de probabilité donne le moins d'informations possible pour le plus grand nombre de tours ?

https://www.datagenetics.com/blog/december32011/

L'article compare 4 algorithmes, en faisant tourner chaque algorithme sur 100 millions de parties.

1. Random n'est qu'une (mauvaise) ligne de base, on voit qu'il y a une probabilité de 17/100 de tirer sur tous les 100 endroits.
2. Pas de parité aussi appelé Hunt/Target joue au hasard jusqu'à ce qu'il touche, puis tire à côté de ce qui touche.
3. Parité faire la même chose que le n°2 mais utiliser aussi la parité (comme dans la réponse de @Zags (N = 2 pour commencer))
4. Nouvel algorithme est le gagnant et il tire de la manière suivante :

calcule l'emplacement le plus probable pour le prochain tir en se basant sur une superposition de tous les emplacements possibles où les navires ennemis pourraient se trouver.

Le graphique suivant montre la distribution du nombre de tours, nous pouvons voir que dans la plupart des jeux, le nombre de tours est plus élevé que le nombre de tours. Nouvel algorithme a coulé les navires de l'adversaire en 30 à 60 tours.

Answer 4

Comment gagner aux cuirassés

Il y a deux phases répétitives dans le jeu : Chasser et Tuer.

Dans la phase de chasse, vous essayez de trouver des navires. Comme tous les navires occupent au moins deux cases contiguës, vous n'avez besoin de tirer que sur une case sur deux. Si c'était un damier, vous ne tireriez que sur les cases rouges et pas sur les noires, par exemple. Une fois que vous avez obtenu un succès, passez à la phase d'élimination.

La phase d'abattage consiste évidemment à essayer de déterminer dans quelle direction le vaisseau pointe et où se trouvent les extrémités. Dans ce cas, vous tirez immédiatement à côté de l'endroit touché. Le reste, vous pouvez le découvrir.

Vous pouvez gagner du temps en sachant quels navires sont encore en service. Si vous avez trouvé le destroyer, vous n'avez pas besoin d'échantillonner une case sur deux, mais plutôt sur trois, car le plus petit navire s'étendra sur au moins trois cases adjacentes.

Je commencerais à tirer des coups de feu au hasard, mais ne chassez pas dans les cases adjacentes. Vous pouvez ensuite combler les trous plus tard après avoir coulé quelques navires et savoir lesquels sont encore là.

TL,DR ; Une case sur deux pour trouver des bateaux, puis les couler.