300000
Nombre de victoires : 758
La Pipopipette
Si vous ne vous intéressez qu'aux prochains coups à jouer sans en savoir la raison, dirigez-vous vers l'« Arbre de Décision » en bas de page. La section « Index » ci-bas dresse la liste de tous les termes introduits dans ce texte et peut donc faire office d'une brève introduction.
Les Bases
Lexique: On introduit de la nouvelle terminologie pour mieux pouvoir discuter le jeu.
Une case est un petit carré dont les sommets sont 4 points voisins. Une case peut avoir des traits tracés sur 0, 1, 2, 3, 4 de ses côtés et est alors appelé une case-0, case-1, case-2, case-3, ou case-4.
Une ligne est le segment de ligne liant deux points voisins.
Le fait de tracer une ligne est aussi appelé effectuer ou jouer un coup.
Si une ligne non-tracée sépare une case-2 d'une case-3, alors le fait de tracer cette ligne a 3 conséquences: il complète la case-3 et gagne donc un point, il change la case-2 en case-3, et il impose au joueur de rejouer encore un coup ce qui peut donc servir à compléter la nouvelle case-3. Ce genre de « réaction en chaîne » arrive très souvent au cours du jeu.
Toutes les cases-2 connectées forment une chaîne. Une chaîne peut avoir deux bouts et est alors appelée une chaîne linéaire, sans égard à ce qu'elle soit droite ou pas, par exemple
+ + +---+---+ + +---+
| | , ou | |
+ + +---+---+ +---+ +
|
+---+---+montrent des chaînes ayant 1, 2, et 4 cases.
Une chaîne peut aussi ne pas avoir de bouts, ce qu'on appelle alors une chaîne bouclée ou bien tout simplement une boucle, peu importe qu'elle ressemble à un cercle ou pas, telle que celle-ci :
+---+---+---+
| |
+ +---+ +
| | |
+---+ + +
| |
+---+---+
Le fait de jouer dans une chaîne ou sur un de ses bouts se fait nommer ouvrir une chaîne dans la litérature mathématique à propos de la Pipopipette.
Que se passe-t-il lorsqu'on ouvre une chaîne?
Si un joueur trace une des lignes non-tracées dans une chaîne, par exemple le coup A1 dans
+---+---+---+
| |
+ +A1-+ +
| |
+---+---+alors au moins une case-2 devient une case-3 (ici les cases au-dessus et en dessous du coup A1) et l'adversaire peut alors fermer cette/ces case(s) pour obtenir une case-4, obtenir un ou deux points et en même temps convertir la case-2 avoisinante en case-3 (ici la case sur la gauche de B1 et sur la droite du B2 dans
+---+---+---+
| B1 |
+ +A1-+ + .
| B2 |
+---+---+À chaque fois qu'il ferme une case, le joueur est obligé de rejouer, ce qui peut permettre de fermer la prochaine case et toutes les autres cases de la chaîne. Après avoir complété la dernière case, le joueur doit jouer encore un coup ailleurs, à moins qu'il ne reste aucune case incomplète.
Jeu initial
Règle n°1: Le jeu le plus facile consiste à éviter de créer une case-3 que peut fermer l'adversaire pour le prendre. Ceci est une règle simple est utile même si elle n'est pas sans faille, ce qu'on verra plus tard. Cependant, après avoir tracé la moitié des lignes, une case-3 devient inévitable. Que faire alors? Des chaînes à 1, 2, ou ≥ 3 cases sont traitées de manière différente alors on les examinera une par une.
Les chaînes à 1 case
Doit-on toujours fermer une case-3, c.-à-d. une chaîne à 1 case?
+---+
| ?
+---+
Oui, on doit toujours fermer une case-3. Entre prendre la case pour ensuite jouer un coup A et ne pas prendre la case pour ensuite jouer ce coup A, la seule différence est que soit vous obtenez la case, soit c'est votre adversaire qui l'obtient. Alors il vaut mieux prendre la case.
Les chaînes à 2 cases : à quoi ça ressemble et quels coups faut-il jouer?
Les chaînes à 2 cases peuvent avoir les apparences suivantes :
+---+---+ +---+---+ +---+---+
ou | ou | |
+---+---+ +---+ + + + +ou bien les mêmes mais tournées ou retournées. Si on trace la ligne centrale dedans on obtient alors
+---+---+ +---+---+ +---+---+
| ou | | ou | | |
+---+---+ +---+ + + + +ce qui s'appelle dans la litérature un « Hard-Hearted Handout ».
Devrait-on toujours prendre les deux cases dans une telle position ?
Oui, on doit toujours prendre ces cases pour les mêmes raisons qu'on doit toujours prendre les cases-3. Réfléchissez-y bien pour vous en rassurez.
Tracer une ligne sur le bord d'une chaîne à 2 cases donne
+---+---+ +---+---+ | ou | | +---+---+ +---+ +
et s'appelle alors un «Half-Hearted Handout.».
Un coup joué sur le bord d'un « Half-Hearted Handout » donne
+---+---+ | | . +---+---+
La litérature mathématique appelle un tel coup du « Double Dealing » (DD).
Tracer la ligne du milieu qui ferme alors les deux boîtes s'appelle alors un Coup « Double-Crossed ». Une boucle est toujours complétée par un tel coup mais dans une chaîne linéaire ceci ne peut arriver que lorsque l'adversaire joue un Coup DD pour prendre le contrôle tel qu'expliqué ci-bas. Dans une telle situation, le joueur qui joue un Coup « Double-Crossed » est trompé, c.-à-d. « Double-Crossed » (doublé), d'où le nom pour ce coup.
Est-ce que celui qui joue après un coup DD devrait toujours prendre les deux cases ?
Un coup DD est un sacrifice de deux cases parce que le joueur peut, de manière alternative, tracer d'abord la ligne du milieu du « Hard-Hearted Handout » puis sur le bord pour ainsi obtenir les 2 cases. Mais pourquoi voudrait-on sacrifier 2 cases ? Continuez de lire pour le savoir !
Le fait de jouer un coup comme le « Half-Hearted Handout » avant DD, ce qui donne à l'adversaire l'option de faire un sacrifice, est appelé dans la litérature un « loony move » c.-à-d. un « Coup fou ». Il existe d'autres exemples de coups fous, par exemple des coups ouvrant des chaînes d'au moins 3 cases car l'adversaire aura alors l'option de jouer un coup DD aussi, ce qu'on verra ci-après.
Retournons aux coups de type « Half-Hearted Handout », devrait-on toujours prendre les deux cases dans une telle position ? Sinon, quand doit-on jouer DD sur le bord ? Tentez-les vous-même pour en voir la différence que ça donne!
Examinons toutes les différences. Si on prend une des cases alors on doit prendre la deuxième case, tel que discuté ci-haut. Si on prend les deux cases on obtient alors 2 points, mais par la suite il s'impose de jouer un coup ailleurs. Ceci peut coûter cher car on peut se retrouver obligé d'ouvrir une chaîne ayant plusieurs cases, ce qui permettrait à l'adversaire de prendre plus de cases. Si on joue sur le bord, on ne ferme pas de cases alors on n'est pas obligé de rejouer. Par contre, ceci cède à l'adversaire les deux cases tel que discuté ci-haut. Alors, les deux jeux sont possibles. On reviendra plus tard sur cette question pour pouvoir déterminer quel coup jouer dans une situation donnée.
Si on se retrouve obligé d'ouvrir une chaîne à 2 cases parce que tous les autres coups seraient alors plus coûteux, devrait-on prioritiser un « Half-Hearted Handout » ou un « Half-Hearted Handout » ?
Si on joue au milieu de la chaîne (un « Hard-Hearted Handout ») alors l'adversaire est obligé de fermer les deux cases et de rejouer ailleurs, ce qui peut être otentiellement plus coûteux pour lui.
+---+---+ +---+---+ +---+---+
→ | → | | | plus un coup ailleurs
+---+---+ +---+---+ +---+---+
Si on joue sur le bord d'une chaîne (un « Half-Hearted Handout ») alors on donne à l'adversaire l'option soit de prendre les deux cases, soit de jouer sur le bord (un Coup « Double Dealing » (DD)):
+---+---+ +---+---+ +---+---+
→ | → | |
+---+---+ +---+---+ +---+---+
Cette option peut s'avérer très utile comme on verra plus tard. Donner à son adversaire plusieurs options ne peut pas être le meilleur coup, alors lorsqu'on veut de manière optimale il faut éviter de jouer un « Half-Hearted Handout ». Si on joue de manière non-optimale, pour s'amuser, alors on peut essayer des coups « Half-Hearted Handout » pour évaluer le niveau de son adversaire ou bien pour embrouiller son adversaire si on essaie de le rattraper.
Les chaînes ouvertes à 3 cases ou plus : qu'en faire ?
Si une chaîne est ouverte alors elle a au moins une case-3. On pourra fermer cette cases et les autres aussi, mais devrait-on les fermer?
Y a-t-il des cases qu'on devrait absolument prendre dans une chaîne linéaire ouverte ?
D'une part, on veut prendre le plus de cases possible. D'autre part, il faut penser au coup qui suit la fermeture de cette chaîne et si ce coup sera coûteux, c'est-à-dire s'il offrira une chaîne encore plus grande à l'adversaire. Ce qu'il faut absolument faire sans question est de prendre toutes sauf deux cases (comme on a déjà expliqué)− celles-ci sont gratuites car elles ne peuvent avoir aucune effet négatif. Après, il faut choisir entre prendre les 2 cases restantes et jouer un Coup DD (Double Dealing). On en reparlera plus tard.
Des chaînes ayant ≥ 3 cases s'appellent des châines longues.. Celles-ci comprennent des chaînes linéaires aussi bien que les chaînes bouclées.
Pourquoi y a-t-il un nom spécial pour ces chaînes en particulier ?
S'il ne reste que des chaînes de 3 cases et plus, alors le fait d'en ouvrir une, peu importe comment, indiquera que sur au moins un côté du coup joué il reste au moins 2 cases voisines. Alors, l'autre joueur peut jouer un Coup DD (Double Dealing) ce qui peut déterminer la fin du jeu.
Combien faut-il de cases pour former une boucle ?
La boucle la plus petite possible n'a que 4 cases :
+---+---+ | | + + + | | +---+---+
Si on ouvre une boucle, peut-on prendre toutes les cases sans devoir s'en soucier ?
Pour le savoir, essayons-le. La boucle la plus petite possible est
+---+---+ | | +---+ + | | +---+---+
Bien sûr, on peut prendre toutes les 4 cases pour ensuite jouer ailleurs... mais que faire si on doit éviter de jouer ailleurs à tout prix ? Si on prend deux cases, on obtient
+---+---+ | | | +---+---+ | | +---+---+
mais il faudra alors jouer encore un coup. Ce qui veut dire qu'on ne peut pas s'arrêter là car toutes les lignes des bords sont déjà tracées et donc on doit continuer pour obtenir
+---+---+ | | | +---+---+ | | | +---+---+
et puis on est obligé de jouer un coup ailleurs, ce qui peut être bénéfique pour l'adversaire.
Comment jouer dans une boucle sans s'obliger de jouer en dehors de la boucle ?
On doit jouer un coup qui ne complète aucune case pour ne pas devoir jouer un coup ailleurs par la suite. Alors le seul coup possible est de jouer au milieu de la boucle ouverte pour obtenir
+---+---+ | | +---+---+ . | | +---+---+
Ce coup ne ferme aucune case alors l'adversaire doit jouer par la suite. On appellera donc ce type de coup un Coup « Double Double Dealing » ou bien un Coup DDD. Le prix s'élève à 4 cases sacrifiées au lieu de 2 cases. Pour l'adversaire le mieux est de prendre les 4 cases et ensuite de jouer ailleurs.
Que faire si une boucle ouverte a plus de 4 cases?
On peut prendre autant de cases qu'on voudrait à moins qu'on puisse toujours jouer un coup par la suite qui ne ferme aucune case. Ceci veut dire qu'on peut prendre toutes sauf 4 cases, par exemple en ouvrant
+---+---+---+---+ +---+---+---+---+ | | | | | + +---+---+ + donnant, par exemple + +---+---+ + | | | | +---+---+---+---+ +---+---+---+---+
et prenant 8 − 4 = 4 cases donne, par exemple,
+---+---+---+---+ | | | | | + +---+---+---+ . | | | +---+---+---+---+
Après il faut décider si on prend les 4 cases restantes ou bien si on les sacrifie à l'adversaire en jouant
+---+---+---+---+ | | | | | + +---+---+---+ . | | | | +---+---+---+---+
On en reparlera plus tard.
Dans une position où il y a une chaîne ouverte ou dans celle (très improbable) où il y a plusieurs chaînes ouvertes, combien de cases peut-on prendre sans réfléchir à jouer un coup DD (ou pas) ?S'il y a au moins une châine linéaire ouverte ayant au moins deux cases voisines, alors on peut compléter toutes les autres cases de cette chpaine ainsi que celles de toutes les autres chaînes linéaires et bouclées ouvertes. Sinon, s'il n'y a qu'une ou plusieurs chaînes bouclées seulement, alors on peut fermer toutes les cases sauf 4 cases d'une chaîne bouclée ainsi que toutes les autres cases des autres chaînes bouclées. Une fois toutes ces cases prises, on peut réfléchir à la question de jouer un Coup DD/DDD ou pas.
On a appris que le jeu se commence par des coups plus ou moins aléatoires où les joueurs essayent d'éviter de créer des cases-3 le plus longtemps possible. Autrement dit, ils évitent d'ouvrir des chaînes. Arrivé à un certain moment du jeu, ceci devient inévitable et donc ce moment marque le début de la fin de partie.. On commence par là car c'est la partie la plus facile de tous les jeux.
La Fin de Partie
Comme avec tous les autres jeux, plus on s'approche de la fin, plus il devient facile de prédire qui va gagner (en jouant de manière optimale) et de combien. Alors on commence cette analyse par la fin de la partie. À la fin de partie, tous les coups ont pour effet d'ouvrir des chaînes, de fermer des cases, ou sont des coups DD/DDD. Quand un joueur doit ouvrir une chaîne alors la première idée qui peut lui venir comme stratégie serait peut-être d'ouvrir la plus petite des chaînes disponibles pour céder à l'adversaire le plus petit nombre de cases. On va essayer cette stratégie avec quelques exemples.
Exemple 1
Supposons que toutes les cases sont fermées sauf deux ayant 3 et 4 cases respectivement :
+ +---+---+ | | | | + +---+---+ | +---+---+---+ +---+---+---+
Le joueur A qui joue au prochain tour ouvrira la petite chaîne (par le coup A1) pour que le joueur B prenne cette chaîne et obtient 3 points et que A prenne la plus grande chaîne par la suite avec des points au total après ces chaînes de A:B=(0+4):(3+0)=4:3.
+A9-+---+---+ | | | | +A8-+---+---+ | B5 A6 A7 +---+---+---+ B2 A1 B3 B4 +---+---+---+
Pour info, le coup A1 est un exemple de ce qu'on a défini plus tôt comme un coup fou, un coup qui donne à son adversaire l'option de faire un sacrifice.
Mais le joueur B est malin et ne prend qu'une seule case par le coup B2 (dans le prochain diagramme), puis un coup Double Dealing par le coup B3. Le joueur A doit donc fermer les 2 cases par le coup A4, est obligé d'ouvrir la grande chaîne avec un coup comme A5, et le joueur B obtient alors les 4 cases restantes pour un score final de A:B = (2+0):(1+4)=2:5.
+B9-+---+---+ | | | | +B8-+---+---+ | A5 B6 B7 +---+---+---+ B2 A1 A4 B3 +---+---+---+On voit alors que dans cette situation il est bénéfique à B de sacrifier deux cases.
Exemple 2
Supposons que toutes les cases sont fermées sauf une chaîne ayant 3 cases et une boucle ayant 4 cases.
+---+---+---+ | | | + + +---+ | | | +---+---+---+ +---+---+---+C'est le tour au joueur A.
Cas n°1 : A ouvre la chaîne à 3 cases.
Si après le coup A1 le joueur B prend la chaîne entière, alors le joueur A prend la boucle et le score provenant de ces deux chaînes sera de A:B = (0+4):(3+0) = 4:3.
+---+---+---+ | A7 | | +A6-+A8-+---+ | B5 | | +---+---+---+ B2 A1 B3 B4 +---+---+---+
Si après le coup A1 le joueur B effectue un coup BB alors après
+---+---+---+ | B7 | | +B6-+B8-+---+ | A5 | | +---+---+---+ B2 A1 A4 B3 +---+---+---+le score provenant de ces deux chaînes sera donc de A:B = (2+0):(1+4) = 2:5 alors ici aussi il est bénéfique au joueur B de faire un coup DD et d'atteindre ainsi A:B = 2:5.
Cas n°2 : le joueur A ouvre la boucle à 4 cases.
Si après le coup A1 le joueur prend la boucle entière, alors le joueur A prend la petite chaîne et le score provenant de ces deux chaînes sera de A:B = (0+3):(4+0) = 3:4.
+---+---+---+ | B3 | | +B2-+B4-+---+ | A1 | | +---+---+---+ B5 A6 A7 A8 +---+---+---+
Si après le coup A1 le joueur B effectue un coup DDD avec B2 on obtient
+---+---+---+ | B2 | | +A3-+A4-+---+ | A1 | | +---+---+---+ B6 A5 B7 B8 +---+---+---+et un score provenant de ces deux chaînes de A:B = (4+0):(0+3) = 4:3. Dans ce cas il vaut mieux que B évite de faire un coup DDD pour obtenir A:B = 3:4.
Quelles leçons tirer de ces deux cas?
Dans le cas n°2 on a vu que le coût d'effectuer un coup DDD dans une boucle est élevée (4 cases) ce qui veut dire qu'il peut être plus bénéfique de ne pas jouer DDD à préférence de prendre la boucle entière. Alors quelle chaîne le joueur A doit-il ouvrir dans cet exemple? Pour le joueur A il vaut mieux ouvrir la boucle qui permet d'atteindre un score de A:B = 3:4 au lieu d'ouvrir la chaîne à trois cases qui donne un score de A:B = 2:5. On a appris que s'il y a des boucles, il ne suffit pas de classer les chaînes par leur taille (nombre de cases) pour savoir laquelle ouvrir en premier. Mais s'il y a une boucle, on peut la classer par taille − 2 pour donner ici : 4−2 = 2 < 4.
Exemple 3
Dans cet exemple on veut apprendre plus sur l'ordre dans laquelle on devrait ouvrir les chaînes. Supposons que toutes les cases sont fermées sauf deux chaînes linéaires avec 3 et 4 cases et une boucle avec 4 cases comme montré ci-dessous :
+---+---+ +---+
| | |
+ + +---+ +
| | | |
+---+---+---+ +
|
+---+---+ +---+C'est au tour du joueur A. Il est évident que A n'ouvrira pas la plus grande chaîne linéaire à 4 cases s'il y a une chaîne linéaire à 3 cases.
Cas n° 1: A ouvre la chaîne à 3 cases.
Afin de décider le coup optimal pour B, déterminons laquelle des 2 chaînes restantes devraient être ouverte en premier :
+---+---+ +---+ | | | + + +---+ + | | | | +---+---+---+ + | | | | +---+---+---+---+
Soient C et D les joueurs où le prochain tour est à C.
Cas n° 1.1: C ouvre la boucle
+---+---+ +---+
| | |
+ + +---+ +
| C1 | | |
+---+---+---+ +
| | | |
+---+---+---+---+ Si après C1 le joueur D joue DDD avec D2 alors après
+---+---+C5-+---+ | D2 | D6 | +C3-+C4-+---+D7-+ | C1 | | | +---+---+---+D8-+ | | | | D9 +---+---+---+---+
le score obtenu de ces deux chaînes sera alors C:D = (4+0):(0+4) = 4:4. Si D ne joue pas DDD mais prend la boucle alors
+---+---+D5-+---+ | D3 | C6 | +D2-+D4-+---+C7-+ | C1 | | | +---+---+---+C8-+ | | | | C9 +---+---+---+---+
le score obtenu de ces deux chaînes sera encore une fois C:D = (0+4):(4+0) = 4:4.
Cas n° 1.2: C ouvre la chaîne à 4 cases
+---+---+C1-+---+
| | |
+ + +---+ +
| | | |
+---+---+---+ +
| | | |
+---+---+---+---+ Si après le coup C1 le joueur D prend la chaîne entière alors après
+---+---+C1-+---+ | C8 | D2 | +C7-+C9-+---+D3-+ | D6 | | | +---+---+---+D4-+ | | | | D5 +---+---+---+---+
le score obtenu sera alors C:D = (0+4):(4+0) = 4:4. Si après C1 le joueur D effectue un coup DD avec D4 alors après
+---+---+C1-+---+ | D8 | D2 | +D7-+D9-+---+D3-+ | C6 | | | +---+---+---+C5-+ | | | | D4 +---+---+---+---+le score obtenu est alors C:D = (2+0):(2+4) = 2:6. Alors le meilleur score que le joueur D peut forcer par la suite du coup C1 est C:D = 2:6 .
Qu'apprend-on de ces deux cas ?
Pour le prochain joueur (C), il vaut mieux ouvrir la boucle pour donner un score C:D = 4:4 plutôt que la chaîne linéaire ce qui aboutit à C:D = 2:6. Si on ordonne les chaînes en ordrant croissant selon la valeur longueur − 2 pour déterminer laquelle ouvrir en premier alors (4−2) = 2 < 4 donne le bon résultat. On peut maintenant déterminer le jeu optimal pour B dans
+---+---+- +---+
| | |
+ + +---+ +
| | | |
+---+---+---+ +
A1 |
+---+---+ +---+
Le joueur B devrait-il prendre la chaîne ou jouer DD ?
Si B prend la chaîne alors après
+---+---+A9-+---+ | A7 | A10 | +A6-+A8-+---+A11+ | B5 | | | +---+---+---+A12+ B2 A1 B3 | A13 +---+---+B4-+---+
le score obtenu par ces 3 chaînes sera A:B = (0+4+0):(3+0+4) = 4:7. Si B joue plutôt DD via B3 alors après
+---+---+B9-+---+ | B7 | A10 | +B6-+B8-+---+A11+ | A5 | | | +---+---+---+A12+ B2 A1 A4 | A13 +---+---+B3-+---+
le score obtenu par ces 3 chaînes sera alors A:B = (2+0+4):(1+4+0) = 6:5. Alors le meilleur score que peut obtenir B apràs le coup A1 est A:B = 4:7 obtenu par B lorsqu'il ne joue pas DD. Dans les deux cas on a appliqué la découverte obtenue plus tôt comme quoi il vaut mieux ouvrir la boucle au prochain tour.
Cas n°2 : A ouvre la boucle à 4 cases :
+---+---+ +---+
| | |
+ + +---+ +
| A1 | | |
+---+---+---+ +
|
+---+---+ +---+
Cas n° 2.1 : B prend la boucle entière.
Il est évident qu'il doit jouer DD sur la petite chaîne pour obtenir
+---+---+B9-+---+ | B3 | A10 | +B2-+B4-+---+A11+ | A1 | | | +---+---+---+A12+ B5 A6 B8 | A13 +---+---+A7-+---+ce qui donne un score via ces 3 chaînes de A:B = (0+1+4):(4+2+0) = 5:6.
Cas n° 2.2 : B sacrifie la boucle.
Encore une fois il faut jouer DD sur la petite boucle pour obtenir
+---+---+A9-+---+ | B2 | B10 | +A3-+A4-+---+B11+ | A1 | | | +---+---+---+B12+ A5 B6 A8 | B13 +---+---+B7-+---+ce qui donne par des 3 chaînes un score de A:B = (4+2+0):(0+1+4) = 6:5.
Qu'apprend-on des cas n° 2.1 et 2.2 ?
Étant donné le coût élevé de jouer DDD dans une boucle, le meilleur à faire pour B dans cette situation sera de prendre la boucle entière et d'obtenir ainsi un score de A:B = 5:6.
Quelles conclusions peut-on tirer des cas n° 1 et 2?
On a deux chaînes linéaires à 3 et 4 cases et une boucle à 4 cases. Il est préférable que A ouvre la boucle et atteigne un score de A:B = 5:6. Si A ouvre la chaîne avec 3 cases alors il n'atteint que A:B = 4:7. Il est clair qu'il ne peut pas être favorable pour B d'ouvrir la chaîne à 4 cases avant la chaîne à 3 cases. Par conséquent, trier les chaînes simplement par longueur pour déterminer laquelle ouvrir ensuite n'est pas une manière valable de choisir entre elles. Par contre, les trier par longueur − 2 s'il s'agit d'une boucle semble fonctionner car (4−2) = 2 < 3 indique que la boucle doit être ouverte en premier.
L'ordre dans lequel ouvrir les chaînes
Avec l'expérience acquise à partir des exemples ci-dessus, on aborde maintenant le problème de la détermination de l'ordre dans lequel les chaînes seront ouvertes et complétées. Cet ordre de chaînes sera utilisé ci-dessous pour déterminer à quel moment l'un des joueurs jouera DD/DDD, qui gagnera la partie et de combien. La bonne nouvelle est qu'en fin de partie, cette séquence de chaînes ouvertes ne dépend pas du joueur auquel il est le tour ou de qui a joué DD/DDD avant. La raison en est qu'à tout moment du jeu, seules les lignes qui ont été tracées comptent, pas par qui ni dans quel ordre. Même le score actuel n'a aucun effet sur le jeu optimal futur. Diviser un problème difficile en plusieurs problèmes plus faciles est déjà un succès. Dans ce cas, la tâche difficile de déterminer qui effectue quel coup dans la phase finale a été divisée en deux problèmes : le problème de l'ordre dans lequel ouvrir les chaînes, et le problème de savoir qui joue DD/DDD et quand. Avant de commencer, on doit réfléchir sur la tendance générale de la fin du jeu.
Est-ce que la « valeur » des chaînes ouvertes augmente ou diminue vers la fin ?
Une chaîne ouverte est cédée à l'adversaire. La chaîne doit donc avoir le moins de « valeur » possible où la valeur est, d'un seul clin d'oeil, le nombre de cases. Par conséquent, au cours de la phase finale, la « valeur » des chaînes ouvertes ne peut qu'augmenter ou rester constante, mais pas diminuer. Dans notre exemple ci-dessus, nous avons vu qu'ouvrir la chaîne avec le moins de cases qui peuvent être prises par l'adversaire ne fonctionne pas. Mais on veut tout de même trier les chaînes par une certaine « valeur » parce que chaque joueur veut ouvrir la chaîne la moins favorable pour l'adversaire. Pour l'adversaire, la valeur d'une chaîne ne se détermine pas seulement du nombre de cases ; il importe également de savoir si la chaîne ouverte convient pour y effectuer un coup DD/DDD. Un bon candidat pour cet ajustement d'adéquation pour DD est de soustraire 2 du nombre de cases si la chaîne est une boucle. Donc, pour trier les chaînes par une « valeur » on fixe « valeur » = # de boîtes si la chaîne n'est PAS une boucle et « valeur » = # de boîtes − 2 si la chaîne EST une boucle.
On commence par des positions où chaque case a au moins 2 lignes tracées. Par cela, on peut formuler deux règles qui permettent d'ordonner toutes les chaînes.
Règle n°2 : Pour ordonner les chaînes, prendre comme la dernière chaîne soit la chaîne linéaire la plus longue, soit, s'il n'y a pas de chaîne linéaire, la plus grande boucle.
Justification de la Règle n°2
Un joueur en contrôle n'ouvre pas de chaînes et ne les trie donc pas. Ainsi, tout joueur triant des chaînes veut rendre aussi coûteux que possible pour l'adversaire la prise ou le maintien du contrôle (c'est-à-dire jouer des mouvements DD/DDD). Un coup DD coûte 2 cases et un coup DDD coûte 4 cases. Ce prix doit être payé pour toutes les chaînes sauf la dernière. Par conséquent, pour maximiser le coût total pour l'adversaire, dans le tri des chaînes, la dernière chaîne doit être linéaire si possible et non une boucle. ∎
Règle n°3 : Si dans la fin du jeu toutes les cases ont au moins deux lignes tracées, alors pour ordonner toutes les autres chaînes dressez-les selon (nombre de cases − 2 si c'est une boucle).
Justification de la Règle n°3
Pour que le prochain joueur prenne ou garde le contrôle, la valeur d'une chaîne est le nombre de ses cases − 2 si c'est une chaîne linéaire et − 4 si c'est une boucle. Pour trier les chaînes on obtient le même résultat si on ne soustrait que 2 en cas de boucle. Que se passe-t-il si l'adversaire n'a pas le contrôle et ne prendra pas le contrôle au prochain tour ? L'adversaire ne bénéficierait-il pas lorsque, sur la base de cet ordre, l'adversaire doit effectuer un coup ensuite dans une boucle ouverte avec deux cases de plus que d'obtenir une chaîne linéaire avec la même « valeur » mais moins de cases ? Non! Si l'adversaire prend toute la boucle puis ensuite quand ce sera au tour de ce joueur, il y aura une boucle de moins et il sera de 2 cases moins cher de reprendre le contrôle. ∎ Nous avons vu cet effet dans l'exemple 3 cas n° 2.1 où, après que le joueur A a ouvert la boucle avec A1, le joueur B prend toute la boucle mais en conséquence, il est devenu abordable pour A de prendre le contrôle avec A7 et d'obtenir le meilleur résultat possible.
Les règles ci-dessus sont claires lorsque toutes les cases appartiennent à une chaîne, c'est-à-dire si toutes les cases ont au moins 2 lignes tracées. Mais que faire lorsqu'il y a des cases-0 et cases-1 ?
À quelles chaînes appartiennent ces cases ?
Règle n°4 : Pour établir une séquence de chaînes triées par valeur, effectuez le cycle suivant de coups jusqu'à ce que l'ensemble du plateau soit terminé.
- Ouvrez une des chaînes dont la valeur (nombre de cases, ou s'il s'agit d'une boucle le nombre de cases −2) est minimale à une exception près : S'il reste au moins une boucle, connectée ou déconnectée, et s'il y a est une seule chaîne linéaire déconnectée, et s'il n'y a pas d'arbre connecté de chaînes linéaires uniquement, n'ouvrez pas la dernière chaîne linéaire déconnectée.
- Complétez la chaîne ouverte sans compter les cases. Tracer des lignes à la fin d'une chaîne linéaire peut changer une case-1 en une case-2 et ainsi fusionner deux chaînes linéaires ou couper une boucle.
Si dans la fin de partie, il y a encore des cases-0 et des cases-1, alors on peut considérer une telle case comme un point et considérer les chaînes comme des lignes qui se terminent à ces points ou terminant au bord du plateau et ensuite obtenir un point artificiel supplémentaire.
L'ensemble de points reliés par des lignes s'appelle un graphe en mathématiques.
L'exception de la règle 4 formulée en « langage des graphes » dirait : ne pas ouvrir une chaîne linéaire correspondant à une ligne déconnectée du graphe restant si le graphe restant a une partie déconnectée qui contient une boucle et n'a pas de partie déconnectée qui ne contient pas une boucle (et est donc appelé un « arbre«» dans le langage des graphes).
Exemple 4: Un graphe ressamblant en forme de lettre 'T'
La case-1 a un T inscrit :
+---+---+---+ + | T | | + + + + + | | | | + + +---+---+ | | | + +---+---+ +
Le graphe correspondant à ce plateau sera un T formé à partir de 4 points, où le − et le | dans le T se croisent et avec 3 points aux 3 bouts du T.
La plus petite des 3 chaînes attachées à la case-1 est sur sa gauche. En l'ouvrant de la complétant
+---+---+---+ + +---+---+---+ + | | | | | | | + + + + + +---+ + + + | | | | | | | | +---+ +---+---+ +---+ +---+---+ | | | | | | + +---+---+ + +---+---+---+ +
on voit que le plateu a alors 2 chaînes linéaires ayant 3 et 9 cases respectivement.
Exemple 5: Un graphe en forme de 'P'
La case-1 a un P inscrit :
+---+---+---+---+ | | + +---+---+ + | P | + +---+---+---+ | | +---+---+---+ +
Dessiner le côté au-dessus de la case 1 ou à droite de cette case créerait et ouvrirait une grande chaîne linéaire avec 12 cases
+---+---+---+---+ | | +---+---+---+ + | | + +---+---+---+ | | +---+---+---+ +
qu'on ne voudrait pas donner à l'adversaire. Tracer la ligne sous la case 1 divisera le plateau en une chaîne linéaire ouverte avec 4 cases et une boucle avec 8 cases.
+--+--+--+--+ | | + +--+--+ + | | +--+--+--+--+ | | +--+--+--+ +
Dans la Règle n° 4 ci-dessus, une exception a été formulée. L'exemple suivant illustre cette exception.
Exemple 6: Un graphe 'P' plus une chaîne linéaire déconnectée
Deux chaînes linéaires peuvent être ouvertes, l'une sur la droite et l'autre en bas.
+---+---+---+---+ + | P | | + + +---+ + + | | | | + +---+---+---+ + | | | +---+---+---+ + +
Cas n°1. Ouvrir la chaîne la plus petite d'abord
21 ont été effectuées jusqu'ici, alors si le joueur A a joué en premier, le tour est au joueur B.
Si après avoir ouvert la plus petite chaîne via B1, le joueur A reprend le contrôle tout de suite, on obtient
+---+---+---+---+B1-+ | B5 B12 | | +A6-+ +---+ +A2-+ | | | | +A7-+---+---+---+B4-+ | A8 A9 B11 | | +---+---+---+A10+A3-+
et un score de A:B = (1+4+6):(2+2+0) = 11:4 où (2+2+0) signifie que le joueur B obtient des 3 chaînes ouvertes dans cet ordre 2, 2 et 0 cases. Parce que B ne peut ouvrir la 2ème chaîne linéaire qu'avec B5, le joueur A peut garder le contrôle avec A10 avec un coût de seulement 2 et obtenir la boucle gratuitement.
Cas n° 2. Ouvrir la chaîne la plus longue d'abord
Une fois que B ouvre la chaîne la plus longue avec B1 en dessous et que cette chaîne est terminée, celui qui obtient la ou les dernières cases doit ouvrir une chaîne. Selon la règle n° 2, le joueur B ouvre ensuite la boucle avec B8 pour rendre la prise/garde du contrôle coûteuse. Cette stratégie fonctionne car prendre/garder le contrôle dans la boucle n'a pas de sens pour le joueur A puisqu'il coûte 4 cases mais ne gagne que 3 cases dans la dernière chaîne.
+---+---+---+---+A14+ | B1 A13 B8 | | +A2-+A12+---+A9-+B15+ | | A11 A10 | | +A3-+---+---+---+B16+ | A4 A5 B7 | | +---+---+---+A6-+B17+
Le score est alors A:B = (4+6+0):(2+0+3) = 10:5
Si A ne joue pas DD dans la première chaîne :
+---+---+---+---+B14+ | B1 B13 A8 | | +A2-+B12+---+B9-+A15+ | | B11 B10 | | +A3-+---+---+---+A16+ | A4 A5 A6 | | +---+---+---+A7-+A17+
alors le score A:B = (6+0+3):(0+6+0) = 9:6 serait pire pour A. La raison est que jouer dans la boucle après son ouverture (B9 ci-dessus) vaut 6−3=3 points et prendre le contrôle dans la première longue chaîne ne coûte que 2 points, donc cela vaut la peine de prendre le contrôle dans la première chaîne. 10:5 vaut mieux que 9:6 pour le joueur A.
En comparant les cas 1 et 2 et les deux scores 11:4 et 10:5, il est clair que le joueur B doit ouvrir la chaîne la plus longue en premier. La raison en est que si B ouvrait la chaîne linéaire déconnectée en premier, la boucle serait complétée en dernier, ce qui signifie que le joueur A n'aurait pas à payer 4 points lorsqu'il joue DDD dans la boucle pour garder le contrôle. Nous violerions notre règle n° 2 précédente. On peut montrer en général que si la chaîne déconnectée a m cases, la chaîne linéaire connexe a n cases et la boucle a p cases puis le joueur B ouvrant la chaîne déconnectée donne d'abord à B 4 points à partir de 2 fois DD alors que lorsque B ouvre la chaîne linéaire attachée, B obtient
min(p + max(0,m-4),min(6,m+2))
points. La valeur la plus basse que cela peut prendre est lorsque p a sa valeur la plus basse qui est 4 (une boucle a au moins 4 cases) et m a sa valeur la plus basse qui est 3 (la valeur la plus courte longue chaîne linéaire, si la chaîne la plus courte n'avait que 2 cases qui seraient jouées instantanément avec Hard-Hearted Handout et la formule serait différente). Pour p = 4 et m = 3, le joueur B obtiendrait
min(4 + max(0,-1),min(6,5)) = min(4+0,5) = 4
et pour p > 4 ou m > 4 le joueur B obtiendrait plus de 4 points.
Que faire lorsqu'il y a des chaînes différentes égales ayant la même valeur minimale ?
Si de différentes chaînes ont la même valeur minimale, notre programme utilise la règle pour ouvrir une chaîne connectée. L'idée sous-jacente est qu'il est possible qu'à travers cette chaîne ouverte, une boucle devienne accessible, ce qui peut rendre la prise/le maintien du contrôle plus coûteux.
Durant une partie, on prend généralement le contrôle en jouant DD/DDD au début de la fin de partie. Mais s'il y a beaucoup de chaînes avec 3 cases et de boucles avec moins de 8 cases alors il peut être préférable de ne pas jouer DD/DDD et de ne pas prendre le contrôle. Nous avons donc besoin d'un algorithme général et pas seulement d'une règle empirique.
Quand faut-il jouer / ne pas jouer DD/DDD ?
Dans la littérature sur la Pipopipette, la première fois qu'on effectue un coup DD/DDD est aussi appelé « prise de contrôle. ». Cela signifie que le joueur prend le contrôle de qui obtient la dernière longue chaîne, ce qui peut ne pas être la même chose que de prendre le contrôle de la partie et de la remporter en ne jouant PAS un coup DD/DDD comme nous le verrons ci-dessous.
Lorsqu'un joueur a la possibilité de jouer DD/DDD alors ce joueur a la possibilité d'inverser les rôles avec l'adversaire au prix de 2 points (DD) ou 4 points (DDD). Si l'on connaît le score qu'on peut obtenir en jouant de manière optimale dans les chaînes restantes, alors on peut décider s'il vaut la peine de changer de rôle maintenant au prix de 2 (si la chaînedans laquelle on joue actuellement est linéaire) ou au prix de 4 (si la chaîne dans laquelle on joue actuellement est une boucle). Avec les gains de la chaîne actuelle, on peut déterminer le score avant d'ouvrir la chaîne actuelle. Ce calcul peut être effectué à l'envers à partir de la fin de la partie si l'on connaît la séquence des chaînes ouvertes. Une telle séquence peut être déterminée par la Règle n° 4 ci-dessus.
Règle n°5 : Décidez s'il faut jouer ou ne pas jouer DD/DDD en suivant le pseudo-code ci-dessous.
Dans le pseudo-code informatique suivant, la variable A est le nombre de points obtenus dans la suite du jeu par le joueur qui ouvre la chaîne suivante, et la variable B est le nombre de points obtenus par l'autre joueur. Le nombre de cases restantes est A+B. On fait le calcul à l'envers et par facilité on étiquète aussi les chaînes à l'envers : la dernière chaîne ouverte dans la partie est la chaîne 1, la chaîne d'avant est la chaîne 2 et ainsi de suite. La chaîne actuelle est la chaîne k. Toute chaîne j a n_j cases. La variable coupDD enregistre si DD/DDD est effectué dans la chaîne j.
Dans les lignes de pseudo-code suivantes
- (1)-(3) initialize les 3 varialbes comme étant le résultat d'avoir joué dans la dernière chaîne.
- (4)-(22) mettent à jour A, B, coupDD pour la chaîne j où j s'étend à l'envers depuis l'avant-dernière chaîne (j=2) jusqu'à la chaîne actuelle, la chaîne k.
- (5)-(13) si la châine j est linéaire alors le coût sera 2
- (14)-(22) si la chaîne j est une boucle alors le coût sera 4
- (6)-(9), (15)-(18) si le gain B−A est plus grand que le coût (2 ou 4) alors effectuer un coup DD et réduire B par le coût et l'ajouter à A. Dans tous les cas on ajoute à B la valeur n_j.
(1) A = 0
(2) B = n_1
(3) playDD = faux
(4) Pour chaque chaîne j de If 2 à If k:
(5) Si chaîne j est linéaire:
(6) Si B > (A + 2):
(7) playDD = vrai:
(8) B = B + n_j - 2
(9) A = A + 2
(10) Sinon {}:
(11) playDD = faux:
(12) B = A + n_j
(13) A = B
(14) Sinon {} → Si chaîne j est une boucle:
(15) Si B > (A + 4):
(16) playDD = vrai
(17) B = B + n_j - 4
(18) A = A + 4
(19) Sinon {}
(20) playDD = faux
(21) B = A + n_j
(22) A = B
Après ce calcul A est le score obtenu par le joueur ayant ouvert la chaîne actuelle, B est le score pour son adversaire, et coupDD indique si l'adversaire devrait maintenant effectuer un coup DD/DDD. ∎ (Fin de la Règle n°5)
Ce pseudo-code peut sembler difficile pour quelqu'un n'ayant aucune expérience avec la programmation, mais il est facile à exécuter dans sa tête car il sert seulement à vérifier si l'avantage de garder le contrôle emporte sur le coût, c'est-à-dire le coût de faire un coup DD/DDD.
Test de connaissances
On sait que les chaînes avec le moins de valeur sont celles qui sont ouvertes en premier. Est-ce que cela veut dire que les coups DD/DDD deviennent de plus en plus avantageux vers la fin de partie ?
Autrement dit, est-ce qu'effectuer un coup DD/DDD maintenant implique toujours qu'il faut continuer de l'effectuer jusqu'à la fin de partie car sinon l'adversaire prendrait le contrôle et la remportera ?
Oui, dans presque tous les cas. Mais nous avons vu dans l'exemple 6, cas n°2, qu'il est possible qu'une boucle de faible valeur ne devienne accessible qu'après des chaînes de plus grande valeurs sont complétées. En conséquence, bien qu'il n'y ait pas eu suffisamment d'avantage à jouer DDD lorsque la boucle a été ouverte (la dernière chaîne n'avait que 3 cases alors que DDD coûte 4 cases), l'avantage était suffisante pour jouer DD plus tôt car ceci ne coûte que 2 points.
Test de connaissances
Supposez que quelqu'un estime correctement s'il faut effectuer un coup DD/DDD. Le joueur décide d'effectuer un tel coup et d'obtenir la dernière chaîne.
Est-ce que ce joueur remportera toujours la partie ?
Non. Par exemple, supposons que nous ayons 5 chaînes linéaires avec 3 cases chacune. Obtenir le dernier donne un avantage de 3 cases, ce qui est suffisant pour payer 3 DD coûtant chacun 2 points et obtenir ainsi 1 case. Cela signifie que la première chaîne est terminée dans son ensemble et que 3 autres coups DD donnent des scores (3+2+2+2+0) : (0+1+1+1+3) = 9:6 pour le joueur qui n'a pas obtenu la dernière chaîne.
Est-ce que ces règles pour la fin de partie sont parfaites ?
Non. Lorsque l'on a plusieurs chaînes connectées via des cases-0 et des cases-1, plusieurs d'entre elles peuvent avoir le même nombre de cases, puis une théorie ou une recherche plus raffinée peut être nécessaire pour sélectionner la chaîne optimale en fonction de laquelle des autres chaînes deviennent accessibles par la suite de la complétion des autres chaînes.
Est-ce que la théorie de la fin de partie ci-dessus change lorsque l'adversaire effectue un « Half-Hearted Handout » de manière non-optimale ??
Les positions
+---+---+ +---+ + | ou | | +---+---+ +---+---+
ou des versions réfléchies/ tournées sont pour nos règles pareilles à toute chaîne linéaire mais avec 2 cases. Ces chaînes donnent au prochain joueur l'option de prendre la chaîne ou d'effectuer un coup DD alors on les traite comme des chaînes longues à au moins trois cases.
La Règle des Chaînes Longues
Règle n°6: Le premier joueur doit essayer de rendre pair le nombre de points + le nombre de chaînes longues linéaires et le deuxième joueur doit essayer de rendre cette valeur impaire.
Justification de la règle
Pour commencer on introduit quelques variables où '#' signifie « nombre »:
nt = # de tours (# de tours qu'un joueur a effectué des coups consécutifs)
nd = # de points
r = # de rangées de points
c = # de colonnes de points
nl = # de lignes
nb = # de cases
nc = # de chaînes longues
nz = # du tour qui a ouvert la première chaîne longue de la fin de partie
On commence par déduire une relation connue sous le nom « l'Identité d'Euler ».
nb = (r−1)(c−1) = rc − r − c + 1
nd = rc
nl = # de lignes horizontales + # de lignes verticales
= r(c−1) + c(r−1)
= 2rc − r − c
et alors
nl = nb + nd − 1 .
Cette relation est équivalente à l'identité d'Euler qui est valable pour des graphes arbitraires, c'est-à-dire tout nombre nd de points reliés par tout nombre nl de lignes, non seulement verticalement et horizontalement, entourant nf faces où dans ce cas nf = nb + 1 car la grille rectangulaire de points a une face environnante supplémentaire qui est également comptée dans l'identité d'Euler :
nl − nd + 2 = nf (= nb + 1).
Ensuite on calcule le nombre de tours composant la partie :
nt = nl − ((# de fois où le traçage d'une ligne a complété au moins 1 case)
− 1 {Compléter la dernière case ne donne pas de coup par la suite.})
= nl − (nb − (# de coups qui complètent 2 cases) − 1)
= nl − nb + 1 + (# de coups qui complètent 2 cases)
= nd {en se servant de la relation obtenue plus tôt nl = nb + nd − 1}
+ (# de DD effectués dans des chaînes linéaires) + (# de boucles) + (# de DDD effectués dans des boucles)
La dernière ligne résulte du fait que lors de la complétion d'une boucle, le dernier coup complète toujours deux cases et si DDD est joué en boucle, un autre coup complète également 2 cases. On appelle la relation dérivée la Formule du Nombre de Termes :
nt = nd + (# de DD effectués dans des chaînes linéaires) + (# de boucles) + (# de DDD effectués dans des boucles)
Il s'agit d'une règle exacte sans approximations.
Calculer nz, c'est-à-dire le tour qui ouvre la première chaîne longue
Après l'ouverture de la première chaîne longue dans la phase finale, si aucun DD et aucun DDD n'est joué, alors le nombre de tours restants est égal au nombre de chaînes longues lorsque chaque joueur complète une chaîne. Par conséquent, si (# de DD) = (# de DDD) = 0 alors
nz {# du tour qui ouvre la première chaîne longue de la fin de partie}
= nd + (# de boucles) − (# de chaînes longues)
= nd − (# de chaînes longues linéaires)
Aucun coup DD/DDD effectué ne pourrait changer ce qui s'est déjà passé auparavant, à savoir les nz tours qui mènent à l'ouverture de la première chaîne longue de la fin de partie. Pour chaque DD et DDD joué, le nombre de tours dans la fin de partie augmente de 1 (veuillez vérifier par vous-même) donc en soustrayant le nombre de tours dans la fin de partie du nombre total de tours, alors (# de DD) et (# de DDD) seraient annulés et on obtiendrait la même valeur pour nz que lorsqu'aucun DD/DDD n'a été joué.
Donc, aucun joueur ne veut faire ce mouvement, c'est-à-dire que le premier joueur ne veut pas que nz soit impair et veut donc que nz soit pair. 2 × (# de chaînes longues linéaires) est un nombre pair, donc l'ajouter à nz ne change pas si nz est impair ou pair, ce qui aboutit finalement à la
Règle des Chaînes Longues :Le premier joueur essaie de faire en sorte que (# de points) + (# de chaînes longues linéaires) soit pair pendant que le deuxième joueur essaie de le rendre impair. ∎
Une mauvaise déduction de la Règle des Chaînes Longues
Dans certaines publications sur le jeu DOTS, deux hypothèses inutiles sont faites pour dériver la Règle des Chaînes Longues.
Supposition n°1 : Si les deux joueurs jouent la fin de partie de manière optimale, alors celui qui joue le dernier coup gagne en raison de la valeur élevée de la dernière et plus grande chaîne et du fait de ne pas avoir à jouer à nouveau et à ouvrir une autre chaîne pour l'adversaire.
Alors le premier joueur veut que nt = (# de tours) soit impair pour pouvoir effectuer le premier et le dernier coup et gagner.
Supposition n°2 : Toutes les chaînes longues sauf la dernière chaîne sont jouées avec DD/DDD. Ainsi (# de boucles) + (# de DDD dans les boucles) est pair et peut être ignoré et nt = nd + (# de DD dans les chaînes linéaires) devient nt = nd + (# de longues chaînes linéaires) − 1. Par conséquent, le premier joueur veut que ce nt soit impair pour pouvoir faire le dernier coup qui arrive lorsque (# de points) + (# de chaînes longues linéaires) est pair - la Règle des Chaînes Longues. ∎
Mais on sait que ces deux suppositions ne sont pas nécessaires pour que la Règle des Chaînes Longues soit vraie. Le prochain exemple démontrera ceci.
Quel succès est garanti par la règle pour l'un des joueurs ?
La Règle des Chaînes Longues donne une condition nécessaire et suffisante pour décider quel joueur est le premier à jouer dans la première chaîne longue ouverte durant la fin de partie. Ce joueur P peut choisir d'effectuer ou de ne pas effectuer un coup DD/DDD. On a donc 2 cas à considérer.
Si la première chaîne longue est linéaire alors elle a au moins 3 cases, et jouer DD a un coût de 2 cases.
• Si l'incitation à jouer DD est <2 alors le joueur P ne jouera pas DD et prendra toute la première chaîne et l'adversaire obtiendra au plus 1 case de plus des chaînes restantes, donc P obtient dans la fin de partie au moins 3−1 = 2 cases de plus que l'adversaire.
• Si l'incitation est de 2, alors il importe peu que P joue ou ne joue pas DD dans la première chaîne longue et prend donc ≥ 3 cases de plus dans la fin de partie.
• Si l'incitation est >2 alors P joue DD et obtient >3 cases de plus dans la fin de partie.
Si la première chaîne longue est une boucle alors dans le pire des cas la première chaîne a 4 cases et l'incitation est de 4 et ensuite si l'on joue DDD ou non, les deux joueurs obtiendront le même nombre de points dans la fin de partie. Mais si l'incitation est > 4, alors jouer DDD donnera plus de points et si l'incitation est < 4 alors ne pas jouer DDD donnera plus de points car la boucle a au moins 4 cases. Et si la première chaîne longue est une boucle avec plus de 4 cases, alors P obtiendra ces points supplémentaires comme un avantage dans la fin de partie, même si l'incitation est de 4.
Quelles sont les différences de score possibles au début de la fin de partie ?
• Si le nombre de chaînes à 1 case est pair et que le nombre de chaînes à 2 cases linéaires est pair, la différence de score au début de la fin de partie est nulle.
• Si le nombre de chaînes à 1 case est pair et le nombre de chaînes à 2 cases linéaires est impair, le score au début de la fin de partie est de 2.
• Si le nombre de chaînes à 1 case est impair, après avoir terminé toutes les chaînes à 1 case, la différence de score est de 1. Ensuite, chaque chaîne à 2 cases complétée ne sera retournée qu'entre les deux joueurs qui ont une case d'avance.
Alors, quelle est l'importance de la Règle des Chaînes Longues ?
Quand la Règle de la Longue Chaîne ne détermine-t-elle pas le résultat ?
Quelle règle suivre alors ?
Exemple 7: Tester la Règle dans une situation inhabituelle
Sur la grille, un nombre impair de 5 × 3 = 15 coups ont été effectués. Le coup 16 ouvrira la première chaîne longue qui satisfait la formule qu'on a dérivée : 16 = (# de points) - (# de chaînes longues linéaires) = 20 − 4. Celui qui fait ce coup, dans ce cas le joueur B, perdra si le joueur A joue DD de manière optimale.
+ + + + + | | | | | + + + + + | | | | | + + + + + | | | | | + + + + +
Le joueur A a commencé et maintenant le joueur B doit ouvrir une chaîne.
Quel est le score lorsque trois DD sont effectués ?
Si A joue 3 fois DD alors le score final sera A:B = 6:6.
+---+---+---+---+ | A | A | A | A | +---+---+---+---+ | B | B | B | A | +---+---+---+---+ | B | B | B | A | +---+---+---+---+
Le score obtenu à partir des 3 dernières chaînes est 5:4, alors effectuer DD dans la première chaîne et payer 2 points pour en obtenir 1 n'est pas optimal.
Quel est le score lorsque deux DD sont effectués ?
Pour A il est plus avantageux de prendre la totalité de la première chaîne et obtenir ainsi A:B = 7:5.
+---+---+---+---+ | A | B | B | B | +---+---+---+---+ | A | A | A | B | +---+---+---+---+ | A | A | A | B | +---+---+---+---+
Quelle supposition de la mauvaise déduction de la Règle des Chaînes Longues est violée?
Les deux! A remporte la partie mais ne prend pas la dernière chaîne. On n'effectue pas DD dans toutes les chaînes longues linéaires.
Est-ce que la Règle des Chaînes Longues reste valide pour ce cas de jeu optimal?
On obtient (# de points) + (# chaînes longues linéaires) = 20 + 4 = 24 qui est pair et le premier joueur gagne comme le prédit la règle. Cette règle est donc meilleure que la preuve alternative avec des hypothèses inutiles et des interprétations erronées.
Test de connaissances
Est-ce que le jeu optimal nécessite SOIT de jouer DD/DDD SOIT de ne pas jouer DD/DDD ?
Non, les deux peuvent être également utiles. Avec seulement 2 chaînes longues à 3 cases, A a besoin de jouer DD pour obtenir un score de A:B = 4:2.
+ + + +---+---+ | | | | A | A | + + + +---+---+ | | | → | B | A | + + + +---+---+ | | | | B | A | + + + +---+---+
Ainsi, l'avantage de jouer DD avant ces deux chaînes est de 4 − 2 = 2, ce qui est égal au coût de jouer à DD. Par conséquent, les deux parties donnent le même score : 4 : (2+3) = 4 : 5 = (2+2) : (4+1)
+---+---+---+ +---+---+---+ | B | A | A | | B | B | B | +---+---+---+ +---+---+---+ | B | B | A | = | A | A | B | +---+---+---+ +---+---+---+ | B | B | A | | A | A | B | +---+---+---+ +---+---+---+
Test de connaissances
Pourrait-il arriver dans des conditions de jeu optimales que les joueurs commencent et arrêtent de jouer à DD/DDD à plusieurs reprises ?
Oui. On a vu ci-dessus comment l'ajout d'une chaîne de 3 cases a fait passer le score de 4:2 à 4:(2+3) = 4:5. L'avantage de jouer DD avant ces 3 chaînes serait de 5−4 = 1 < 2 donc moins que le coût de jouer DD qui est de 2. Ainsi, avec quatre chaînes de 3 cases, on ne jouerait pas DD dans la première. S'il y avait une autre chaîne avec 3 cases, le score deviendrait (4+3):5 = 7:5 = (4+1):(5+2) donc l'avantage de jouer en deuxième dans 5 chaînes de 3 cases serait 7−5 = 2 donc jouer DD serait valable donnant dans les deux cas un score de (2+5):(1+7) = 7:8 = 7:(3+5).
+---+---+---+---+---+ +---+---+---+---+---+ | B | B | A | A | A | | B | B | A | B | B | +---+---+---+---+---+ +---+---+---+---+---+ | A | B | B | B | A | = | A | B | A | A | B | = +---+---+---+---+---+ +---+---+---+---+---+ | A | B | B | B | A | | A | B | A | A | B | +---+---+---+---+---+ +---+---+---+---+---+ +---+---+---+---+---+ +---+---+---+---+---+ | B | A | B | B | B | | B | A | B | A | A | +---+---+---+---+---+ +---+---+---+---+---+ | B | A | A | A | B | = | B | A | B | B | A | +---+---+---+---+---+ +---+---+---+---+---+ | B | A | A | A | B | | B | A | B | B | A | +---+---+---+---+---+ +---+---+---+---+---+
En rajourant plus de chaînes à 3 cases on pourrait avoir encore plus d'alternations entre jouer et ne pas jouer DD.
Est-ce que la Règle des Chaînes Longues est satisfaite ?
On encourage le lecteur à vérifier la Règle des Chaînes Longues dans d'autres exemples avec des boucles.
Exemple 8 : Appliquer la Règle des Chaînes Longues
Sur ce site web de David Wilson on retrouve la position suivante où le joueur suivant peut effectuer un seul coup peut remporter la partie.
+ + + +
|
+ + +---+
+---+---+---+
|
+ +---+ +
Qui est-ce qui gagnera en suivant les règles de fin de partie détaillées ici ?
Cette grille a un nombre pair de points et un nombre pair de chaînes longues. La dernière chaîne longue n'aura pas de coup DD joué donc un nombre impair de coups DD sera normalement joué et donc # de points + # de DD est impair ce qui veut dire que le nombre de tours est impair donc le premier joueur obtiendra la dernière chaîne et gagnera. Ceci est conforme à la « Règle des Chaînes Longues » selon laquelle « Le premier joueur essaie de faire en sorte que (# de points) + (# de chaînes longues linéaires) soit pair pendant que le deuxième joueur essaie de le rendre impair. »
Que peut faire le deuxième joueur ?
Le 2ème joueur ne peut pas changer le nombre de points mais plutôt le nombre de coups DD en sacrifiant 2 cases et en jouant le coup marqué B qui est le seul coup gagnant que le 2ème joueur a dans cette situation :
+ + + +
|
+ + +---+
+---+---+---+
| B
+ +---+ +Ce coup réduit le nombre de chaînes longues de 2 à 1 et rend ainsi # de points + # de chaînes longues (linéaires) impairs et permet ainsi au 2ème joueur de gagner d'un point au lieu de perdre d'un point.
Comment la partie pourra-t-elle continuer ?
Les variations suivantes mènent toutes vers un score de A:B = 4:5 alors à une victoire par 1 point pour B.
+ +A10+B6-+
A3 | B9 A11
+ +A5-+---+
B4 A12
+---+---+---+
| | A2 B8
+A1-+---+A7-+
+A3-+A5-+B6-+
A11 | A12
+B9-+ +---+
A10 B4
+---+---+---+
| | A2 B8
+A1-+---+A7-+
+A3-+A10+B6-+
| B9 A11
+ +B4-+---+
A5 A12
+---+---+---+
| | A2 B8
+A1-+---+A7-+
Effectuer ce coup viole la toute première règle n° 1 de ne pas créer de cases-3 si ce n'est pas vraiment nécessaire. Est-ce que cette violation est vraiment grave ?
Cette violation de la règle n° 1 n'est pas moins étrange que de jouer DD. Comme on l'a découvert plus tôt, il est normal de jouer à DD et de payer un prix de 2 points afin d'échanger les rôles. Donc, ce sacrifice est minime et justifié s'il a le même effet qu'un mouvement DD.
Dans la partie ci-haut on a introduit des termes techniques et formulé des règles. La fin de partie est décrite en détail et pour la première partie du jeu, la règle des chaînes longues donne quelques indices. Si vous souhaitez en savoir plus sur la première partie du jeu, veuillez vérifier [2] et [3] dans les références. L'arbre de décision suivant résume cette page Web.
Un Arbre de Décision
Pour que les liens ci-dessous fonctionnent, veuillez ouvrir toutes les sections ci-haut en cliquant sur
- Avant de commencer la partie, réfléchissez à la question de jouer en premier ou non. Voir point 3.A.a ci-dessous.
- S'il y a au moins une case-3 (une case qui peut être complétée), alors identifiez toutes les chaînes qui sont attachées à toutes ces cases-3.
- Si l'une de ces chaînes est linéaire et a au moins 2 cases voisines, alors complétez toutes les cases de toutes les chaînes linéaires et de toutes les chaînes bouclées à l'exception de ces deux cases voisines de cette seule chaîne linéaire. Ensuite, analysez s'il faut jouer DD et jouez DD ou remplissez les 2 dernières cases.
- Si toutes les chaînes ont une longueur de 1 ou sont bouclées, complétez d'abord toutes les chaînes de longueur 1 et s'il y a au moins une chaîne bouclée, complétez toutes les chaînes bouclées sauf les 4 dernières cases de l'une des chaînes bouclées. Ensuite, analysez s'il faut jouer à DDD ou remplissez les 4 dernières cases.
- S'il n'y a aucune case qui ne peut être complétée alors
- Si tous les coups possibles créeront une case-3 alors
- si la plus petite chaîne est de longueur 2
+---+---+ +---+---+
où les deux lignes non-tracées peuvent être n'importe où mais pas dans la même case, alors jouez au milieu pour obtenir :+---+---+ | +---+---+ - Sinon, déterminez la prochaine chaîne à ouvrir et jouez n'importe où dans cette chaîne.
- si la plus petite chaîne est de longueur 2
- s'il y a un coup qui ne créera pas de case-3 alors
- si dans la partie il y aura au plus 1 chaîne longue (linéaire ou bouclée), par exemple, parce que le rectangle de points est petit ou étroit, alors aucun coup DD/DDD ne sera joué et alors le joueur prenant le dernier tour gagne et en raison de la Formule du Nombre de Termes, le premier joueur doit essayer de rendre la somme # de points + # de boucles impaire et le deuxième joueur doit la rendre paire. Comme le nombre de points est fixe, on ne peut essayer d'obtenir que 0 respectivement 1 boucle. Si cela est impossible, on peut changer qui joue en premier.
- s'il est clair combien de chaînes linéaires existeront à la fin de la partie et si la Règle des Chaînes Longues prédit la perte de la partie, envisagez alors de faire un coup de sacrifice pour réduire le nombre de longues chaînes, sinon
- s'il n'est pas clair combien de chaînes longues il y aura à la fin de partie alors en tant que premier joueur, essayez de rendre impair le # de points + le # de longues chaînes (linéaires) et en tant que deuxième joueur, essayez de rendre la somme paire.
- Si tous les coups possibles créeront une case-3 alors
Références
[1] Wikipedia: Dots and Boxes, et les autres sources citées sur cette page.
[2] Berlekamp, Elwyn R.; Conway, John H.; Guy, Richard K. (1982), 'Chapter 16: Dots-and-Boxes', Winning Ways for your Mathematical Plays, Volume 2: Games in Particular, Academic Press, pp. 507–550.
[3] Berlekamp, Elwyn (2000), The Dots-and-Boxes Game: Sophisticated Child's Play, AK Peters, Ltd, ISBN 1-56881-129-2.
[4] Wilson, David, Dots-and-Boxes Analysis Results, University of Wisconsin
Index
Pour que les liens ci-dessous fonctionnent, veuillez ouvrir toutes les sections ci-hautes en cliquant sur
- # ...
- le nombre de ...
- Case
- un petit carré ayant aux sommets 4 points avoisinants
- Case-?
- case-0, case-1, case-2, case-3, case-4 sont des cases ayant 0, 1, 2, 3, 4 lignes tracées sur leurs côtés.
- Chaîne
- une séquence composée de cases-2 reliées. Il y a des chaînes linéaires et des chaînes bouclées.
- Coup « Double-Crossed »
- un coup qui complète deux cases voisines en même temps. Il se joue immédiatement après un coup Double Dealing dans une chaîne linéaire ou lorsqu'une boucle est complétée.
- DD
- abréviation de Double Dealing
- DDD
- abréviation de Double Double Dealing
- Double Dealing
- un coup effectué sur le bord d'un « Half-Hearted Handout » menant à
- Double Double Dealing
- un coup effectué au milieu d'une boucle ouverte avec 4 cases restantes, ce qui crée, par exemple,
+---+---+ +---+---+---+---+ | | | | | +---+---+ ou +---+---+---+---+ ou | | +---+---+ +---+---+ +---+---+---+ | | | | | +---+---+---+ ou +---+---+ + | | | | +---+---+ +---+ - Fin de partie
- l'étape finale de la partie qui commence lorsqu'il devient inévitable de créer une case-3 lors du prochain coup
- L'identité d'Euler
- une relation générale pour tout graphe dans le plan, où les lignes ne se croisent pas (pas seulement dans le jeu de la Pipopipette): (# de lignes) − (# de points) + 2 = (# de faces) où les faces comptent aussi la face 'extérieure' alors pour la Pipopipette (# de faces) = (# de cases) + 1.
- Graphe
- un concept mathématique où un nombre de points sont connectés par un nombre de lignes
- « Hard-Hearted Handout »
- tracer la ligne du milieu dans
+---+---+ +---+---+ +---+---+ ou | ou | | +---+---+ +---+ + + + +ou des versions réfléchis ou tournés ce qui résulte en+---+---+ +---+---+ +---+---+ | ou | | ou | | | +---+---+ +---+ + + + +ou des versions réfléchis ou tournés. - « Half-Hearted Handout »
- tracer une ligne sur le bord d'une chaîne avec deux cases menant à
+---+---+ +---+---+ | ou | | +---+---+ +---+ +
- Ligne
- le segment de ligne reliant deux points horizontalement +---+ ou verticalement
- Chaîne Linéaire
- une chaîne qui a deux bouts, mais qui n'est pas nécessairement droite
- Règle des Chaînes Longues
- Le premier joueur doit essayer de rendre la somme du # de points + du # de chaînes longues paire, et le deuxième joueur doit essayer de rendre la somme impaire.
- Chaîne Longue
- une chaîne ayant ≥ 3 cases
- Coup fou
- un coup donnant à l'adversaire l'option de faire un sacrifice
- Boucle
- abbréviation pour chaîne bouclée
- Chaîne Bouclée
- une chaîne sans bouts
- Coup
- le fait de tracer une ligne
- Formule du Nombre de Termes
- une formule exacte donnant le nombre de tours dans un jeu qui est la base de la Règle des Chaînes Longues et qui est utile pour un petit nombre de points pour décider de joueur en premier ou non.
- Ouvrir une chaîne
- effectuer un coup à l'intérieur d'une chaîne ou sur l'un de ses bouts (si elle est linéaire)
- Règle n°1
- La stratégie la plus évidente consiste à éviter de créer une case-3 que l'adversaire pourra prendre en la complétant.
- Règle n°2
- Pour classer les chaînes selon l'ordre dans laquelle on devrait les ouvrir, prendre comme la dernière chaîne la plus longue chaîne linéaire et s'il n'y a pas de chaîne linéaire prend la plus grande boucle.
- Règle n°3
- Si lors de la fin de partie toutes les cases ont au moins 2 bords tracés alors pour ordonner toutes les autres chaînes, classez-les par (# de cases) − 2 (si c'est une boucle).
- Règle n°4
- Pour établir une séquence de chaînes triées par leur valeur pour le prochain joueur, avec la plus petite valeur en premier, effectuez une séquence de coups (voir le texte ici) jusqu'à ce que la grille soit complète.
- Règle n°5
- Utiliser le pseudo-code fourni (voir le texte) pour déterminer s'il faut jouer ou ne pas jouer DD/DDD.
- Règle n°6
- Fait référence à la Règle des Chaînes Longues
- Prendre le Contrôle
- équivaut jouer DD/DDD ce qui donne l'effet secondaire important de pouvoir continuer de jouer DD/DDD dans les chaînes suivantes.
- Tour
- séquence de coups consécutifs d'un joueur
Suivez ou abonnez-vous à l'Infolettre