Jeux combinatoires/Introduction
La théorie des jeux combinatoires étudie les jeux à deux joueurs comportant un concept de position et où les joueurs jouent à tour de rôle un coup d'une façon définie par les règles, dans le but d'atteindre une certaine condition de victoire. Ce sont des jeux à information complète où le hasard n'intervient pas. Les jeux les plus connus sont les échecs, les dames, les Jeux de mancala ou le jeu de go qui font l’objet de leçons en tant que tels.
On présente dans cette leçon les autres jeux combinatoires qui sont aussi très intéressants mais parfois moins connus:
- Jeux de Nim avec ses variantes:
- Jeu des bâtonnets
- jeu des allumettes ou Jeu de Marienbad
- Jeu de Grundy et Jeu de Wythoff
- Jeu du Morpion (ou Tic, Tac, Toe) ( jeu dont le but est de créer le premier un alignement sur une grille - alignement de 3 pour Tic, Tac, Toe et de 5 pour le morpion )
- Jeu de Hex ( jeu combinatoire qui se joue sur un tablier en forme de losange avec des cases hexagonales )
 = Jeu de Marienbad |
 |
 |
- Jeu de Cram ( se joue sur un damier que l'on remplit progressivement avec des Dominos )
- Othello et Reversi ( ces jeux se jouent sur un tablier unicolore de 64 cases. )
 |
 |
- Le Jeu du chocolat empoisonné ou Chomp est un jeu mathématique à deux joueurs, joué sur un rectangle composé de blocs carrés, souvent représenté comme une tablette de chocolat.
Chaque joueur mange chacun leur tour un ou plusieurs carré de chocolat (on mange tous les carrés situés à la droite ou plus bas que le carré choisi). Le carré en haut à gauche est empoisonné et celui qui le mange perd la partie. C'est un jeu impartial, c'est-à-dire que les coups possibles ne dépendent que de position courante, mais pas du joueur dont c'est le tour.
- Jeu de Sim : c'est un jeu de papier et crayon pour deux joueurs.
On dessine six points (sommets) sur le papier (hexagone régulier) et chaque point est relié à chaque autre sommet par une ligne (arête). Chacun joueur choisit une couleur différente. Les joueurs colorient une arête non encore coloriée à tour de rôle. Le premier joueur qui trace un triangle dont les côtés sont unicolores et dont les sommets appartiennent à l'hexagone a perdu. Seuls les triangles dont les sommets coïncident avec les sommets du graphe comptent ; les intersections d'arêtes ne sont pas concernées.
- NB : ne pas confondre ce jeu avec les jeux de simulation de vie (appelés aussi jeux de type Sim) qui sont des jeux de vie virtuelle où il s'agit de retrouver les principes fondamentaux d'une vie humaine.
Au départ, on dessine n points sur la feuille de papier. Chaque joueur, à tour de rôle, relie un point à un autre point par une ligne et ajoute un nouveau point sur cette ligne. Deux contraintes doivent être respectées : les lignes peuvent être droites ou courbes, de longueur quelconque, mais en aucun cas ne peuvent se croiser, le nouveau point ne peut être à l’extrémité d’une ligne, il doit être sur la ligne et d’un point ne peuvent émerger qu’au maximum trois lignes.
Dans la version normale du jeu, le perdant est celui qui ne peut plus jouer sans enfreindre les deux contraintes. Il existe également une version misère, où celui qui ne peut plus jouer est alors le gagnant.
Jeu impartial et jeu partisan
modifier- Un jeu impartial est un jeu tour par tour dans lequel les coups autorisés, ainsi que les gains obtenus, dépendent uniquement de la position, et pas du joueur dont c'est le tour de jouer.
- Un jeu partisan est un jeu qui n'est pas impartial. Ici les coups disponibles dépendent non seulement de la position, mais aussi du joueur dont c'est le tour de jouer. C'est par exemple le cas du jeu d'échecs.
Références
modifier
