Cgsuite, un logiciel pour construire le nombre avec des jeux combinatoires

samedi 18 mars 2017
par  Alain BUSSER

Plusieurs chapitres du livre « winning ways for your mathematical plays » (Berlekamp, Conway et Guy) sont consacrés à des jeux dits « partisans » où l’un des joueurs a un net avantage sur l’autre. Ces jeux sont a priori inintéressants puisque c’est tout le temps le même joueur qui gagne. Mais s’ils sont peu intéressants à jouer, il est par contre intéressant de les analyser, ne serait-ce que parce que cette analyse permet de modéliser la construction des nombres réels par coupure de Dedekind, et, au-delà, la notion de nombre surréel. La théorie des jeux combinatoires est complexe de par ses notations ésotériques et les calculs surprenants, mais aussi parce qu’elle voit apparaître des infinitésimaux qui ne sont pas du même ordre de grandeur et qui ne s’additionnent pas comme on s’y attendrait, et même des jeux qui ne sont pas des nombres. Le logiciel cgsuite (« combinatorial games suite ») étant capable de mener ces calculs surprenants et même d’explorer certains jeux (partisans ou non), aide à modéliser les nombres surréels, et à représenter par des jeux, les nombres entiers ou réels ou certains infinitésimaux.

Pour ceux qui veulent jouer

Avant de lire la suite, il est recommandé de faire quelques parties des jeux suivants (pour en démarrer un, cliquer droit sur la copie d’écran de CG suite ; on joue à deux joueurs sur une seule page web, en cliquant chacun son tour sur une des pièces tant qu’on peut) :

HTML - 23.6 ko

Dans ce jeu, celui qui joue en premier (les chevaux blancs ou les crapauds bleus) gagne ; ce que CG suite note par un « * ». On remarque que dans les jeux combinatoires, le but du jeu n’est pas d’arriver le premier au bout, mais de jouer le plus longtemps possible. Autrement dit, « gagner c’est jouer » (plus longtemps que l’adversaire).

HTML - 23.6 ko

La valeur du jeu est plus complexe que ci-dessus, ce n’est plus « * » mais un intervalle, entre -1/8 et 1/8. On remarque que dans les deux cas, ce n’est pas un nombre. Mais on verra des nombres ci-dessous, en particulier dans le jeu Konane.

HTML - 24.2 ko

Le jeu ci-dessus est une somme de jeux combinatoires, la ligne dessinée ci-dessus ayant elle aussi la valeur « * ». Il faut donc trouver comment on additionne des jeux qui ne sont pas des nombres.

Après avoir testé les jeux ci-dessus, on constate que pour certaines positions de départ, l’un des joueurs a un avantage sur l’autre, qu’il est logique de chercher à quantifier. Pour d’autres positions de départ, celui qui joue en premier est le gagnant, et ceci laisse l’impression que si certains jeux sont des nombres, d’autres ne le sont pas, et donc que la notion de jeu généralise celle de nombre.

Toads and frogs

La notation de Conway pour désigner un jeu est peu lisible parce qu’elle fait appel à des accolades, le jeu « gauche contre droite » (désignant un jeu où le premier joueur a les possibilités de jeu désignées par « gauche » et l’autre joueur a les possibilités désignées par « droite »), étant noté par Conway {gauche|droite}. En fait il s’agit de dessiner un arbre à plat, les sous-arbres de gauche et de droite étant eux aussi représentés avec des accolades, ainsi imbriquées. On utilisera dans cet article les phrases du type « gauche contre droite » plutôt que la notation de Conway.

Le jeu le plus simple du monde

Le jeu le plus simple à jouer est celui qu’on ne peut pas jouer du tout ! Par exemple, le jeu de Nim à un tas déjà vide (dont on ne peut donc rien retirer), le jeu ci-dessus où on a oublié de disposer les pions (chevaux, grenouilles ou crapauds) d’une couleur, le jeu de dames (ou de Konane, voir ci-dessous) où un joueur n’a plus de pion (ou, dans le cas de Konane, uniquement des pions isolés, donc injouables), etc. Ce jeu, noté { } par Conway, est donc le jeu vide.

Construction des entiers naturels

En dehors du jeu vide, le jeu le plus simple est celui dans lequel chaque joueur n’a que le jeu vide comme option de jeu, comme celui où ni la grenouille, ni le crapaud, ne peuvent bouger :

Ce jeu est noté { | } = 0 par Conway, on a donc l’équation définitionnelle vide contre vide égal zéro.

Le nombre 0 à lui seul ne permet pas de définir d’autres nombres (parce que « zéro contre zéro » n’est pas un nombre, voir plus bas) mais à l’aide de 0 et du vide on peut définir d’autres nombres, tout d’abord vide contre zéro égal -1 et 0 contre vide égal 1. Ce nombre est illustré ci-dessous par le fait que, alors que la grenouille est face au jeu vide (elle est déjà au bout), le crapaud peut encore jouer un tour et arriver à son tour au jeu vide, soit { 0 | } = 1 :

Ensuite, on peut continuer à construire les entiers naturels avec l’équation n contre le vide égal n+1 : D’abord 2 = {1 | } :

Puis 3, qui est deux contre le vide :

Puis 4, etc :

Bien entendu on aurait pu inverser les rôles de la grenouille et du crapaud, et ainsi, construire les nombres entiers négatifs :

Et, en jouant à ce genre de jeu sur deux lignes, on réalise l’addition des nombres ainsi représentés. Par exemple si on a sur la première ligne un jeu de valeur 4 comme celui ci-dessus, et sur la seconde ligne un jeu de valeur 2, le tout est un jeu de valeur 4+2=6.

L’addition permet de définir, à partir des entiers, d’autres entiers (voir plus bas la version Konane, plus simple à mettre en œuvre), par somme ou différence (à l’aide des entiers négatifs), mais elle ne permet pas de définir d’autres nombres que les entiers. On a donc besoin, pour construire d’autres nombres, de faire des choses plus complexes comme 0 contre 1 (qui vaut 1/2) ou 1 contre 0 (qui n’est pas un nombre). Mais d’abord il est temps de découvrir le plus simple des jeux qui ne sont pas des nombres :

Une étoile est née

Ce titre est de Conway, en effet ce jeu est très important, et Conway lui a donné une notation simple, sous la forme d’un astérisque. Il s’agit de 0 contre 0 noté {0|0} = *. Ce jeu non numérique est représenté par exemple, par le premier des jeux en ligne qui ouvrent cet article :

HTML - 23.6 ko

Mais la démonstration du fait que les deux options de ce jeu sont toutes deux égales à 0 est compliquée, et fait appel à des jeux qui sont beaucoup plus complexes à évaluer que des nombres [1]. Par contre, en entrant, dans CG suite, l’expression {0|0} le logiciel calcule automatiquement sa forme la plus simple et c’est *. Ce jeu n’est pas un nombre mais un nimber : C’est le jeu de Nim à un tas d’une seule pièce : Le premier joueur qui joue retire la pièce et gagne. Remarque de Conway à ce propos :

  • Si le premier qui joue gagne, le jeu est *
  • Mais si au contraire c’est le second joueur qui gagne, le jeu est 0

Ces deux jeux sont donc d’une certaine manière plus équitables que le jeu 4 par exemple : Ils sont plus petits que la plupart des jeux que l’on verra ci-dessous (en particulier, ils sont plus petits que tous les nombres strictement positifs).

La place de l’étoile

On rappelle que 0 contre 0 égal * ; ensuite, 0 contre 1 égal 1/2 :

Ceci permet de définir les nombres dyadiques avec 0 contre 1/2 égal 1/4 et ainsi de suite : Les jeux inférieurs à tous les jeux du type 1/n où n est une puissance de 2 (et en même temps supérieurs à leurs opposés), sont dits infinitésimaux. On peut déjà affirmer que

L’étoile est un infinitésimal

La question qui se pose maintenant est de savoir s’il y en a d’autres, en particulier s’il y a des nombres infinitésimaux. Avant de répondre à cette question, l’étoile permet déjà de construire des infinitésimaux non numériques :

Les descendants de l’étoile

En calculant des jeux du type 3 contre 3 le logiciel CG suite répond 3* qui est à interpréter comme la somme de 3 et de l’étoile : On retrouve là un phénomène typique de l’analyse non standard où tout réel fini est la somme de sa partie standard et d’un infinitésimal. D’ailleurs, comme en analyse non standard, Conway utilise le mot « halo » pour désigner les nombres infiniment proches d’un entier (par exemple) et l’étude de l’ensemble de tous les jeux finis se ramène, par addition ou soustraction, à celle du halo de 0 qui est formé des jeux infinitésimaux.

Tout d’abord il y a les nimbers, notés * pour un jeu de Nim d’une seule pièce, *2 pour le jeu de Nim à deux pièces, *3 pour le jeu de Nim à 3 pièces, etc (chaque fois, les pièces sont mises en un seul tas donc le premier joueur qui joue a l’option de vider le tas et de gagner d’un coup). L’ensemble des nimbers est muni d’une nim-addition et d’une nim-multiplication lui donnant une structure de corps de caractéristique 2 [2] qui est une extension de tous les corps finis de caractéristique 2 [3].

Le prochain infinitésimal remarquable est appelé « up » par Conway, et noté ↑ (son opposé * contre 0 est noté ↓ et appelé « down » évidemment). Il est défini par 0 contre * égal « up » ou {0|*} = ↑ :

Dans CG suite, pour entrer « up » ou « down », on utilise les touches suivantes du clavier : ^ et v. Cela permet de vérifier que ces infinitésimaux sont opposés l’un à l’autre parce que ↑+↓ donne 0, mais aussi que {↑|↓}=* : up contre down égal * (ainsi d’ailleurs que * contre *). Mais aussi, en additionnant « up » avec lui -même un certain nombre de fois, on a de nouveaux infinitésimaux notés ↑2, ↑3, ↑4 etc. Avec une notation pour le cas particulier de ↑2 (« double up ») noté également ⇑.

On a donc une infinité d’infinitésimaux entre les nimbers : les ups et les downs. On verra plus bas comment les comparer entrer eux et avec les nombres. Mais on peut déja donner ce résultat guère surprenant :

« up » est strictement positif et « down » est strictement négatif. L’étoile n’est ni positive ni négative

Konane

Ce jeu est intéressant non seulement du point de vue mathématique mais aussi du point de vue ethnologique : Considéré comme le jeu national de l’archipel d’Hawai’i [4], il date de plusieurs siècles et se joue sur la plage avec des pierres claires et foncées. Le plateau de jeu est un damier de forme rectangulaire (ici un carré 4×4), recouvert de pions noirs et blancs disposés comme ceci :

Ensuite chacun son tour, les joueurs prennent les pions de l’adversaire en sautant par-dessus, soit horizontalement, soit verticalement [5]. La valeur de ce jeu est pour l’instant nulle puisqu’aucun des joueurs ne peut jouer (il manque de la place pour sauter par-dessus un pion de la couleur opposée, on ne peut pas atterrir « derrière »). Aussi, pour que le jeu soit tout simplement jouable, on enlève, avant le début de la partie, deux pions adjacents, un de chaque couleur, et on arrive à quelque chose comme ça :

Ensuite, chaque joueur lorsque c’est son tour, choisit un de ses pions, et le fait sauter par-dessus un pion de l’adversaire, horizontalement ou verticalement, à condition que la case suivant le saut soit vide (on doit pouvoir atterrir après le saut). Le premier joueur ne pouvant plus bouger (parce qu’aucun de ses pions n’est adjacent à un pion adverse prolongé par une case vide) perd.

Exemple de partie

L’analyse du jeu ci-dessus est possible avec CG suite par le dessin de l’arbre du jeu, suivi de l’attribution d’une valeur à chaque embranchement. Traditionnellement ce sont les noirs qui commencent. Or il n’y a qu’une case vide bordée de pions blancs, et un seul pion noir peut y accéder en sautant par-dessus un pion blanc, ce qui fait passer de ça

à ça :

Les blancs, qui jouent maintenant, ont deux choix, consistant à prendre le pion noir qui vient de jouer : Ils le prennent verticalement ou horizontalement, par exemple verticalement :

Ensuite, les noirs n’ont plus que le choix de jouer le pion en haut à gauche :

Les blancs non plus n’ont guère le choix :

Les noirs non plus, du coup :

Maintenant les blancs ont le choix entre trois coups possibles ; disons qu’ils choisissent celui-ci :

Alors les noirs n’ont à nouveau le choix :

Les blancs peuvent choisir ce coup :

L’un des pions noirs ne peut plus jouer maintenant parce qu’il n’y a pas de pion blanc par-dessus lequel sauter. Mais les deux autres non plus parce que même s’il y a un pion blanc voisin d’eux, il n’a pas de place (à moins de sortir du plateau de jeu) pour atterrir derrière. Les noirs ne peuvent plus jouer. Les blancs, si, si c’était leur tour : Ils pourraient prendre un pion noir en sautant par-dessus. La valeur du jeu est donc -1 pour les noirs (à savoir vide contre 0). Mais l’étape précédente n’était déjà plus jouable pour les noirs, si ça avait été leur tour. Pour eux elle vaut donc vide contre -1 = -2, comme le dit CG suite en bas de la copie d’écran. En remontant ainsi les calculs, on trouve que le jeu initial était 0, ce qui signifie que celui qui joue en second, qu’il soit noir ou blanc, a une stratégie gagnante.

Le jeu vide, décrit ci-dessus, apparaît non seulement sur un plateau de Konane vide, mais aussi sur un plateau dont tous les pions, noirs ou blancs, sont isolés. Par exemple quel que soit le joueur qui hérite de cette situation, il ne peut jouer (les blancs parce qu’ils n’ont plus de pion à jouer, les noirs parce que leur unique pion ne peut jouer, faute de pion blanc par-dessus lequel sauter) :

La valeur de ce jeu est donc vide contre vide = 0

Entiers naturels dans Konane

Dans ce jeu, les blancs ne peuvent déjà plus jouer (ils ont déjà affaire au jeu vide) ; mais les noirs peuvent prendre le pion blanc, ce qui les amène à un jeu similaire au précédent (un seul pion noir, donc injouable). Ce jeu est donc 0 contre vide égal 1 :

Dans ce jeu, si les noirs prennent le pion blanc à droite, ils arrivent à une situation similaire au jeu précédent (le pion noir à droite étant isolé du reste du jeu, ne compte plus) :

Ce jeu est donc 1 contre vide = 2. De même, on peut représenter en Konane le nombre 3 :

Et ainsi de suite, on peut représenter tous les entiers en Konane, même en se limitant à une dimension.

Comme on ne peut jouer qu’en sautant par-dessus un pion de l’autre couleur, il suffit de jouer avec une ligne sur deux vide, pour représenter dans Konane la somme de jeux ; ici, on n’a même pas besoin que la ligne 2 soit vide puisque la ligne 3 n’existant pas, on ne peut pas y atterrir :

La ligne 1 est le nombre 2, et la ligne 2 est le nombre 1, ce jeu illustre donc que 2+1=3 : Konane permet donc de représenter non seulement les entiers naturels, mais aussi leur addition.

Entiers négatifs avec Konane

Il suffit d’inverser les rôles des noirs et des blancs pour représenter les nombres négatifs avec Konane. Mais ce jeu aussi vaut -1 :

En effet les noirs ne peuvent pas jouer mais les blancs peuvent prendre un pion noir pour aboutir au jeu nul (quel que soit le joueur qui va jouer, il ne peut pas parce que ses pions sont isolés). On a donc l’égalité vide contre 0 égal -1. De même le nombre vide contre -1 = -2 :

Tout entier négatif peut être représenté par un jeu de Konane sur une seule ligne.

En mettant un entier naturel sur une ligne et l’opposé d’un autre entier naturel sur une seconde ligne, on peut utiliser Konane pour effectuer des soustractions. Par exemple la soustraction 5-3 :

On peut aussi effectuer des soustractions comme 2-5 mais tant qu’on n’a que des entiers à additionner ou soustraire, on ne construit, par ces additions ou soustractions, que des entiers. Mais d’autres nombres existent, que les entiers.

Fractions en Konane

On rappelle que ce jeu de Konane est un nombre et que ce nombre est 1 :

En effet, les blancs qui sont bloqués ont face à eux le jeu vide, alors que les noirs peuvent prendre le pion blanc pour arriver à leur tour au jeu nul : 0 contre vide égal 1.

Du coup dans le jeu ci-dessous, si c’était aux blancs de jouer, ils arriveraient au jeu 1, alors que les noirs, s’ils jouent, arrivent au jeu 0 : Ce nouveau nombre est 0 contre 1, en fait égal à 0,5 :

En additionnant 0,5 avec 3 par exemple, on peut construire 3,5 et plus généralement, tout demi-entier est constructible avec Konane. Mais on peut recommencer avec 0 contre 1/2 :

Et ainsi de suite :

Toute fraction est donc représentable dans Konane, du moment que son dénominateur est une puissance de 2. Les autres nombres sont aussi représentables en Konane, mais sur un plateau infini. Par exemple 1/3 = 1/4 + 1/16 + 1/64 + .... Mais si on admet (ne serait-ce que pour pouvoir représenter tous les nombres) de jouer sur un plateau de jeu infini [6], on peut aussi construire, sur un tel plateau, des entiers infinis (sur le modèle vu ci-dessus avec les entiers finis) ce qui a conduit Conway à redéfinir la notion de nombre ordinal en représentant les ordinaux par des jeux. Il semble même que ce soit à l’origine de l’intérêt de Conway pour les jeux combinatoires.

Mais à l’inverse, un plateau de Konane de taille infinie permet aussi de représenter des nombres du type ci-dessus (1/2, 1/4, 1/8 etc) avec un dénominateur infini et qui ont la propriété suivante : Le nombre est strictement positif mais strictement inférieur à 1/2, à 1/4, à 1/8 etc. On appelle ce genre de nombre un nombre infinitésimal positif. La seconde partie du livre on numbers and games a essentiellement pour but d’examiner la structure des infinitésimaux (nombres ou pas) et la façon dont ils sont agencés sur (ou à côté de) l’axe des réels.

Un exemple simple d’infinitésimal (mais ce n’est pas un nombre) est l’étoile de Conway :

Ce jeu est fondamental dans la théorie de Conway, parce que ce n’est pas un nombre ; quel que soit le joueur qui va jouer, il va prendre l’unique pion de son adversaire et arriver à la position 0 ; ce jeu est donc 0 contre 0 égal * :

De l’étoile aux étoiles

En additionnant l’étoile avec un nombre on construit un nouveau jeu, par exemple le jeu 2* est la somme du jeu 2 et de l’étoile :

Le jeu ci-dessous a aussi pour valeur l’étoile : Si les noirs jouent, ils prennent l’unique pion blanc et arrivent au jeu nul (le premier qui joue a perdu), mais si ce sont aux blancs de jouer, ils arrivent aussi au jeu nul, en prenant un des deux pions noirs. Le jeu est donc 0 contre 0 égal * :

Par contre ce jeu est nul, les pions noirs et blanc étant isolés donc injouables :

Mais ces deux jeux sont ceux qu’on peut obtenir à partir de celui ci-dessous, si ce sont les noirs qui jouent :

Selon le cas les noirs arrivent à l’étoile ou au jeu nul ; mais les blancs, si c’est à eux de jouer, arrivent à l’étoile aussi. La valeur de ce jeu est donc 0 ou * contre * notée {0,* | *} = *2. On peut dire que c’est une double étoile mais comme *+*=0 (l’étoile est son propre opposé) on ne peut pas vraiment la définir comme le produit de 2 par l’étoile.

Un algorithme permet de construire les *n par récurrence. Or *4 est par exemple le jeu de Nim à un tas de taille 4, et comme on sait aussi additionner les jeux de Konane si on a suffisamment de place (on les écarte l’un de l’autre), on peut simuler avec Konane tout jeu de Nim :

Konane est une généralisation du jeu de Nim (ou de Marienbad)

Depuis l’étoile, vers le haut

La valeur de ce jeu est donnée par CG suite comme étant la somme de l’étoile et d’un autre jeu appelé « up » (noté ↑ ; on remarque que le signe « + » est superflu dans la notation de Conway) :

Par conséquent, si on lui additionne l’étoile (qui est son propre opposé) on obtient le jeu « up » :

Et comme on l’a vu dans la partie sur Toads and Frogs, il est possible d’additionner autant de copies d’« up » que l’on souhaite et ainsi construire une infinité d’infinitésimaux positifs. Voici un dessin extrait de winning ways for your mathematical plays illustrant la situation ; on y voit les fractions 1/16, 1/32 etc et leurs opposés, et la partie centrale est zoomée avec un rapport infini pour voir les multiples d’up et down :

Le nuage est une partie du halo de 0, et contient, en zoomant encore une fois, d’autres infinitésimaux d’ordre supérieur (les puissances d’up et leurs multiples entiers), et encore, et encore, et encore...

Et au milieu, même en zoomant une infinité de fois d’un rapport infini, il reste encore les nimbers comme l’étoile, qui ne sont ni positifs, ni négatifs, ni nuls : Comme dirait l’étoile,

I am not a number, I am a nimber

Entre les dames et Konane

Voici jeu très récent, dont on ne connaît donc pas encore de stratégie gagnante (ni s’il y en a une). Sa créatrice [7] a tenu à rajouter une régle qui, non seulement complique le jeu, mais semble donner un trop net avantage à celui qui joue en premier (les blancs ci-dessous). En tout état de cause voici cette règle :

Lorsqu’un joueur a trois de ses pions alignés, cela s’appelle « un échec de trois pions » ; dans ce cas, le joueur en question doit jouer trois fois de suite.

Pour les raisons évoquées ci-dessus, cette règle complexe n’a pas été gardée. Voici les autres règles :

  • Chaque joueur, à son tour, avance un de ses pions, en diagonale (comme aux dames), d’une seule case ; mais on peut reculer.
  • Si un pion adverse est voisin d’un pion à soi, et que le symétrique de ce pion par rapport au pion adverse est une case vide, on peut prendre le pion adverse en sautant par-dessus lui (comme à Konane) ; la prise s’effectuant horizontalement ou verticalement, on constate que les pions blancs restent toujours sur des cases blanches, et les pions noirs, sur des cases noires.
  • Le but du jeu est de prendre tous les pions de l’adversaire.

Voici le jeu en question (cliquer sur l’image pour ouvrir le jeu dans un autre onglet du navigateur) :

HTML - 4.8 ko
Un jeu réunionnais à la Konane
Existe-t-il une stratégie gagnante à ce jeu ?

Les fins de partie de ce jeu évoquent fortement tiouk tiouk. La possibilité de reculer fait qu’il peut y avoir des parties infinies ; dans ce cas la tradition est de considérer la partie comme nulle dès qu’on revoit 3 fois de suite la même position de jeu.

Simple mancala

Mancala est le nom commercialisé dès le milieu du XXe siècle, par un certain Wliilam Julius Champion, et qui diffère d’awalé par les caractéristiques suivantes :

  • chaque joueur dispose d’une case supplémentaire appelée son kalah (grenier) dans laquelle les deux joueurs sèment ;
  • mais on ne sème jamais les graines depuis le kalah, et on n’y prend pas de graines non plus : Les graines peuvent être mises en sécurité dans le kalah, en plus des coups du jeu classique d’awalé ;
  • lorsqu’un joueur a placé la dernière graine de son semis dans son kalah, il rejoue.

Ci-dessous, le joueur qui a les graines du bas, a son kalah à sa droite, et sème de gauche à droite :

Avec le jeu ci-dessus, si le joueur du bas décide de semer les deux graines de sa dernière case, il en place une dans le kalah et l’autre dans la case de tout à droite de son adversaire (pour l’adversaire cette case est tout à gauche). Si par contre il décide de semer le contenu de l’avant-dernière case, il place une des deux graines dans la dernière case et l’autre dans son kalah, ce qui l’autorise à rejouer : Essayer de placer un maximum de graines dans son kalah est une bonne stratégie à ce jeu, et la version à un joueur (où le kalah est renommé rouma) est un bon entraînement à Mancala. Mais ce mot désigne aussi les jeux de semailles en général.

Simple Mancala

Le jeu dit simple mancala, fourni avec CG-suite, diffère à son tour de Mancala, par les points suivants :

  • normalement, lorsqu’on place la dernière graine dans une de ses cases autre que son kalah, on la récolte ainsi que celles de l’adversaire qui sont en face, et on stocke le tout dans son kalah ; ce n’est pas le cas là...
  • normalement, on sème en passant par son propre kalah mais pas par celui de l’adversaire ; la version « simple » laisse semer dans tous les trous, y compris les deux kalahs ;
  • le simple mancala est si simple qu’on ne rejoue pas si on sème sa dernière graine dans son kalah ;
  • le simple macala est un jeu combinatoire, et le but du jeu n’est pas tant de récolter un maximum de graines, que d’être en position de jouer le plus longtemps possible ;
  • enfin, et cela semble être un bug, la direction dans laquelle on sème n’est pas la même pour les deux joueurs.

En fait, pour représenter un tel jeu dans CG-suite, on se contentera de donner deux tableaux respectivement pour le joueur du bas (« Left ») et celui du haut « Right »). Par exemple ce jeu

s’entre par

g := game.sowing.BasicMancala([0,1,4,3],[2,0,3,3])

Ensuite on entre

g.LeftOptions

pour savoir quelles sont les positions que peut atteindre (en un coup de jeu) le joueur du bas, et

g.RightOptions

pour savoir les positions que peut atteindre le joueur du haut.

g.CanonicalForm

permet de savoir si le jeu est un nombre, et le cas échéant, lequel.

Comme précédemment, le jeu sans graines à semer vaut 0, comme le montre ce programme en CG-suite :

game.sowing.BasicMancala([0,0,0,0],[0,0,0,0]).CanonicalForm

qui donne 0, alors que

game.sowing.BasicMancala([0,0,0,1],[0,0,0,0]).CanonicalForm

donne 1 : Le joueur du bas peut encore jouer un coup, en semant la graine dans son kalah.

Mais du coup ce jeu représente le nombre 2 :

En effet, en jouant un coup, le joueur du bas arrive à la position précédente où il lui reste encore un coup à jouer.

Par récurrence, ce jeu vaut 3 :

et celui-là, 4 :

Les symétriques de ces jeux par rapport à un axe horizontal ont pour valeur des nombres entiers négatifs puisqu’ils reviennent à échanger les rôles des joueurs. Du coup, on peut représenter des soustractions comme 4 moins 2 :

Mais aussi des additions comme 4+3, qu’on représente avec une graine dans le trou numéro 4 et une autre dans le trou numéro 3 :

Il faut bien 3 tours de jeu pour amener la graine de droite dans le kalah, et 4 tours pour amener celle de gauche dans le kalah. Mais si on commence par mettre la graine du trou 4 dans le trou 3, on obtient ceci :

Et là il faut 4 coups maximum pour amener les deux graines dans le kalah. Or la valeur d’un jeu entier est le plus grand nombre de mouvements que peut encore faire le joueur du bas : Le but est de jouer le plus longtemps possible.

Cette représentation des nombres entiers n’est pas vraiment originale : On met une graine dans le trou d’abscisse n pour que le jeu obtenu représente le nombre n ; on a alors ces abscisses :

-4 -3 -2 -1
4 3 2 1

On peut aussi résoudre des jeux en solitaire avec CG-suite ;par exemple combien faut-il de mouvements pour amener toutes ces graines dans le kalah ?

CG suite permet de répondre en entrant

game.sowing.BasicMancala([4,3,2,1],[]).CanonicalForm

Mais les entiers ne sont pas les seuls nombres représentables avec simple Mancala ; par exemple voici le nombre 1/2 :

et le nombre 3/2 :

Et la star absolue, l’étoile, est présente aussi :

Un peu de code source

Pour dessiner les plateaux de jeux de mancala, c’est alcoffeethmique qui a été utilisé. Voici un exemple de dessin de plateau de Mancala à 6 trous par joueurs (les kalahs ne sont pas dessinés) :

Les cases du haut sont dessinées par une fonction dessineD, qui place n graines dans le trou numéro p :

dessineD = (p,n) ->
    dessineCercle 120+80*p, 80, 32, 'brown'
    si n==1
        dessineCercle 120+80*p,80,8,'blue'
    si n>1
        r=16
        pour k dans [0...n]
            t=360/n*k
            rc=r*cosinus t
            rs=r*sinus t
            dessineCercle 120+80*p+rc, 80+rs,8,'blue'

Les cases du bas sont dessinées de manière similaire :

dessineG = (p,n) ->
    dessineCercle 120+80*p, 160, 32, 'brown'
    si n==1
        dessineCercle 120+80*p,160,8,'blue'
    si n>1
        r=16
        pour k dans [0...n]
            t=360/n*k
            rc=r*cosinus t
            rs=r*sinus t
            dessineCercle 120+80*p+rc, 160+rs,8,'blue'

Les rangées de cases sont dessinées à partir d’un tableau t de nombres entiers (les graines dans les cases, la syntaxe est la même que dans CG-suite) :

G = (t) -> dessineG x,t[x] pour x dans [0...t.length]
D = (t) -> dessineD x,t[x] pour x dans [0...t.length]

Le plateau ci-dessous a été obtenu avec ce script :

effaceDessin()
D [1..6]
G ((leCarréDe n) % 7 pour n dans [0..5])


[1Pour vérifier cela avec CG suite, on entre les deux commandes suivantes, destinées à définir puis dessiner le jeu :

g := game.strip.ToadsAndFrogs("tt..ff");
ex:=Explorer(g);

Ensuite on choisit, dans le dessin de droite, l’option « expand sensible games », puis on essaye les différentes positions du jeu, en cliquant sur « add » à chaque fois : Ceci dessine l’arbre du jeu et à chaque fois, les valeurs peuvent être affichées avec selection.CanonicalForm. En cliquant sur un embranchement dans l’arbre, la position de jeu se dessine automatiquement.

[2Au départ, Conway parle de définir sur N une structure de corps, avec l’isomorphisme associant 0 à lui-même, 1 à l’étoile, et n à *n

[3c’est-à-dire qu’elle contient comme sous-corps, tous les corps finis de caractéristique 2

[4on le pense descendant d’alquerque, à l’instar du jeu de dames ; mais pour passer d’alquerque aux dames, on a enlevé les lignes horizontales et verticales, ne permettant que les prises en diagonales ; dans Konane au contraire, ce sont les diagonales qu’on a enlevées. Par ailleurs Konane est plus proche de Nim que les dames puisqu’au contraire des dames, le but du jeu n’est pas de prendre tous les points de l’adversaire mais de continuer à jouer le plus longtemps possible : Le premier joueur qui ne peut plus bouger a perdu, indépendamment du nombre de pions qu’il lui reste...

[5ce qui fait appeler Konane « le jeu de solitaire à 2 » et lui donne un intérêt épistémologique supplémentaire : Le jeu du solitaire a été abondamment étudié non seulement par Conway et al, mais avant eux, par Édouard Lucas

[6Le fait que la taille du plateau soit un paramètre permet de consisdérer la longueur de la recherche d’une stratégie gagnante, fonction de la taille du plateau : celle-ci est fonction exponentielle de la taille du plateau, ce qui amène à se demander si la recherche d’une stratégie gagnante ne serait pas un problème NP-complet, voire de gagner le million de dollars de la fondation Clay ; pour l’instant on a prouvé que ce problème est P-SPACE complet, en simulant n’importe quelle fonction calculable par un jeu de Konane.

[7déjà auteure de ce jeu qui a eu un certain succès à la fête de la science


Commentaires

Annonces

Prochains rendez-vous de l’IREM

Séminaire EDIM-IREM

- Mercredi 12 avril 2017, 14h-18h, campus du Tampon, amphi 120C
- Mercredi 3 mai 2017, 14h-18h, PTU, Saint-Denis, salle S23.6
- Mardi 13 juin 2017, 14h-18h, campus du Tampon
- Mercredi 14 juin 2017, 14h-18h, PTU, Saint-Denis, salle S23.6


Brèves

À travers les labyrinthes : algorithmes et fourmis

dimanche 1er septembre 2013

Quand les chercheurs mettent au point des modèles d’optimisation et de recherche de plus court chemin qui s’inspirent du comportement de masse de colonies de fourmis...
À écouter : Sur les Épaules de Darwin, émission diffusée sur France Inter samedi 31 août 2013.

Rencontres Mondiales du Logiciel Libre à St-Joseph

mardi 20 août 2013

Les RMLLd se dérouleront pour la 2e fois à Saint-Joseph du 22 au 25 août.
C’est une opportunité pour les élèves qui suivent la spécialité ISN et les passionnés d’informatique.

Voici pour le samedi et le dimanche quelques interventions choisies :
- http://2013.d.rmll.info/Raspberry-votre-ordinateur-au-format-carte-de-credit?lang=fr
- http://2013.d.rmll.info/Materiel-libre-et-DIY?lang=fr
- http://2013.d.rmll.info/Arduino-de-l-electronique-libre?lang=fr

Noter aussi les conférences Art et Culture du dimanche, ainsi qu’une conférence plus engagée.

Le programme complet se trouve ici. Une radio sera ouverte pour l’occasion.
Des plaquettes à distribuer se trouvent ici.

Hyper-vidéos pour l’algorithmique au lycée

dimanche 19 août 2012

Olivier Roizès, à la demande de l’ADIREM, a réalisé une collection d’hyper-vidéos de présentation de logiciels et environnements de programmation. Ces hyper-vidéos, c’est-à-dire des vidéos contenant des éléments clicables, devraient être utiles aux enseignants désireux de se familiariser avec Python, CaRMetal, R, Rurple, Scilab ou Xcas.

Ouverture du SILO

mardi 1er novembre 2011

Le SILO (Science Informatique au Lycée : Oui !) est un espace collaboratif documentaire de partage et de formation collégiale, à destination des professeurs appelés à enseigner l’informatique au lycée.

Une initiative du CNDP, de l’INRIA et de Pasc@line, à laquelle se sont associés SPECIF, fuscia, EPI et ePrep.

Sur le Web : Site du SILO

Introduction à la science informatique

lundi 12 septembre 2011

Le CRDP de Paris publie le premier ouvrage destiné aux professeurs chargés d’enseigner la nouvelle spécialité « Informatique et sciences du numérique » en Terminale S à la rentrée 2012. Cet ouvrage a été coordonné par Gilles Dowek, directeur de recherche à l’INRIA.

Sur la création de la spécialité ISN, on pourra également consulter l’interview donnée au Café pédagogique par l’inspecteur général Robert Cabanne.

Sur le Web : CRDP de Paris

Deux publications sur l’algorithmique

samedi 17 octobre 2009

L’IREM d’Aix-Marseille publie une brochure de 73 pages, téléchargeable librement, intitulée Algorithmes et logique au lycée. Ces notions sont illustrées et déclinées sur des exercices du programme de spécialité mathématique en série L, mais sont adaptables aux programmes à venir.

Le hors série thématique n° 37 du magazine Tangente, disponible actuellement en kiosque, s’intitule « Les algorithmes. Au cœur du raisonnement structuré ». Extrait de l’éditorial : « La rédaction de Tangente a conçu la quasi-totalité de ce hors série thématique pour qu’il puisse être lu par des élèves de Seconde ».

Une carte mentale pour l’algorithmique

jeudi 10 septembre 2009

Sur son site, Jean-Jacques Dhénin a publié une carte mentale géante qui renvoie vers plus de 30 documents en ligne sur l’algorithmique. Tout ce qu’il faut — et même davantage — pour faire face au nouveau programme de Seconde !

Un catalogue libre d’algorithmes pour le lycée

dimanche 30 août 2009

Guillaume Connan, de l’IREM de Nantes, publie un catalogue libre de 119 pages d’algorithmes pour le lycée. Sur son site très riche, on trouvera d’autres documents en rapport avec l’algorithmique, notamment sur l’utilisation des langages fonctionnels au lycée et sur la comparaison programmation fonctionnelle/programmation impérative.

L’algorithmique à l’IREM de Lille

vendredi 26 juin 2009

Le groupe AMECMI de l’IREM de Lille vient de mettre en ligne des ressources importantes au service des professeurs de Seconde :

- Algorithmique et programmation (Emmanuel Ostenne)
- Bibliographie amoureuse de l’algorithmique (Alain Juhel)

Statistiques

Dernière mise à jour

jeudi 27 avril 2017

Publication

739 Articles
Aucun album photo
130 Brèves
11 Sites Web
126 Auteurs

Visites

374 aujourd'hui
1189 hier
1993924 depuis le début
24 visiteurs actuellement connectés