Back Arbre de joc Catalan Árbol de juego Spanish درخت بازی Persian Arbre de jeu French עץ משחק HE ゲーム木 Japanese 게임 트리 Korean Drzewo gry Polish Drevo igre Slovenian Stablo igre Serbian

Game tree

For game tree as it is used in game theory (not combinatorial game theory), see Extensive-form game.
The diagram shows the first two levels, or plies, in the game tree for tic-tac-toe. The rotations and reflections of positions are equivalent, so the first player has three choices of move: in the center, at the edge, or in the corner. The second player has two choices for the reply if the first player played in the center, otherwise five choices. And so on.

In the context of combinatorial game theory, a game tree is a graph representing all possible game states within a sequential game that has perfect information. Such games include chess, checkers, Go, and tic-tac-toe.

A game tree can be used to measure the complexity of a game, as it represents all the possible ways that the game can pan out. Due to the large game trees of complex games such as chess, algorithms that are designed to play this class of games will use partial game trees, which makes computation feasible on modern computers. Various methods exist to solve game trees. If a complete game tree can be generated, a deterministic algorithm, such as backward induction or retrograde analysis can be used. Randomized algorithms and minmax algorithms such as MCTS can be used in cases where a complete game tree is not feasible.

From Wikipedia, the free encyclopedia · View on Wikipedia

Developed by Nelliwinne