Concept
Game complexity
Concepts associés (16)
Gomoku
Le gomoku, du nom japonais gomoku narabe (Kanji : 五目並べ, littéralement, « alignement des cinq pions ») est le nom japonais d'un jeu de plateau chinois, où il est nommé Wǔzi qí (五子棋, littéralement, « l'échiquier des 5 ») consistant à aligner 5 pions sur les intersections d'un plateau de jeu de go (ou wéiqí, 围棋). Il est également connu en France sous le nom de « Darpion ». Découvert au siècle dernier par les anglo-saxons, le gomoku (prononcer « gomokou ») a des millions d'adeptes en Extrême-Orient (Chine, Corée, Japon).
Arbre de jeu
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. 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 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.
PSPACE-complete
In computational complexity theory, a decision problem is PSPACE-complete if it can be solved using an amount of memory that is polynomial in the input length (polynomial space) and if every other problem that can be solved in polynomial space can be transformed to it in polynomial time. The problems that are PSPACE-complete can be thought of as the hardest problems in PSPACE, the class of decision problems solvable in polynomial space, because a solution to any one such problem could easily be used to solve any other problem in PSPACE.
Jeu de stratégie combinatoire abstrait
On appelle jeu de stratégie combinatoire abstrait ou jeu combinatoire à information parfaite, selon la définition donnée par la théorie des jeux combinatoires, un jeu, généralement un jeu de société : opposant généralement deux joueurs ou deux équipes (ou bien un joueur humain seul contre un ordinateur « intelligent ») ; dans lequel les joueurs ou équipes jouent à tour de rôle ; dont tous les éléments sont connus (jeu à information complète) ; où le hasard n'intervient pas pendant le déroulement du jeu.
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 ».
Hex
Le jeu de Hex est un jeu de société combinatoire abstrait pour deux joueurs. Il se joue sur un tablier en forme de losange dont les cases sont hexagonales. Toutes les dimensions du côté du losange sont possibles, la plus traditionnelle est celle composée par 11 hexagones, mais on trouve aussi les valeurs 13 ou 19. L'un des inventeurs du jeu, John Nash, préconise un tablier de taille 14 × 14. Ce jeu possède des similarités avec le go. Ce jeu, inventé par des mathématiciens fait uniquement appel à la logique, à l'image du go ou des échecs.
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.
Xiangqi
Le xiangqi ( ; Shanghaïen : Jiandji /ʒjɑ̃dʒi/ ), aussi appelé « échecs chinois » (par opposition aux échecs occidentaux), est un jeu de société combinatoire abstrait qui se joue sur un tableau rectangulaire de 9 lignes de large sur 10 lignes de long. Le jeu est également connu au Japon sous le nom de kawanakajima shōgi (le shōgi est un autre jeu d’échecs traditionnel au Japon, dont il existe aussi de nombreuses variantes). Ce jeu se joue avec 16 pièces par joueur qui sont placées sur les intersections des lignes.
State space (computer science)
In computer science, a state space is a discrete space representing the set of all possible configurations of a "system". It is a useful abstraction for reasoning about the behavior of a given system and is widely used in the fields of artificial intelligence and game theory. For instance, the toy problem Vacuum World has a discrete finite state space in which there are a limited set of configurations that the vacuum and dirt can be in. A "counter" system, where states are the natural numbers starting at 1 and are incremented over time has an infinite discrete state space.