Élagage alpha-bêtaEn 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.
Équilibre de Nashvignette|Le dilemme du prisonnier : chacun des deux joueurs dispose de deux stratégies : D pour dénoncer, C pour ne pas dénoncer. La matrice présente le gain des joueurs. Si les deux joueurs choisissent D (se dénoncent), aucun ne regrette son choix, car s'il avait choisi C, alors que l'autre a opté pour D, sa « tristesse » aurait augmenté. C'est un équilibre de Nash — il y a « non-regret » de son choix par chacun, au vu du choix de l'autre.
Théorie de la décisionLa théorie de la décision est une théorie de mathématiques appliquées ayant pour objet la prise de décision par une entité unique. (Les questions liées à la décision collective relèvent de la théorie du choix social.) La notion de décision intertemporelle découle de la prise en compte du facteur temps dans les problématiques reliant l'offre et la demande, les disponibilités et les contraintes. Ces problématiques sont celles qui découlent des combinaisons possibles entre les disponibilités et les décisions pouvant les impliquer.
Algorithme de rechercheEn informatique, un algorithme de recherche est un type d'algorithme qui, pour un domaine, un problème de ce domaine et des critères donnés, retourne en résultat un ensemble de solutions répondant au problème. Supposons que l'ensemble de ses entrées soit divisible en sous-ensemble, par rapport à un critère donné, qui peut être, par exemple, une relation d'ordre. De façon générale, un tel algorithme vérifie un certain nombre de ces entrées et retourne en sortie une ou plusieurs des entrées visées.
Programme d'échecsvignette|Jeu d'échecs électronique des années 1990 avec écran LCD. Un programme d'échecs est un programme informatique conçu pour jouer au jeu d'échecs. L'histoire des machines joueuses d'échecs n'attend pas le développement de l'électronique et de l'informatique : la première fut l'automate turc inventée en 1769 par Johan Wolfgang von Kempelen, qui joua notamment contre l'impératrice Catherine II et Napoléon Bonaparte. C'était en fait un homme de petite taille caché dans la machine.
Go (jeu)Le go, également appelé jeu de go, appelé en japonais , ou dans certaines expressions ; en chinois (), en Hanyu pinyin wéiqí, la prononciation shanghaïenne Wedji; et en coréen baduk (바둑), est un jeu de société originaire de Chine. Il oppose deux adversaires qui placent à tour de rôle des pierres, respectivement noires et blanches, sur les intersections d'un tablier quadrillé appelé goban en japonais ( en chinois). Le but est de contrôler le plan de jeu en y construisant des « territoires ».
Arbre de jeuEn 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. vignette| Les deux premiers de l'arbre de jeu pour le tic-tac-toe. 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).
Théorie des jeux combinatoiresLa 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.
Jeu à somme nulleUn jeu de somme nulle est un jeu où la somme des gains et des pertes de tous les joueurs est égale à 0. Cela signifie donc que le gain de l'un constitue obligatoirement une perte pour l'autre. Par exemple si l'on définit le gain d'une partie d'échecs comme 1 si on gagne, 0 si la partie est nulle et -1 si on perd, le jeu d'échecs est un jeu à somme nulle. En économie, cette notion simplificatrice est importante : les jeux à somme nulle correspondent à l'absence de production ou de destruction de produits.
Recherche exhaustiveLa recherche exhaustive ou recherche par force brute est une méthode algorithmique qui consiste principalement à essayer toutes les solutions possibles. Par exemple pour trouver le maximum d'un certain ensemble de valeurs, on consulte toutes les valeurs. En cryptanalyse on parle d'attaque par force brute, ou par recherche exhaustive pour les attaques utilisant cette méthode. Le principe de cet algorithme est d'essayer toutes les possibilités dans un intervalle. Un exemple courant est l'attaque par force brute des mots de passe.
Stratégie (théorie des jeux)En théorie des jeux, la stratégie d'un joueur est l’une des options qu’il choisit dans un contexte où le résultat dépend non seulement de ses propres actions, mais également de celles des autres . La stratégie d'un joueur déterminera l'action qu'il entreprendra à n'importe quel stade de la partie. Une stratégie est un algorithme complet pour jouer à un jeu permettant au joueur de déterminer ce qu’il doit faire dans toutes les situations possibles du jeu.
Lexique du jeu d'échecsCe lexique du jeu d'échecs énumère par ordre alphabétique les termes les plus couramment utilisés au jeu d'échecs. Dans certains cas, il existe des pages propres à ces termes. Pour une liste des joueurs, voir Liste de joueurs d'échecs. Pour le lexique spécifique aux problèmes d'échecs, voir Lexique de la composition échiquéenne. Abandon indication qu'un camp accepte la défaite. Dans le cadre d'une compétition, le joueur déclare oralement qu'il abandonne ou couche son roi.
Théorie du regretLa théorie du regret ou de l'aversion au regret ou du regret anticipé est un modèle de théorie économique développé simultanément en 1982 par Graham Loomes et Robert Sugden, David E. Bell, et Peter C. Fishburn. Elle permet de développer des modèles de choix dans un contexte d'incertitude qui tiennent compte des effets anticipés du regret. Cette théorie a par la suite été développée par d'autres auteurs. Elle incorpore un terme regret dans la fonction d'utilité qui dépend négativement du produit obtenu et positivement du meilleur produit alternatif l'incertitude étant donnée.
Wald's maximin modelIn decision theory and game theory, Wald's maximin model is a non-probabilistic decision-making model according to which decisions are ranked on the basis of their worst-case outcomes – the optimal decision is one with the least bad worst outcome. It is one of the most important models in robust decision making in general and robust optimization in particular. It is also known by a variety of other titles, such as Wald's maximin rule, Wald's maximin principle, Wald's maximin paradigm, and Wald's maximin criterion.
Game complexityCombinatorial 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).
Info-gap decision theoryInfo-gap decision theory seeks to optimize robustness to failure under severe uncertainty, in particular applying sensitivity analysis of the stability radius type to perturbations in the value of a given estimate of the parameter of interest. It has some connections with Wald's maximin model; some authors distinguish them, others consider them instances of the same principle. It has been developed by Yakov Ben-Haim, and has found many applications and described as a theory for decision-making under "severe uncertainty".
Go en informatiquethumb|Les programmes sont plus performants sur un goban de petite taille (ici 9×9). Le développement de programme informatique capable de jouer au go est un problème de l'intelligence artificielle. Ce problème est considéré comme l'un des plus complexes à résoudre, les algorithmes classiques (minimax et alpha-bêta) offrant des résultats médiocres. Le premier programme a été écrit en 1968 par comme un élément de sa thèse sur la reconnaissance des formes.
