iChomp

Jeux Combinatoires: Des jeux à deux personnes, sans hasard, sans information cachée, où chaque joueur doit gagner ou perdre.

Jeux Impartiaux: Des jeux combinatoires dans lesquels les coups autorisés dépendent uniquement de la position et pas du joueur dont c’est le tour. En plus, les gains sont symétriques, c.-à-d. La seule différence entre le Joueur 1 et le Joueur 2, c’est que le joueur 1 joue en premier. Ex : Chomp.

Jeux Partisans: Des jeux qui ne sont pas impartiaux. Ex: les Échecs.

Version Normale: Le joueur qui joue en dernier GAGNE, c.-à-d. le joueur qui ne peut plus faire de coup, qui ne peut plus rien enlever du plateau, perd.

Version Misère: Le joueur qui joue en dernier PERD.

Chomp: Le jeu en Version Misère sur notre page de jeux qui utilise un seul quadrant

Le jeu de Chomp sur notre site se joue-t-il en Version Normale ou en Version Misère?
- Notre jeu de Chomp se joue en Version Misère car le joueur qui prend le dernier bonbon perd.
Le jeu de Chomp sur notre site se joue-t-il en Version Normale ou en Version Misère?
- Notre jeu de Chomp se joue en Version Misère car le joueur qui prend le dernier bonbon perd.
Pourquoi sera-t-il illogique de jouer à Chomp en Version Normale?
- La Version Normale voudrait dire que le joueur qui prend le dernier bonbon gagne, alors celui qui joue en premier pourrait gagner dès le départ en prenant le bonbon dans le coin supérieur gauche.
Le jeu d’iChomp sur notre site se joue-t-il en Version Normale ou en Version Misère?
- Notre jeu d’iChomp se joue en Version Normale car le joueur qui prend le dernier bonbon gagne.
Sera-t-il possible de changer le plateau de Chomp pour pouvoir y jouer en Version Normale?
- On pourra commencer le jeu dans une position où il manque le bonbon (empoisonné) dans le coin supérieur gauche. Pour remporter la partie en Version Normale il faudra prendre le dernier bonbon. En Version Misère, gardant le bonbon empoisonné, l’autre joueur devra prendre ce bonbon et perdra, en effet le même résultat.
  
  Alors c’est exactement pareil de jouer en Version Misère avec une case supérieure gauche ou de jouer en Version Normale sans la case supérieure gauche.

Le jeu d’iChomp est conçu comme l’union de quatre jeux de Chomp joués en même temps en Version Normale. Ceci rend le jeu plus beau en deux aspects qu’on expliquera ci-dessous. Quoiqu’il puisse paraître, si on applique le théorème de Sprague-Grundy (décrit ci-dessous, aussi), iChomp ne s’avère pas beaucoup plus difficile que Chomp.

Il s’applique à une certaine classe de jeux, celle des jeux combinatoires impartiaux. Ce théorème apporte deux avantages:
1. Il nous donne un algorithme qui détermine pour chaque jeu (c.-à-d. chaque position) un nombre (appelé ici la valeur SG) tel que le nombre est 0 uniquement s’il représente une position perdante (appelée « position P » dans la littérature sur la théorie des jeux combinatoires où ‘P’ indique que le joueur ‘p’récédent a fait un coup gagnant). Ceci veut dire qu’une valeur SG de 1,2,3,… indique alors une position gagnante (appelée « position G » dans la littérature francophone, ou « position N » en anglais). Dans ce cas, celui qui joue prochainement (« Next » en anglais) peut s’assurer la victoire s’il joue de façon optimale.
2. Le deuxième avantage du théorème de Sprague-Grundy, c’est qu’il décrit comment gagner un jeu qui consiste en plusieurs positions jouées en même temps. On réalise un coup dans un tel jeu en faisant un coup dans n’importe laquelle des positions combinées.
  
  Ce qu’il faut savoir, c’est la valeur SG de chacune des positions combinées. Pour les obtenir il faut savoir la valeur SG résultant de chaque coup dans une des positions combinées. Il faut savoir les deux pour jouer de façon optimale.
  
  Par exemple : Dans le jeu de Nim on a un, deux ou plusieurs tas d’allumettes. Si on sait la valeur SG pour jouer sur chaque tas individuel, le théorème de SG indique la façon optimale de jouer en enlevant le bon nombre d’allumettes d’un de ces tas.
Le plus émerveillant dans le théorème de SG est le fait qu’il ne s’applique pas uniquement aux tas dans le jeu de Nim mais à toute position dans tout jeu combinatoire impartial. On pourra, par exemple, combiner plusieurs positions de Chomp pour créer un seul « Super-Chomp ». Plus loin encore, on pourra jouer de façon optimale à un jeu qui consiste en 5 positions différentes de Chomp et 3 tas d’allumettes et où on peut jouer dans n’importe quel jeu à un moment donné.

C’est la nouvelle version du jeu de Chomp introduit par les Concours Caribou auquel vous pouvez jouer sur cette page. Le « i » dans iChomp représente « isotrope » c.-à-d. que les propriétés sont les mêmes dans toutes les directions.

À la base, quand on enlève un bonbon dans Chomp on enlève aussi tous les bonbons à son Est et au Sud. Alors les directions Est et Sud ont un rôle particulier.

Dans iChomp on peut enlever les tuiles dans les autres directions aussi dépendamment de l’emplacement de la tuile sélectionnée par rapport au centre du plateau. Si on sélectionne une tuile qui se trouve au Nord-Ouest du centre par exemple, on enlève aussi toutes les tuiles à son Nord et Est.

Ainsi rend-on le jeu plus mathématiquement beau car on se débarrasse d’une règle artificielle, en l’occurrence la règle qui dit que le Sud et Est sont spéciaux.

iChomp démontre un deuxième embellissement par rapport à Chomp.

À la base la tuile dans le coin supérieur gauche a un rôle spécial par rapport aux autres tuiles, c.-à-d. que si elle est la seule tuile restante, le jeu est terminé. Quand on enlève une tuile différente, le jeu se poursuit. On pourra envisager de commencer Chomp sans cette tuile pour que toutes les tuiles soient égales, mais ceci aurait pour effet une règle artificielle de plus pour expliquer pourquoi cette tuile est absente et pas d’autres.

Comme vous pouvez voir, toutes les tuiles sont bien présentes au début d’iChomp. Elles sont égales: enlever une certaine tuile n’entraîne pas forcément la fin du jeu.

Quelques questions se posent:

iChomp est-il un jeu futile car c’est la combinaison de 4 plateaux de Chomp en Version Normale?
- Non. Par exemple, jouer au jeu de Nim avec un seul tas d’allumettes sera futile. En Version Normale, on pourra enlever le tas entier et gagner. Dans le jeu de Nim en Version Misère, on pourra enlever tout sauf une allumette et gagner. Toutefois, quand on combine de tels jeux de Nim à 1 tas pour créer un jeu de Nim à plusieurs Nim, comme on a fait sur notre page de jeu de Nim, le résultat n’est pas futile.
  
  C’est pareil ici : Un jeu de Chomp basique en Version Normale serait futile car on pourrait enlever toutes les tuiles d’un coup et gagner. Mais la combinaison de 4 tels jeux n’est pas futile.
Résumé de la Comparaison
- Par rapport à Chomp, le jeu iChomp fait preuve d’une beauté mathématique rehaussée car il est isotrope, c.-à-d. toutes les directions sont égales, et il n’y a pas une seule tuile qui détermine le résultat du jeu. Oui, ces changements font qu’iChomp est plus difficile que Chomp, mais le théorème de SG allégera en partie cette difficulté. Il suffit de savoir calculer la valeur SG des positions Chomp jusqu’à une certaine taille pour pouvoir déterminer facilement la valeur SG des positions iChomp jusqu’à 4 fois cette taille et donc pour savoir jouer à iChomp de façon optimale avec un plateau 4 fois plus grand.

La somme OU exclusif, abrégée en XOR, est une opération logique qui s’applique aux données binaires. Les données binaires ont deux valeurs possibles, Vrai (=1) ou Faux (=0). Appliquer l’opération XOR sur deux valeurs binaires donne la table de vérités suivante.

a b a XOR b
1 1 0
1 0 1
0 1 1
0 0 0

Il est facile d’appliquer cette opération à des valeurs de 1 (vrai) ou 0 (faux), mais pour nos computations il faut qu’on puisse réaliser l’opération XOR sur deux nombres. Ceci est possible, mais avant de pouvoir utiliser XOR, il faut réaliser une nouvelle étape.

Cette nouvelle étape est la conversion des nombres en binaire, c.-à-d. de tout convertir de la base 10 en base 2.

Comment convertit-on un nombre de base 10 en base 2?
- L’algorithme suivant permet de convertir un nombre n de base 10 en base 2. (Petit rappel: 2⁰ = 1):
  1. Trouvez la plus grande puissance de 2 de sorte que 2^p ≤ n.
  2. Marquez un 1 et soustraire 2^p de n.
  3. Si p = 0 alors arrêtez sinon soustraire 1 de p et continuez.
  4. Si 2^p > n alors marquez un 0 sinon soustraire 2^p de n et marquez un 1.
  5. Retournez à l’étape 3.
  La suite de 1s et de 0s que vous aurez marquée en suivant cet algorithme sera la représentation binaire du nombre n. Exemple:
  
  Convertissons le nombre 13 en base 2. On commence par trouver la plus grande puissance de 2 qui est inférieure ou égale à 13, ce qui donne 2³, ou 8. On marque 1 et on soustrait 8 de 13, ce qui donne 5. Ensuite on vérifie 2⁽³⁻¹⁾ = 2² = 4. Puisque 4 ≤ 5, on marque 1, et on soustrait 4 de 5, ce qui donne 1. La prochaine puissance de 2 est 2¹ = 2. Mais > > 1, alors on marque un 0. La prochaine puissance de 2 est 2⁰ = 1, égal à la valeur de n qui est 1, alors on marque un 1 et on soustrait 1 de 1, ce qui donne 0. Puisque p = 0 l’algorithme s’arrête. Alors 13 (base 10) = 1101 (base 2).
  
  Une fois les deux nombres convertis en représentation binaire, on peut réaliser l’opération XOR sur les chiffres correspondants des deux nombres binaires. Le résultat est un nombre binaire qui peut se reconvertir en base 10 s’il s’avère plus utile pour utiliser cette valeur XOR. Exemple:
  
  Calculons la valeur XOR des nombres 6 et 13. En binaire ces deux nombres s’écrivent 6=110 et 13=1101. D’abord on ajoute des 0s sur la gauche du plus petit nombre pour que les deux aient le même nombre de chiffres, alors 6=0110. On peut ensuite réaliser l’opération XOR dessus en les alignant et réalisant l’opération sur chacun des chiffres individuels:
  
  0110
  XOR 1101
  ------
  1011
  
  Alors 6 XOR 13 = 1011 (base 2) = 1×2³+0×2²+1×2¹+1×2⁰ = 8+2+1 = 11 (base 10).
Testons notre compréhension de XOR en répondant à quelques questions.

Quel est m XOR m pour tout nombre m?
- Pour tout nombre m l’opération m XOR m = 0 car 0 XOR 0 = 1 XOR 1 = 0.
Est-ce que n XOR m = m XOR n pour toute valeur de n et m?
- Oui, car 1 XOR 0 = 0 XOR 1 (=1).
Quel est 0 XOR m pour tout nombre m?
- 0 XOR m = m car 0 XOR 0 = 0 et 0 XOR 1 = 1.
Si on XOR un nombre m avec un nombre n à travers m XOR n alors quels chiffres de m seront changés?
- Si on XOR un chiffre de m avec 0 alors le chiffre reste le même (car 0 XOR 0 = 0 et 1 XOR 0 = 1). Si on XOR un chiffre de m avec 1 alors le chiffre change (car 0 XOR 1 = 1 et 1 XOR 1 = 0). Alors m XOR n fait changer tous les chiffres de m pour lesquels le chiffre correspondant en n est 1.

a	b	a XOR b
1	1	0
1	0	1
0	1	1
0	0	0

L’algorithme suivant permet de calculer la valeur SG de toute position P dans tout jeu combinatoire impartial. On se sert de Chomp comme exemple.
- Toute position perdante a la valeur SG de 0. Dans Chomp, une seule tuile (dans le coin supérieur gauche) est la seule position sans suite possible alors c’est une position perdante avec la valeur SG de 0.
- Il nous faut les valeurs SG de toutes les positions qu’on peut atteindre à partir de la position P en un coup. Alors si la position P a n tuiles alors il y a n – 1 coups possibles : à l’exception de la tuile supérieure gauche, on peut enlever toute autre tuile et toute les tuiles à sa droite et plus bas.
- La valeur SG d’une position P est le plus petit nombre positif qui ne figure pas dans cette liste de n – 1 valeurs SG atteignables.
Cet algorithme est récursif car il faut des valeurs SG pour calculer d’autres valeurs SG. Il marche quand même parce que les valeurs SG nécessaires ne regardent que des positions plus petites de moins de tuiles et parce que la valeur SF de la position la plus petite est connue.

Essayez de vérifier la troisième propriété dans le jeu. Sélectionnez une longueur et une largeur de plateau plus grandes et cliquez sur ‘Plateau Aléatoire’.
- Quand vous placez votre curseur sur une tuile, cette tuile ainsi que toutes les tuiles qui seraient enlevées sont surlignées en jaune. En Version Normale, le nombre dans cette tuile est la valeur SG du quadrant (mais pas en Version Misère) qui résultera si vous cliquez sur cette tuile. Vous pouvez vérifier que le nombre affiché dans le texte ‘Valeur SG Base Dix :’ à côté du quadrant est le plus petit nombre qui ne figure pas dans le quadrant. Vous pouvez le vérifier aussi en cliquant sur une tuile, alors le nombre sur cette tuile est maintenant affiché comme la ‘Valeur SG Base Dix’ de cette nouvelle position.
Comment déterminer les valeurs SG plus rapidement:

Puisqu’on peut atteindre la même position à partir de plusieurs positions en un coup, et puisque cette même position peut revenir plusieurs fois dans le calcul d’une position SG plus grande, ce serait donc un gaspillage d’effort énorme de tout recalculer à chaque fois. Alors, une fois qu’on a calculé la valeur SG d’une position P, on devrait la garder pour plus tard.

Si on voulait calculer la valeur SG de toutes les positions jusqu’à une certaine taille de plateau, alors l’approche suivante est utile. On commence par assigner la valeur SG de 0 à la seule position à une tuile (dans le coin supérieur gauche). Puis on utilise l’algorithme ci-dessous pour calculer les valeurs SG de toutes les positions à 2 tuiles, puis à 3 tuiles, et ainsi de suite.

Une position iChomp consiste en 4 positions Chomp, chacune dans un quadrant du plateau.
- D’abord il faut déterminer la valeur SG de chacune des 4 positions Chomp. Le quadrant vide n’est pas une position Chomp donc on y assigne la valeur −1.
- Puis on ajoute 1 à chaque valeur.
- Ensuite on convertit chacun des 4 nombres résultants en binaire.
- Après, on calcule la somme XOR de chacune des valeurs binaires pour obtenir la valeur SG de cette position (en format binaire). Si cette valeur est 0, la position est perdante, sinon elle est gagnante.

Pourquoi a-t-on ajouté ‘1’?

On ajoute un 1 pour obtenir la valeur SG d’une position Chomp en Version Normale à partir de la valeur SG en Version Misère. Le théorème suivant l’explique.

Théorème:
--------
Pour obtenir la valeur SG d’une position Chomp en Version Normale (c.-à-d. celui qui prend la dernière tuile gagne, ce n’est pas la manière habituelle de jouer à Chomp) il faut ajouter 1 à la valeur SG de cette même position en Version Misère (c.-à-d. celui qui prend la dernière tuile perd, d’habitude Chomp se joue ainsi).

Est-ce qu’on peut démontrer ce théorème par induction?
- Démonstration (par induction (et en pas mal de détail)):
  
  Cas de Base (1 tuile) :
  -------------------
  En Version Normale un plateau vide sans tuiles est une position perdante et a donc une valeur SG de 0. En plus, en Version Normale pour un plateau avec une tuile (dans le coin supérieur gauche) le seul coup possible est d’enlever cette tuile pour obtenir une position d’une valeur SG de 0. Alors en Version Normale la plus petite valeur positive qu’on ne peut pas atteindre avec un coup est 1, alors ceci est la valeur SG d’une position d’une tuile en Version Normale.
  
  En Version Misère, avoir une seule tuile est une position perdante d’une valeur SG de 0.
  
  Alors, pour 1 tuile la valeur SG en Version Normale est supérieure à celle de la Version Misère par 1.
  
  Étape inductive
  ---------------
  
  Hypothèse inductive (n tuiles):
  ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
  Supposons qu’il existe un nombre n tel que pour toutes les positions ayant ≥1 et ≤n tuiles, la valeur SG en Version Normale est supérieure par 1 à celle en Version Misère. Assertion Inductive (n+1 tuiles):
  ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
  On va démontrer que ceci est vrai pour toutes les positions avec n+1 tuiles.
  
  Étape inductive (n tuiles → n+1 tuiles):
  ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
  Pour toute position, les Versions Misère et Normale permettent les mêmes coups, sauf que la Version Normale permet d’enlever toutes les tuiles jusqu’à celle dans le coin supérieur gauche.
  
  Si la position a n+1 tuiles, alors effectuer un coup génère une position avec au plus n tuiles auquel on peut appliquer l’assertion inductive:
  
  On peut obtenir donc la liste des valeurs SG atteignables en Version Normale à partir de la liste des valeurs SG atteignables en Version Misère en les augmentant d’1 et en ajoutant la valeur 0 pour un coup qui enlève toutes les tuiles.
  
  Alors le plus petit nombre positif qu’on ne peut PAS atteindre en Version Normale est supérieur par 1 au plus petit nombre positif qu’on ne peut PAS atteindre en Version Misère. Autrement dit, pour la positon originale avec n+1 tuiles, la valeur SG en Version Normale est supérieure par 1 à la valeur SG en Version Misère ∎ (Ceci achève la démonstration.)

L’objectif est de réaliser un coup de sorte que la valeur SG de la position résultante soit 0. Quoi que soit le coup, il sera effectué dans un des 4 quadrants. Ceci veut dire que la somme XOR de la valeur SG de la position où on fait le coup ainsi que des valeurs SG des positions dans les 3 autres quadrants doit égaler 0. Ce n’est le cas que si la somme XOR des 3 autres valeurs SG donne exactement la nouvelle valeur SG après qu’on a effectué le coup. Alors la procédure est ce qui suit:
- Calculez les 4 valeurs SG, disons w,x,y,z des 4 quadrants d’iChomp (chacune égale à la valeur SG Chomp de ce quadrant plus 1).
- Calculez u où u = w XOR x XOR y XOR z.
- Si u=0, alors c’est une position perdante. Alors on enlève une seule tuile de n’importe quel quadrant pour retarder la perte et se donner plus de chances pour que l’adversaire joue un coup non optimal.
- Si u ≠ 0 alors
  - Trouvez une des valeurs w,x,y,z, disons y, qui satisfait y > y XOR u.
  - Dans le quadrant de valeur SG y, faites un coup qui crée un quadrant de valeur SG y XOR u.
Pourquoi ceci est-il un coup gagnant?
- Rappelez-vous des propriétés de XOR ci-dessus pour répondre aux questions suivantes.
  
  Si u = w XOR x XOR y XOR z, alors quel est y XOR u?
  - Suivant les règles ci-dessus on obtient
       y XOR u
    = y XOR w XOR x XOR y XOR z
    = y XOR y XOR w XOR x XOR z
    =        0     XOR w XOR x XOR z
    =            w XOR x XOR z.
  Si on remplace y par y XOR u alors quelle est la nouvelle somme XOR des 4 valeurs SG?
  - La nouvelle XOR sera
    (y XOR u) XOR w XOR x XOR z
    = (w XOR x XOR z) XOR (w XOR x XOR z)
    = 0
    car m XOR m = 0 pour tout nombre m.
    
    Alors la nouvelle valeur SG du plateau entier sera 0, ce qui sera une position perdante pour son adversaire.
  Pourquoi doit-il exister un coup qui change une valeur SG y en une valeur inférieure?
  - Selon la définition : Une position n’a une valeur SG de y que s’il existe des coups qui génèrent des positions de valeurs SG 0,1,..,(y-1). Alors, si y > (y XOR u), il doit exister un coup qui génère une valeur SG de (y XOR u) < y.
  Le trou qui reste à combler c’est:
  
  Pourquoi doit-il exister un quadrant y qui satisfait y > (y XOR u)?
  - Un petit rappel:
    Plus tôt, quand on a appris les propriétés de XOR, on a vu : XOR change tous les chiffres pour lesquels le chiffre correspondant est 1.
    
    Si u ≠ 0, alors u contient une puissance de 2 la plus haute, disons 2^p. Cette puissance de 2 doit figurer dans un nombre impair des 4 valeurs SG, donc dans au moins une des valeurs, disons y.
    
    Alors quand on calcule y XOR u, ce 1 dans y est changé en un 0 par le 1 correspondant dans u. Il peut y avoir d’autres chiffres binaires changés dans y à la droite de ce 1. La valeur la plus grande de y − (y XOR u) est obtenue lorsque tous les chiffres à droite de ce 1 dans y sont des zéros et quand tous les chiffres à la droite de ce 1 dans y sont des 1s. Dans ce cas u = 111..111 change y = *100..00 (où * représente tout nombre de chiffres) en y XOR u = *011..11. Leur différence égale:
    
    y − (y XOR u)
    = 2^p − (2^p−1 + 2^p−2+ ... +2⁰)
    = 2^p − (2^p−1 + 2^p−2+ ... +2⁰)× (2-1)/(2-1)
    = 2^p − (2^p−1)/(2-1)
    = 1.
    Alors y est supérieur à (y XOR u) par au moins 1. ∎
Essayez d’utiliser cet algorithme pour jouer et gagner contre la «Difficulté: Difficile».
- Pour commencer, sélectionnez ‘Difficulté : Difficile’ qui oblige l’ordinateur de jouer de manière optimale. Si vous gagnez, vos coups étaient tous optimaux.
  
  La valeur SG de chaque quadrant est affiché en base 10 et en base 2. Vérifiez que ce nombre est la plus petite valeur qui ne figure pas dans le quadrant.
  
  En-dessous est affichée la somme XOR des 4 valeurs SG. Vérifiez la valeur de u en changeant toute paire de 1s correspondantes dans les 4 valeurs SG en 0. Puis, écrivez un seul nombre binaire à partir des 1s restants et convertir ce nombre en base 10.
  
  Pour faire un coup, suivez les instructions ci-dessous:
  - Trouvez une des 4 valeurs SG, disons y, qui a un 1 dans la même position que le 1 le plus à gauche dans u.
  - Calculez y XOR u en binaire et convertissez-le en base 10.
  - Dans le quadrant y cliquez sur la tuile où figure y XOR u.
  - Répétez jusqu’à ce que vous avez gagné.
  - Rejouez, mais cette fois, commencez par un coup aléatoire. Sauf si la chance vous sourit et que vous avez fait le coup optimal par hasard, vous serez incapable de gagner cette partie même si vous ne faites ensuite que de coups optimaux.

Afin de calculer la valeur SG d’une position donnée, il faut connaître la valeur SG de toutes les positions auxquelles on peut accéder en un seul coup. Ce processus est récursif. Alors on doit commencer par les positions avec le moins de tuiles avant de passer sur des positions plus complexes.

Pouvez-vous déterminer les valeurs SG d’1,2,3 tuiles dans une rangée?
- Quand il y a 1 seule tuile (dans le coin supérieur gauche), c’est une position perdante dont la valeur SG égale donc 0.
  
  Quand il y a 2 tuiles (dans la rangée supérieure ou la première colonne), il n’y a qu’un coup possible qui est d’enlever une tuile pour obtenir la susdite position de valeur SG 0. Alors le plus petit nombre positif qu’on ne peut pas obtenir en un coup est 1, alors 1 est la valeur SG d’une position avec 2 tuiles.
  
  Quand il y a 3 tuiles dans la rangée supérieure, on peut enlever 1 ou 2 tuiles et obtenir des valeurs SG de 1 et 0, alors la valeur SG égale 2.
  
  Pareillement, la valeur SG de n tuiles dans la première rangée est n-1.
  
  Considérons une position à 3 tuiles, 2 dans la rangée supérieure et 2 dans la première colonne. On peut enlever 1 tuile et obtenir une valeur SG de 1 mais pas 0, alors la plus petite valeur SG qu’on ne peut pas obtenir est 0 qui est donc la valeur SG de cette position. La position est perdante.
Pouvez-vous déterminer la valeur SG d’une position avec m+n−1 tuiles où il y a n tuiles dans la rangée supérieure et m tuiles dans la première colonne?
- Il faut enlever des tuiles de soit la première colonne, soit la rangée supérieure. La valeur SG est donc la même que d’avoir deux quadrants, un de n tuiles dans la rangée supérieure, un de m tuiles dans la première colonne. Alors la valeur SG est (m-1) XOR (n-1). C’est exactement comme jouer au jeu de Nim avec deux tas en Version Normale où un coup ne peut enlever des allumettes que d’un seul tas.
Pouvez-vous déterminer la valeur SG d’une position avec des tuiles dans les deux premières rangées seulement?
- Les formules pour ces positions sont plus compliquées. Pour autant que l’on sache, c’est la première fois qu’elles sont publiées. Vous pourriez les vérifier pour un petit nombre de tuiles.
  
  Soient n et m le nombre de tuiles dans les première et deuxième rangées.
  
  Si n est pair alors
    k = (n-2)/2
    si m est pair alors
      a = m/2
      valeur SG = 2*k+a+1
    sinon (m est impair)
      a = (m-1)/2
      si a ≤ (k/2) alors valeur SG = 2*k-a
      sinon valeur SG = 3*(k-a)
  sinon (n est impair)
    k = (n-1)/2
    si m est pair alors
      a = m/2
      si a ≤ (k/2) alors valeur SG = 2*k-a
      sinon valeur SG = 3*(k-a)
    sinon (m est impair)
      a = (m-1)/2
      valeur SG = 2*k+a+1
  
  Utilisez le plateau de jeu ci-dessus pour vérifier ces formules.
  - Sélectionnez la longueur de plateau minimale pour qu’il y ait des quadrants avec deux rangées de tuiles seulement. Après avoir appliqué les formules ci-dessus vous devriez obtenir une valeur SG inférieure par 1 à la valeur affichée sous ‘Valeur SG Base Dix:’ puisque les formules sont pour la Version Misère alors qu’iChomp se joue en Version Normale.

On commence par une observation : Les règles de Chomp ne distinguent pas entre les directions Est et Sud.

Quelle est la conséquence sur les valeurs SG de deux positions qui sont symétriques l’une à l’autre par rapport à la diagonale qui commence par le coin supérieur gauche?
- Puisque les directions Est et Sud changent de place dans cette symétrie, les deux positions doivent avoir la même valeur SG.
Et quelle est la conséquence pour iChomp quand 2 quadrants ont des positions symétriques par rapport à une réflexion diagonale ou à une rotation?
- La conséquence est qu’on n’a pas besoin de considérer ces quadrants. Pourquoi? Les deux quadrants auront la même valeur SG en Version Misère et, après qu’on y a ajouté 1, la même valeur SG en Version Normale. La somme XOR de ces valeurs égales est zéro. Alors ces deux quadrants ne contribuent pas à la valeur SG de la position du plateau entier.
Quelle stratégie devrait donc marcher?
- On doit faire un coup pour créer deux paires de quadrants de sorte que les quadrants dans chaque paire aient des positions symétriques avec les mêmes valeurs SG, disons A et A, et B et B. Alors, la valeur SG de la combinaison des 4 quadrants est A XOR A XOR B XOR B = 0 XOR 0 = 0 ou (A XOR B) XOR (A XOR B) = 0 alors toujours 0. Ainsi crée-t-on une position perdante.
  
  Également, on ne devrait PAS faire un coup qui permet à l’adversaire de créer ces deux paires, c.-à-d. une paire symétrique et deux quadrants que l’adversaire pourrait changer en paire symétrique d’un coup. Ceci permettra à l’adversaire de créer une position perdante.

Tentez les questions suivantes pour mettre à l’épreuve votre compréhension de Chomp, iChomp, et le théorème de SG.

La connaissance des valeurs SG suffit-elle pour jouer à Chomp parfaitement?
- Tout à fait. Si la valeur SG d’une position est 0, elle est perdante (car aucun coup existe pour le changer en 0, donc il n’y a aucun coup gagnant possible, donc c’est une position perdante). Si la valeur SG est supérieure à 0, ça veut dire qu’il existe un coup qui crée une position d’une valeur SG de 0, ce qui sera un coup gagnant.
Est-il nécessaire de connaître les valeurs SG des positions Chomp pour jouer à Chomp parfaitement?
- Non. Pour jouer à Chomp il faut trouver un coup qui génère une position perdante. Si un tel coup n’existe pas c’est une position perdante alors on peut faire n’importe quel coup. Si par contre on identifie un tel coup, on peut arrêter de chercher. La valeur SG n’est pas nécessaire.
Alors à quoi servent les valeurs SG?
- On en a besoin uniquement pour jouer à plusieurs jeux de Chomp en parallèle, tel que dans iChomp.
Quelle est la différence de difficulté entre identifier un coup gagnant et calculer la valeur SG d’une position?
- Pour jouer à Chomp il faut trouver un coup qui génère une position perdante. Si un tel coup n’existe pas c’est une position perdante alors on peut faire n’importe quel coup. Si par contre on identifie un tel coup, on peut arrêter de chercher.
  
  D’habitude il faudra davantage d’effort pour déterminer la valeur SG d’une position. Pour trouver la valeur SG il faut considérer TOUS les coups pour trouver les valeurs SG des positions résultantes et ainsi identifier le plus petit nombre positif qu’on ne peut pas obtenir d’un seul coup. Cette valeur est la valeur SG de la position.
  
  Par exemple, dans nos (Caribou) calculs on a pu déterminer toutes les positions perdantes (et par conséquent toutes les positions gagnantes) jusqu’à 93 tuiles. Avec un effort de calcul comparable on a pu calculer la valeur SG de toutes les positions Chomp jusqu’à 82 tuiles.
  
  On peut donc considérer que la détermination des valeurs SG coûte plus cher en calcul que déterminer un coup gagnant.
Si le jeu de Nim est plus difficile avec 4 tas qu’avec 1 tas, alors iChomp, avec ses 4 quadrants, est-il beaucoup plus difficile que Chomp qui n’a qu’1 quadrant?
- Dans le jeu de Nim, la valeur SG d’un tas égale tout simplement le nombre d’allumettes dans le tas. (Confirmez-le en appliquant à un seul tas d’allumettes les instructions pour calculer la valeur SG). La seule complication qu’apportent plusieurs tas dans le jeu de Nim, c’est de devoir calculer la somme XOR des différentes valeurs SG de ces tas pour déterminer la valeur SG de la position entière.
  
  Dans Chomp, il coûte plus cher en effort pour calculer la valeur SG d’une position (qui n’est que dans un quadrant). Dans iChomp, lorsqu’on connaît la valeur SG des 4 quadrants, il faut obtenir leur somme XOR aussi, mais ceci est beaucoup plus facile que déterminer la valeur SG d’un quadrant.
  
  Pour jouer à Chomp il n’est pas nécessaire de connaître la valeur SG de la position. Il suffit de connaître un coup gagnant, mais comme on a montré ci-dessus la différence n’est pas si grande que ça.
  
  Alors la réponse est NON, il n’est pas beaucoup plus difficile de jouer à iChomp par rapport à Chomp.
Un coup dans Chomp peut-il créer une position avec une valeur SG plus grande?
- Oui. La valeur SG d’une position est la plus petite valeur qu’on ne peut pas générer en un coup.
Est-il possible que plusieurs coups dans Chomp puissent créer une position avec la même valeur SG?
- Oui. Vous pouvez en voir des exemples en agrandissant le plateau et en cliquant sur le bouton ‘Montrer les Valeurs SG des Coups’. Par exemple, pour la position
  
  ###
  ##
  #
  
  Il existe 3 coups gagnants, qui créeraient tous une valeur SG de 0. On a même trouvé une position avec 7 coups gagnants:
```
 + 10  6 15  2 20 21 14 22 11  0 23  7 26
13  7 11  9 14  0 19  5
17 11 14 18  0 24 23  8
 3 19  2  0 20
11  4  0  5  1
 8  0
 0
 4
23
25
24
```

Comment Jouer :

Comment Gagner :

C’est à votre tour, Joueur 1

	0110
XOR	1101
	------
	1011