A game tree is a rooted tree whose nodes are possible histories of play and whose edges are legal next actions. Internal nodes specify the acting player or a chance move; terminal nodes carry outcomes or payoffs. In an extensive-form game, information sets additionally say which decision histories the acting player can distinguish.
Distinct histories may reach the same board position, so a game tree can contain repeated states that a state graph would merge. For finite two-player zero-sum games with perfect information, minimax search propagates terminal values upward. Chance nodes require expectations instead of maximizing or minimizing their outcomes.
A game tree is a graphical representation used in game theory and artificial intelligence to depict the possible moves in a game and their consequences. It is a tree structure where: - Each node represents a game state, which includes the positions of the pieces, scores, and who's turn it is to move. - Each edge (or branch) represents a possible move that can be made from one game state to another. - The root of the tree represents the initial state of the game.
New to topics? Read the docs here!