Editing Game tree (section)

== Understanding the game tree ==
To better understand the game tree, it can be thought of as a technique for analyzing adversarial games, which determine the actions that player takes to win the game. In game theory, a game tree is a directed graph whose nodes are positions in a game (e.g., the arrangement of the pieces in a board game) and whose edges are moves (e.g., to move pieces from one position on a board to another).<ref>{{Cite journal|last1=Zuckerman|first1=Inon|last2=Wilson|first2=Brandon|last3=Nau|first3=Dana S.|date=2018|title=Avoiding game-tree pathology in 2-player adversarial search|url=https://onlinelibrary.wiley.com/doi/abs/10.1111/coin.12162|journal=Computational Intelligence|language=en|volume=34|issue=2|pages=542–561|doi=10.1111/coin.12162|s2cid=46926187|issn=1467-8640|url-access=subscription}}</ref>

The '''complete game tree''' for a game is the game tree starting at the initial position and containing all possible moves from each position; the complete tree is the same tree as that obtained from the [[extensive-form game]] representation. To be more specific, the complete game is a norm for the game in game theory. Which can clearly express many important aspects. For example, the sequence of actions that stakeholders may take, their choices at each decision point, information about actions taken by other stakeholders when each stakeholder makes a decision, and the benefits of all possible game results.<ref>{{Cite journal|date=2018-05-01|title=A novel optimization model based on game tree for multi-energy conversion systems|url=https://www.sciencedirect.com/science/article/abs/pii/S0360544218303190|journal=Energy|language=en|volume=150|pages=109–121|doi=10.1016/j.energy.2018.02.091|issn=0360-5442|last1=Huang|first1=Zishuo|last2=Yu|first2=Hang|last3=Chu|first3=Xiangyang|last4=Peng|first4=Zhenwei|bibcode=2018Ene...150..109H |url-access=subscription}}</ref>

The number of [[leaf node]]s in the complete game tree is the number of possible different ways the game can be played. For example, the game tree for tic-tac-toe has 255,168 leaf nodes.

Game trees are important in [[artificial intelligence]] because one way to pick the best move in a game is to search the game tree using any of numerous [[tree search]] algorithms, combined with [[minimax]]-like rules to [[decision tree pruning|prune the tree]]. The game tree for tic-tac-toe is easily searchable, but the complete game trees for larger games like [[chess]] are much too large to search. Instead, a [[chess-playing program]] searches a '''partial game tree''': typically as many plies from the current position as it can search in the time available. Except for the case of "pathological" game trees<ref>{{cite journal |last=Nau |first=Dana | year=1982 |title=An investigation of the causes of pathology in games |journal= Artificial Intelligence |volume=19 |issue=3 |pages=257–278 |doi=10.1016/0004-3702(82)90002-9}}</ref> (which seem to be quite rare in practice), increasing the search depth (i.e., the number of plies searched) generally improves the chance of picking the best move.

Two-person games can also be represented as [[and-or tree]]s. For the first player to win a game, there must exist a winning move for all moves of the second player. This is represented in the and-or tree by using disjunction to represent the first player's alternative moves and using conjunction to represent all of the second player's moves.