Existe-t-il une stratégie gagnante pour Don't Break the Ice ?

Question

Ne brisez pas la glace est un jeu pour enfants, où les joueurs utilisent à tour de rôle des maillets pour faire tomber des morceaux de glace hors du terrain de jeu. Le terrain de jeu est composé d'une grille (6 x 6) de blocs carrés simples, à l'exception du bloc 2x2 sur lequel se trouve l'ours patineur.

Le but du jeu est de ne pas briser la glace et de faire tomber l'ours.

Existe-t-il une stratégie gagnante ? Si oui, pour quel joueur ? Hypothèses :

• Chaque joueur n'élimine que un bloc de leur choix.
• Les blocs sont "collants" et s'accrochent les uns aux autres le long de n'importe quel bord, et ainsi de suite :
• Le jeu se termine lorsque le carré central 2x2 a été déconnecté de l'extérieur du carré 6x6, c'est-à-dire lorsqu'il n'y a plus de chemin orthogonal (connecté le long des bords) d'une cellule à l'extérieur du carré 6x6 à une cellule à l'intérieur du 2x2 central.

Answer 1

Si je comprends bien le jeu, il devrait y avoir une stratégie gagnante pour le joueur qui part en dernier. Si on commence par ne pas tenir compte des coins, alors l'ours tombera lorsque l'avant-dernier bloc sera enlevé :

--X---
--X---
--BB--
--BB--
------
------

(ou similaire) Comme le nombre de blocs est pair, ce bloc sera retiré par le joueur qui passe en premier. Maintenant, il y a deux complications. Premièrement, le dernier bloc retiré peut inclure le coin :

-X----
-X----
-XBB--
--BB--
------
------

o

-X----
-XX---
--BB--
--BB--
------
------

Comme le nombre de blocs restants est maintenant impair, le joueur qui part en dernier perd. Deuxièmement, un bloc peut tomber parce qu'il est déconnecté. Comme le note Steven, seuls quatre blocs peuvent tomber de cette façon. Si un nombre impair de blocs tombe, alors le joueur qui est le dernier sera celui qui fera le dernier mouvement dans la première manche.

Cependant, ces deux situations peuvent être facilement évitées en attaquant d'abord les blocs d'angle. Puisqu'il faut deux coups pour retirer un bloc d'angle, le deuxième joueur peut toujours retirer le bloc d'angle avant que le premier ne puisse le faire tomber, et bien sûr avant que tous les blocs latéraux ne soient retirés. Cela garantit que la position finale sera du premier type, et donc que le joueur qui passe en premier perd.

Answer 2

Quelques notes :

• Il n'y a guère de raison de se donner la peine de retirer des blocs dans les conditions spécifiées pour la version simplifiée ; les seules cellules qui peuvent être retirées en devenant isolées sont les quatre cellules diagonalement (mais pas horizontalement) adjacentes au bloc central. Toutes les cellules de l'anneau extérieur 6x6 sont, bien sûr, toujours connectées, et toutes les autres, à l'exception de ces quatre cellules, sont connectées au bloc intérieur 2x2.
• Les quatre cellules situées dans les coins extérieurs du plateau peuvent être ignorées à des fins de connectivité ; elles ne peuvent être traversées par aucun chemin qui ne touche pas également un autre bord du plateau. Ainsi, elles servent effectivement de "passe", un mouvement qui peut être effectué sans affecter le plateau de manière significative. De plus, comme le jeu est symétrique, si un joueur a l'avantage stratégique de passer, alors l'autre joueur en a aussi l'avantage ; ainsi, une passe doit toujours être suivie d'une autre passe. Puisque les passes se font par paires (4 au total), elles n'ont pas non plus d'effet significatif sur le jeu et peuvent être ignorées dans le calcul de l'issue du jeu ; autant laisser ces cases vides dès le début.
• Ces simplifications (ainsi que de nombreuses tables de transposition) rendent le jeu éminemment analysable. Puisque les 4 cellules centrales ne peuvent pas être éliminées et que les 4 cellules des coins extérieurs n'ont pas d'importance, il y a effectivement 28 cellules dont l'état peut changer de manière significative ; cela signifie que le jeu a 2 28 postes au total. Cela représente 256 millions de positions et, comme la valeur d'une position peut être stockée dans un seul bit, la "table de vérité" complète (cette position est gagnante ou perdante) peut être stockée dans seulement 32 mégaoctets. Si vous voulez être fantaisiste, vous pouvez même ajouter un bit supplémentaire indiquant si la position est "déjà perdue" (c'est-à-dire si elle est connectée ou déconnectée), ce qui double votre espace de stockage mais facilite un peu les choses.
• De plus, la construction de cette table de vérité est simple : la position avec 0 bit est impossible, sa valeur n'a donc aucune importance. Toutes les positions avec un bit sont perdues pour celui qui vient de s'y déplacer. À partir de celles-ci, vous pouvez calculer la valeur de toutes les positions avec deux bits activés (ou même plus simplement, il suffit de remplir celles qui ne sont pas perdues : les huit positions avec une cellule "intérieure" et une cellule adjacente "extérieure" activées). À partir de ces positions, vous pouvez calculer la valeur de toutes les positions à trois bits, etc. Cela ne prendrait pas plus d'une journée à écrire et probablement moins de 5 ou 10 minutes à exécuter sur une machine moderne de puissance raisonnable, en supposant que les algorithmes soient bien faits.

S'il y a suffisamment d'intérêt, je peux essayer d'assembler quelque chose pour trouver la valeur finale, mais cela me prendra un jour ou deux ; il est aussi éminemment possible que le problème puisse être résolu avec une analyse rapide du cas, puisque 90% de la connectivité ressemble à un 'hareng rouge' et (à part les cellules de 'coin intérieur') le problème est presque entièrement une question d'éliminer soit une cellule intérieure ou à la fois les cellules extérieures adjacentes et les cellules de coin intérieur adjacentes. Le problème devrait pouvoir être analysé comme la somme de quatre "mini-jeux", un pour chacun des quatre coins du plateau (mais attention, dans le langage standard, le jeu est le suivant misère et non normal, donc les nim-sums normaux ne peuvent pas lui être appliqués).

Answer 3

En théorie, une stratégie optimale, au sens d'une équilibre de Nash doit certainement exister. Cependant, d'après la description du jeu sur Wikipedia Je pense qu'il est difficile de trouver une telle stratégie dans la pratique.

Tout d'abord, il apparaît que le jeu n'est pas déterministe, de sorte que la stratégie optimale ne peut être optimale que dans un sens statistique - elle ne peut garantir la victoire d'aucun joueur. Deuxièmement, les résultats des différents mouvements semblent dépendre des propriétés physiques des blocs, ce qui signifie que pour calculer la stratégie optimale, il faudrait d'abord développer un modèle précis de la physique du jeu, puis adapter le modèle aux mesures réelles.

(Ce n'est pas totalement impossible - par exemple, cela a été fait pour Passez les cochons mais il s'agit d'un exemple plus simple, puisque les cochons dans Pass the Pigs n'interagissent pas vraiment entre eux. À cet égard, Don't Break the Ice semble plus proche de, disons, Jenga .)

Enfin, je ne suis pas sûr de la constance des propriétés physiques des pièces du jeu, ni de la probabilité qu'elles changent avec le temps en raison de l'âge ou de l'usure. Si le comportement des pièces varie trop, une stratégie calculée pour un jeu particulier peut ne pas être optimale pour un autre jeu.

Cela dit, il est peut-être encore possible de trouver une approximation déterministe (ou du moins non déterministe de manière cohérente) du jeu, puis d'analyser cette approximation. Je ne connais pas suffisamment le jeu en question pour suggérer ce à quoi une telle approximation pourrait ressembler, à l'exception de quelques caractéristiques très grossières (par exemple, le fait de déconnecter complètement le centre des bords du terrain de jeu devrait certainement être un coup perdant).

Answer 4

Compte tenu de la physique, il semblerait que les blocs ne soient pas collants - mais vous pouvez toujours prévoir quand ils tomberont. Les blocs resteront en place s'ils se trouvent entre (avec une ligne de blocs ininterrompue) deux blocs dont il est déjà confirmé qu'ils restent en place (en comptant le bord).

Par exemple, prenez ce tableau.

----
--x-
---x
----

Les deux autres blocs "d'angle" par les X tomberaient également, puisqu'ils ne sont pas soutenus.

----
--xx
--xx
----

Le reste des blocs resterait, cependant. Le reste de la planche resterait en place en raison de la compression des bords de la planche.

----
--xx
--xx
x---

Ce bloc a été brisé, maintenant. Cependant, rien d'autre ne tombera. Je vais marquer les blocs stables avec un "s". Ces blocs sont stables car ils sont maintenus ensemble par des bords :

ssss
-sxx
-sxx
xs--

Le reste des blocs va également rester parce qu'ils sont maintenus entre les bords et d'autres blocs stables.

Cependant, il existe toujours une stratégie gagnante assez simple. Il faut toujours casser le bloc de glace à 180 degrés de ce que le premier joueur a joué. Le plateau restera toujours symétrique, et vous finirez par arriver à un scénario comme celui-ci.

xx-xxx
xx-xxx
xxBBxx
xxBBxx
xxx-xx
xxx-xx

Votre adversaire sera obligé de briser l'une de ces chaînes, faisant ainsi tomber le centre.

Vous ne pouvez jamais perdre en faisant cela à cause de la symétrie. La tuile centrale ne tombera que si elle n'est pas soutenue ni verticalement ni horizontalement. Si vous brisez l'une des tuiles qui maintiennent le centre en place (ici les tuiles S)

--SS--
--SS--
SSBBSS
SSBBSS
--SS--
--SS--

vous cassiez toujours un côté sur le même axe que votre adversaire. Vous ne briserez pas la stabilité dans n'importe quel axe parce que votre adversaire le fera en premier.

xxxSxx
xxxSxx
--BB--
--BB--
xxSxxx
xxSxxx

Si votre adversaire casse une des tuiles S, il n'y aura pas de force utile verticalement.

xxxxxx
xxxxxx
--BB--
--BB--
xx-xxx
xx-xxx

Les deux tuiles du bas n'apportent aucune stabilité au centre car cette stabilité ne provient que de la compression, et l'autre côté de cette compression est cassé. Cela signifie que lorsque vous retirez les deux tuiles du bas, vous ne rendez pas le centre moins stable.

Connaître cette stratégie ne signifie toutefois pas que vous gagnerez toujours. Vous devez toujours être capable de faire tomber uniquement le ou les blocs que vous voulez (ce qui relève de l'habileté, pas de la stratégie). Je n'ai pas non plus trouvé ce qu'il faut faire si vous êtes le premier et que votre adversaire fait une erreur.