Concept
Arbre de jeu
Concepts associés (14)
Élagage alpha-bêta
En informatique, plus précisément en intelligence artificielle et en théorie des jeux, l’élagage alpha-bêta (abrégé élagage αβ) est une technique permettant de réduire le nombre de nœuds évalués par l'algorithme minimax. Il est utilisé dans des programmes informatiques qui jouent à des jeux à 2 joueurs, comme les échecs ou les dames. L'algorithme minimax effectue une exploration complète de l'arbre de recherche jusqu'à un niveau donné. L'élagage alpha-beta permet d'optimiser grandement l'algorithme minimax sans en modifier le résultat.
Effet d'horizon
En informatique, et plus précisément en intelligence artificielle, leffet d'horizon est un phénomène se produisant dans l'exploration d'arbres de décision lorsque ceux-ci, comme c'est le cas pour de nombreux jeux tels que les échecs ou le go, sont trop vastes pour être parcourus en entier par la méthode dite de « force brute ».
Game complexity
Combinatorial game theory measures game complexity in several ways: State-space complexity (the number of legal game positions from the initial position), Game tree size (total number of possible games), Decision complexity (number of leaf nodes in the smallest decision tree for initial position), Game-tree complexity (number of leaf nodes in the smallest full-width decision tree for initial position), Computational complexity (asymptotic difficulty of a game as it grows arbitrarily large).
Jeu séquentiel
vignette| Les échecs sont un exemple de jeu séquentiel. En théorie des jeux, un jeu séquentiel est un jeu où les joueurs choisissent leur actions à tour de rôle. Pour qu'un jeu soit séquentiel il faut que certaines informations sur les choix d'un joueur à son tour soient connues par les joueurs suivants avant qu'ils ne fassent eux-mêmes leur choix; sans cela, le tour du premier joueur n'aurait pas d'effet sur la stratégie des suivants. Les jeux séquentiels sont donc régis par l'axe du temps, et peuvent être représentés sous forme d'arbres de décision.
Théorie des jeux combinatoires
La théorie des jeux combinatoires est une théorie mathématique qui é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. La théorie des jeux combinatoires a pour objet les jeux à information complète où le hasard n'intervient pas, comme les échecs, les dames ou le jeu de go.
Extensive-form game
In game theory, an extensive-form game is a specification of a game allowing (as the name suggests) for the explicit representation of a number of key aspects, like the sequencing of players' possible moves, their choices at every decision point, the (possibly imperfect) information each player has about the other player's moves when they make a decision, and their payoffs for all possible game outcomes. Extensive-form games also allow for the representation of incomplete information in the form of chance events modeled as "moves by nature".
Algorithme minimax
L'algorithme minimax (aussi appelé algorithme MinMax) est un algorithme qui s'applique à la théorie des jeux pour les jeux à deux joueurs à somme nulle (et à information complète) consistant à minimiser la perte maximum (c'est-à-dire dans le pire des cas). Pour une vaste famille de jeux, le théorème du minimax de von Neumann assure l'existence d'un tel algorithme, même si dans la pratique il n'est souvent guère aisé de le trouver.
Raisonnement rétrograde
vignette|Un jeu séquentiel en quatre étapes avec une limite de prévoyance Le raisonnement rétrograde ou l'induction à rebours (Backward induction) est une méthode de raisonnement qui consiste à partir d'un résultat final connu pour retracer les étapes ou les événements qui ont conduit à ce résultat. Principalement utilisée en théorie des jeux, il est utilisé pour résoudre les jeux de manière séquentielle en partant de la fin du jeu et en remontant jusqu'au début.
Ply (game theory)
In two-or-more-player sequential games, a ply is one turn taken by one of the players. The word is used to clarify what is meant when one might otherwise say "turn". The word "turn" can be a problem since it means different things in different traditions. For example, in standard chess terminology, one move consists of a turn by each player; therefore a ply in chess is a half-move. Thus, after 20 moves in a chess game, 40 plies have been completed—20 by white and 20 by black.
Decision tree pruning
Pruning is a data compression technique in machine learning and search algorithms that reduces the size of decision trees by removing sections of the tree that are non-critical and redundant to classify instances. Pruning reduces the complexity of the final classifier, and hence improves predictive accuracy by the reduction of overfitting. One of the questions that arises in a decision tree algorithm is the optimal size of the final tree. A tree that is too large risks overfitting the training data and poorly generalizing to new samples.