Wikipédia

Winning Ways for your Mathematical Plays

livre d'Elwyn Berlekamp

Winning Ways for your Mathematical Plays (Academic Press, 1982) est un livre écrit par Elwyn Berlekamp, John Conway, et Richard Guy, qui rassemble l'ensemble de leurs résultats sur les jeux mathématiques. Avec On Numbers and Games, ce livre est considéré comme fondateur de la théorie des jeux combinatoires.

Publié initialement en 1982 en 2 volumes, il a été réédité ensuite de 2001 à 2004 en 4 volumes. La description ci-dessous correspond à la seconde édition.

Premier volume

modifier

Le premier volume, composé de 8 chapitres, introduit la théorie des jeux combinatoires, dont notamment les jeux partisans, les jeux impartiaux, le théorème de Sprague-Grundy :

  • Whose Game? décrit en guise d'introduction le jeu d'Hackenbush, qui sert d'exemple tout au long du livre, et donne les premiers exemples de jeux partisans dont la valeur est un nombre entier ou rationnel.
  • Finding the Correct Number is Simplicity Itself développe la théorie des jeux partisans, en définissant notamment les classes d'outcome, un ordre partiel sur les jeux, la somme de jeux et l'opposé d'un jeu. Ce chapitre explique aussi comment obtenir la valeur numérique d'un jeu (si celui-ci est un nombre), et donne les premiers exemples de jeux qui ne sont pas des nombres : *, x* et les nimbers *n.
  • Some Harder Games and How to Make Them Easier décrit les simplifications possibles dans les jeux, en revenant sur le théorème de Sprague-Grundy pour les jeux impartiaux, puis généralise aux jeux partisans avec les notions de coups réversibles et d'options dominées. Les valeurs ↑ (haut) et ↓ (bas) font leur apparition.
  • Taking and Breaking traite des jeux composés de tas d'objets, principalement les jeux octaux et le jeu de Grundy.
  • Numbers, Nimbers and Numberless Wonders introduit les jeux chauds, comme les switch, et la notion de température d'un jeu. De nombreuses valeurs du jeu de Domineering (en) sont données en fin de chapitre.
  • The Heat of Battle décrit des outils pour analyser la valeur d'un jeu G complexe, dont le jeu refroidi par une valeur t, et le jeu réchauffé par une valeur t.
  • Hackenbush revient en détail sur le jeu d'Hackenbush.
  • It's a small small small small world étudie le cas des jeux infinitésimaux, et introduit des notions comme le poids atomique (atomic weight) d'un jeu ou l'étoile lointaine (remote star).

Deuxième volume

modifier

Le deuxième volume, composé de 5 chapitres, étudie la théorie des jeux dont l'une des règles ne correspond plus exactement aux règles de référence du premier volume.

  • If you Can't Beat 'Em, Join 'Em est un très court chapitre qui traite des jeux où le joueur doit jouer dans toutes les composantes d'une somme, et non plus une seule d'entre elles.
  • Hot Battles followed by Cold Wars traite des jeux où le joueur peut jouer dans les composantes qu'il souhaite (éventuellement plusieurs, mais pas forcément toutes)
  • Games infinite and Indefinite introduit des jeux avec un nombre infini de positions, qui font notamment intervenir les nombres ordinaux.
  • Games Eternal - Games Entailed présente des jeux permettant le coup forçant (entailing move), c'est-à-dire qui force l'adversaire à jouer dans la même composante de la somme.
  • Survival in the Lost World décrit la théorie des jeux impartiaux en version misère, c'est-à-dire lorsque le joueur qui ne peut plus jouer est cette fois le gagnant.

Troisième volume

modifier

Le troisième volume contient 9 chapitres, triés par type de jeu, et traite d'un très grand nombre de jeux combinatoires, en leur appliquant les théories des deux premiers volumes.

  • Turn and Turn About décrit plusieurs variantes du jeu de Nim.
  • Chips and Strips traite d'autres variantes du jeu de Nim, des jeux de soustraction, qui sont un cas particulier de jeu octal, mais aussi du jeu de Cram.
  • Dots-and-Boxes, un chapitre entier consacré aux subtilités de La Pipopipette (Dots-and-Boxes en anglais).
  • Spots and Sprouts introduit plusieurs jeux de papier et crayon qui peuvent se jouer avec des points et des courbes sur une feuille de papier, dont en particulier le Sprouts.
  • The Emperor and his money traite du jeu de Sylver Coinage (en)
  • The King and the Consumer introduit le problème de l'ange, et de multiples variations possibles de ce jeu.
  • Fox and Geese un chapitre entier sur les jeux du type Renard et poules.
  • Hare and Hounds un chapitre sur une variation du jeu Renard et poules
  • Lines and Squares traite des jeux de plateaux, dont Tic-tac-toe, Hex ou Othello.

Quatrième volume

modifier

Le quatrième et dernier volume est composé de trois chapitres. Il ne traite pas des jeux combinatoires à deux joueurs, mais plutôt de jeux ou casse-têtes à résoudre seul, et donne également une analyse détaillée du jeu de la vie.

  • Purging Pegs Properly est une étude mathématique du jeu de Solitaire.
  • Pursuing Puzzles purposefully s'intéresse aux casse-têtes, comme le Cube Soma, la Tour de Hanoï, le Rubik's Cube (avec la description d'une solution), ou Polyomino.
  • What is Life? étudie le jeu de la vie, un automate cellulaire, et montre qu'il est possible d'implémenter un ordinateur avec cet automate. En effet, certaines configurations particulières permettent de créer des portes ET, OU et NON, ou des espaces de stockage similaires à la mémoire d'un ordinateur. Le jeu de la vie est donc une machine de Turing.

Éditions

modifier
Ce document provient de « https://fr.wiki.x.io/w/index.php?title=Winning_Ways_for_your_Mathematical_Plays&oldid=209677102 ».