Théorie des jeux combinatoires
La théorie des jeux combinatoires, également connue sous le nom de CGT, est une branche des mathématiques appliquées et de l'informatique théorique qui étudie les jeux combinatoires, et se distingue de la théorie des jeux "traditionnels" ou "éco…
La théorie des jeux combinatoires, également connue sous le nom de CGT, est une branche des mathématiques appliquées et de l'informatique théorique qui étudie les jeux combinatoires, et se distingue de la théorie des jeux "traditionnels" ou "économiques". La CGT est apparue en relation avec la théorie des jeux impartiaux, le jeu à deux joueurs de Nim en particulier, avec un accent sur la "résolution" de certains types de jeux combinatoires.
Un jeu doit remplir plusieurs conditions pour être un jeu combinatoire. Ces conditions sont les suivantes :
La théorie des jeux combinatoires se limite en grande partie à l'étude d'un sous-ensemble de jeux combinatoires à deux joueurs, finis, avec un gagnant et un perdant (c'est-à-dire qui ne se terminent pas par un match nul).
Ces jeux combinatoires peuvent être représentés par des arbres, dont chaque sommet est le jeu résultant d'un coup particulier du jeu situé directement en dessous sur l'arbre. Des valeurs de jeu peuvent être attribuées à ces jeux. Trouver ces valeurs de jeu est d'un grand intérêt pour les théoriciens de la CG, tout comme le concept théorique de l'addition de jeux. La somme de deux parties est la partie dans laquelle chaque joueur doit, à son tour, se déplacer dans une seule des deux parties, en laissant l'autre telle quelle.
Elwyn Berlekamp, John Conway et Richard Guy sont les fondateurs de cette théorie. Ils ont travaillé ensemble dans les années 1960. Leur ouvrage publié s'intitulait Winning Ways for Your Mathematical Plays.
Galerie d’images
1 Image
Définitions
Dans la théorie, il y a deux joueurs appelés gauche et droite. Un jeu est quelque chose qui permet à la gauche et à la droite de se déplacer vers d'autres jeux. Par exemple, aux échecs, il y a une configuration de départ habituelle. On peut aussi, cependant, considérer qu'une partie d'échecs après le premier coup est une partie différente, avec une configuration différente. Ainsi, chaque position est également appelée une partie.
Les jeux ont la notation {L|R}. Les jeux qui ont la notation {L|R}
sont ceux vers lesquels le joueur de gauche peut se déplacer.
R sont les jeux dans lesquels le joueur de droite peut se déplacer. Si vous connaissez la notation des échecs, la configuration habituelle des échecs est la partie
| { a 3 , a 4 , N a 3 , b 3 , b 4 , c 3 , c 4 , N c 3 , ... | a 6 , a 5 , N a 6 , b 6 , b 5 , c 6 , c 5 , N c 6 , ... } {\displaystyle \{a3,a4,Na3,b3,b4,c3,c4,Nc3,\dots \a6,a5,Na6,b6,b5,c6,c5,Nc6,\dots \}} |
Les points "..." signifient qu'il y a beaucoup de mouvements, donc tous ne sont pas affichés.
Les échecs sont très complexes. Il est préférable de penser à des parties plus faciles. Nim, par exemple, est beaucoup plus simple à envisager. Nim se joue comme ceci :
- Il y a zéro ou plusieurs piles de compteurs.
- Lors d'un tour, un joueur peut prendre autant de pions d'une pile qu'il le souhaite.
- Le joueur qui ne peut pas effectuer un coup perd.
Le jeu le plus facile de Nim commence sans aucun pion ! Dans ce cas, aucun des deux joueurs ne peut bouger. Cela est indiqué par {|}. Les deux côtés sont vides, car aucun des joueurs ne peut se déplacer. Le premier joueur à partir ne peut pas se déplacer, et donc perd. En CGT, on écrit souvent {|} comme le symbole 0 (zéro).
Le jeu le plus facile suivant ne comporte qu'une pile, avec un seul pion. Si le joueur de gauche part le premier, il doit prendre le pion, et le joueur de droite ne peut pas bouger ({|}, ou 0). Si c'est le joueur de droite qui commence, il n'y aura plus de coups pour le joueur de gauche. La gauche et la droite peuvent donc toutes deux se déplacer jusqu'à 0, ce qui est indiqué par {{|}|{|}} ou {0|0}. Le premier joueur à se déplacer gagne. Les parties égales à {0|0} sont très importantes. Elles sont écrites avec le symbole * (étoile).
Questions et réponses
Q : Qu'est-ce que la théorie des jeux combinatoires ?
R : La théorie des jeux combinatoires (CGT) est une branche des mathématiques appliquées et de l'informatique théorique qui étudie les jeux combinatoires, et se distingue de la théorie des jeux "traditionnelle" ou "économique".
Q : Quelles conditions un jeu doit-il remplir pour être considéré comme un jeu combinatoire ?
R : Pour qu'un jeu soit considéré comme un jeu combinatoire, il doit avoir au moins deux joueurs, il doit être séquentiel (c'est-à-dire que les joueurs alternent leurs tours), il doit avoir une information parfaite (c'est-à-dire qu'aucune information n'est cachée), il doit être déterministe (c'est-à-dire qu'il n'y a pas de hasard), la chance ne peut pas faire partie du jeu, il doit y avoir un nombre défini de mouvements possibles, le jeu doit finir par se terminer et le jeu doit se terminer lorsqu'un joueur ne peut plus bouger.
Q : Sur quel type de jeux la théorie combinatoire des jeux se concentre-t-elle ?
R : La théorie combinatoire des jeux se concentre principalement sur les jeux finis à deux joueurs qui ont des gagnants et des perdants (c'est-à-dire qui ne se terminent pas par un match nul).
Q : Comment ces types de jeux sont-ils représentés ?
R : Ces types de jeux peuvent être représentés par des arbres dont chaque sommet représente le jeu résultant d'un mouvement particulier du joueur situé directement en dessous de lui sur l'arbre.
Q : Quels sont les objectifs des théoriciens de la GC ?
R : Parmi les objectifs des théoriciens de la CG, il y a la recherche de valeurs pour ces types de jeux ainsi que la compréhension du concept d'"addition de jeux", qui implique que chaque joueur n'effectue qu'un seul mouvement dans deux jeux différents, laissant l'autre inchangé pendant son tour.
Q : Qui a fondé la CGT ?
R : Elwyn Berlekamp, John Conway et Richard Guy sont crédités d'avoir fondé la CGT dans leur ouvrage publié intitulé Winning Ways for Your Mathematical Plays dans les années 1960.
Articles liés
Auteur
AlegsaOnline.com Théorie des jeux combinatoires Leandro Alegsa
URL: https://fr.alegsaonline.com/art/21870