| Property |
Value |
| dbo:abstract
|
- En théorie des jeux, un arbre de jeu est un arbre (au sens de la théorie des graphes) dont les nœuds sont des positions dans un jeu et dont les arêtes sont des mouvements. L'arbre de jeu complet est l'arbre de jeu commençant à la position initiale et contenant tous les mouvements possibles depuis chaque position. Le diagramme ci-contre montre comment coder dans une représentation arborescente le premier tour de jeu au tic-tac-toe : ce sont les deux premiers niveaux dans l'arborescence, la racine représentant la position initiale (une grille vide, en l'occurrence). Les rotations et les réflexions de la grille sont équivalentes, le premier joueur a donc trois choix de déplacement: au centre, au milieu d'un bord ou dans un coin. Le deuxième joueur a deux choix pour la réponse si le premier joueur a joué au centre, sinon cinq choix, ainsi de suite. Le nombre de feuilles dans l'arbre complet du jeu correspond au nombre de parties différentes possibles de jouer au jeu. Par exemple, l'arborescence du tic-tac-toe comporte 255 168 feuilles[réf. nécessaire]. Les arbres de jeu sont importants dans le domaine de l'intelligence artificielle, car une façon de choisir le meilleur coup dans un jeu est de rechercher dans l'arbre du jeu en utilisant l'un des nombreux algorithmes de parcours d'arbre, combinés à des règles de type minimax pour élaguer l'arbre . Le parcours de l'arbre du tic-tac-toe est relativement simple, mais pour des jeux où le nombre de coups possibles est important, comme aux échecs, l'arbre complet du jeu est beaucoup trop grand pour être parcouru. Pour parer à cela un programme de jeu d'échecs recherche un arbre de jeu partiel: le programme parcourt le plus de niveaux possibles depuis la position actuelle dans le temps dont il dispose. Hormis le cas des arbres de jeu «pathologiques» (qui semblent assez rares en pratique), augmenter la profondeur de recherche (c'est-à-dire le nombre de plis recherchés) améliore généralement les chances de choisir le meilleur coup. Les jeux à deux peuvent également être représentés sous forme d'[réf. nécessaire]. Pour que le premier joueur gagne une partie, il doit exister un coup gagnant pour tous les coups du deuxième joueur. Ceci est représenté dans l'arbre et/ou en utilisant la disjonction pour représenter les mouvements alternatifs du premier joueur et en utilisant la conjonction pour représenter tous les mouvements du deuxième joueur. (fr)
- En théorie des jeux, un arbre de jeu est un arbre (au sens de la théorie des graphes) dont les nœuds sont des positions dans un jeu et dont les arêtes sont des mouvements. L'arbre de jeu complet est l'arbre de jeu commençant à la position initiale et contenant tous les mouvements possibles depuis chaque position. Le diagramme ci-contre montre comment coder dans une représentation arborescente le premier tour de jeu au tic-tac-toe : ce sont les deux premiers niveaux dans l'arborescence, la racine représentant la position initiale (une grille vide, en l'occurrence). Les rotations et les réflexions de la grille sont équivalentes, le premier joueur a donc trois choix de déplacement: au centre, au milieu d'un bord ou dans un coin. Le deuxième joueur a deux choix pour la réponse si le premier joueur a joué au centre, sinon cinq choix, ainsi de suite. Le nombre de feuilles dans l'arbre complet du jeu correspond au nombre de parties différentes possibles de jouer au jeu. Par exemple, l'arborescence du tic-tac-toe comporte 255 168 feuilles[réf. nécessaire]. Les arbres de jeu sont importants dans le domaine de l'intelligence artificielle, car une façon de choisir le meilleur coup dans un jeu est de rechercher dans l'arbre du jeu en utilisant l'un des nombreux algorithmes de parcours d'arbre, combinés à des règles de type minimax pour élaguer l'arbre . Le parcours de l'arbre du tic-tac-toe est relativement simple, mais pour des jeux où le nombre de coups possibles est important, comme aux échecs, l'arbre complet du jeu est beaucoup trop grand pour être parcouru. Pour parer à cela un programme de jeu d'échecs recherche un arbre de jeu partiel: le programme parcourt le plus de niveaux possibles depuis la position actuelle dans le temps dont il dispose. Hormis le cas des arbres de jeu «pathologiques» (qui semblent assez rares en pratique), augmenter la profondeur de recherche (c'est-à-dire le nombre de plis recherchés) améliore généralement les chances de choisir le meilleur coup. Les jeux à deux peuvent également être représentés sous forme d'[réf. nécessaire]. Pour que le premier joueur gagne une partie, il doit exister un coup gagnant pour tous les coups du deuxième joueur. Ceci est représenté dans l'arbre et/ou en utilisant la disjonction pour représenter les mouvements alternatifs du premier joueur et en utilisant la conjonction pour représenter tous les mouvements du deuxième joueur. (fr)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 8229 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:année
| |
| prop-fr:isbn
| |
| prop-fr:langue
| |
| prop-fr:lireEnLigne
|
- https://books.google.com/books?id=BF5_bCN72EUC|consulté le=2007-04-02 (fr)
- https://books.google.com/books?id=BF5_bCN72EUC|consulté le=2007-04-02 (fr)
|
| prop-fr:nom
|
- Hu (fr)
- Shing, Man-tak (fr)
- Hu (fr)
- Shing, Man-tak (fr)
|
| prop-fr:prénom
|
- Te Chiang (fr)
- Te Chiang (fr)
|
| prop-fr:texte
| |
| prop-fr:titre
|
- Combinatorial Algorithms (fr)
- Combinatorial Algorithms (fr)
|
| prop-fr:trad
| |
| prop-fr:wikiPageUsesTemplate
| |
| prop-fr:éditeur
| |
| dct:subject
| |
| rdfs:comment
|
- En théorie des jeux, un arbre de jeu est un arbre (au sens de la théorie des graphes) dont les nœuds sont des positions dans un jeu et dont les arêtes sont des mouvements. L'arbre de jeu complet est l'arbre de jeu commençant à la position initiale et contenant tous les mouvements possibles depuis chaque position. Le nombre de feuilles dans l'arbre complet du jeu correspond au nombre de parties différentes possibles de jouer au jeu. Par exemple, l'arborescence du tic-tac-toe comporte 255 168 feuilles[réf. nécessaire]. (fr)
- En théorie des jeux, un arbre de jeu est un arbre (au sens de la théorie des graphes) dont les nœuds sont des positions dans un jeu et dont les arêtes sont des mouvements. L'arbre de jeu complet est l'arbre de jeu commençant à la position initiale et contenant tous les mouvements possibles depuis chaque position. Le nombre de feuilles dans l'arbre complet du jeu correspond au nombre de parties différentes possibles de jouer au jeu. Par exemple, l'arborescence du tic-tac-toe comporte 255 168 feuilles[réf. nécessaire]. (fr)
|
| rdfs:label
|
- Arbre de jeu (fr)
- Arbre de joc (ca)
- Game tree (en)
- ゲーム木 (ja)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
