Editing Game tree

{{Short description|Combinatorial game theory concept to represent all possible game states}}
{{for|game tree as it is used in game theory (not combinatorial game theory)|Extensive-form game}}
[[Image:Tic-tac-toe-game-tree.svg|thumb|upright=1.35|The diagram shows the first two levels, or ''[[ply (game theory)|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]], [[Draughts|checkers]], [[Go (board game)|Go]], and [[tic-tac-toe]].

A game tree can be used to measure the [[Game complexity|complexity of a game]], as it represents all the possible ways that the game can pan out. Due to the large game trees of [[Game complexity#Complexities of some well-known games|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 algorithm]]s and [[minmax]] algorithms such as [[Monte Carlo tree search|MCTS]] can be used in cases where a complete game tree is not feasible.

== 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.

==Solving game trees==

===Deterministic algorithm version===

[[Image:Arbitrary-gametree-solved.svg|thumb|right|400px|An arbitrary game tree that has been fully colored]]

With a complete game tree, it is possible to "solve" the game – that is to say, find a sequence of moves that either the first or second player can follow that will guarantee the best possible outcome for that player (usually a win or a tie).  The [[deterministic algorithm]] (which is generally called [[backward induction]] or [[retrograde analysis]]) can be described recursively as follows.

# Color the final ply of the game tree so that all wins for player 1 are colored one way (Blue in the diagram), all wins for player 2 are colored another way (Red in the diagram), and all ties are colored a third way (Grey in the diagram). 
# Look at the next ply up.  If there exists a node colored opposite as the current player, color this node for that player as well.  If all immediately lower nodes are colored for the same player, color this node for the same player as well.  Otherwise, color this node a tie.
# Repeat for each ply, moving upwards, until all nodes are colored.  The color of the root node will determine the nature of the game.

The diagram shows a game tree for an arbitrary game, colored using the above algorithm.

It is usually possible to solve a game (in this technical sense of "solve") using only a subset of the game tree, since in many games a move need not be analyzed if there is another move that is better for the same player (for example [[alpha-beta pruning]] can be used in many deterministic games).

Any subtree that can be used to solve the game is known as a '''decision tree''', and the sizes of decision trees of various shapes are used as measures of [[game complexity]].<ref name="Allis1994">{{cite book | author = Victor Allis | author-link = Victor Allis | year = 1994 | title = Searching for Solutions in Games and Artificial Intelligence | publisher = Ph.D. Thesis, University of Limburg, Maastricht, The Netherlands | isbn = 90-900748-8-0 | url = http://fragrieu.free.fr/SearchingForSolutions.pdf}}</ref>

===Randomized algorithms version===
[[Randomized algorithm]]s can be used in solving game trees. There are two main advantages in this type of implementation: speed and practicality. Whereas a deterministic version of solving game trees can be done in {{math|''Ο''(''n'')}}, the following randomized algorithm has an expected run time of {{math|''θ''(''n''<sup>0.792</sup>)}} if every node in the game tree has degree 2. Moreover, it is practical because randomized algorithms are capable of "foiling an enemy", meaning an opponent cannot beat the system of game trees by knowing the algorithm used to solve the game tree because the order of solving is random.

The following is an implementation of randomized game tree solution algorithm:<ref name="Roche2013">{{cite book | author = Daniel Roche | author-link = Daniel Roche | year = 2013 | title = SI486D: Randomness in Computing, Game Trees Unit | publisher = United States Naval Academy, Computer Science Department | url = http://www.usna.edu/Users/cs/roche/courses/s13si486d/u03/ | access-date = 2013-04-29 | archive-date = 2021-05-08 | archive-url = https://web.archive.org/web/20210508074443/https://www.usna.edu/Users/cs/roche/courses/s13si486d/u03/ | url-status = dead }}</ref>

<syntaxhighlight lang="python">
def gt_eval_rand(u) -> bool:
    """Returns True if this node evaluates to a win, otherwise False"""
    if u.leaf:
        return u.win
    else:
        random_children = (gt_eval_rand(child) for child in random_order(u.children))
        if u.op == "OR":
            return any(random_children)
        if u.op == "AND":
            return all(random_children)
</syntaxhighlight>

The algorithm makes use of the idea of "[[Short-circuit evaluation|short-circuiting]]": if the root node is considered an "{{mono|OR}}" operator, then once one {{mono|True}} is found, the root is classified as {{mono|True}}; conversely, if the root node is considered an "{{mono|AND}}" operator then once one {{mono|False}} is found, the root is classified as {{mono|False}}.

<ref>{{Cite journal|last1=Pekař|first1=Libor|last2=Matušů|first2=Radek|last3=Andrla|first3=Jiří|last4=Litschmannová|first4=Martina|date=September 2020|title=Review of Kalah Game Research and the Proposition of a Novel Heuristic–Deterministic Algorithm Compared to Tree-Search Solutions and Human Decision-Making|journal=Informatics|language=en|volume=7|issue=3|pages=34|doi=10.3390/informatics7030034|doi-access=free|hdl=10084/142398|hdl-access=free}}</ref>{{clear}}

==See also==
* [[Alpha-beta pruning]]
* [[Extensive form game]]
* [[Shannon number]]
* [[Game complexity]]

==References==
{{Reflist}}

==Further reading==
* {{cite book|last = Hu|first = Te Chiang|author2=Shing, Man-tak|title = Combinatorial Algorithms|publisher = Courier Dover Publications|year = 2002|isbn = 0-486-41962-2|url = https://books.google.com/books?id=BF5_bCN72EUC|access-date = 2007-04-02}}
* [[Judea Pearl]], ''Heuristics'', Addison-Wesley, 1984
<!-- *Aske Plaat, Jonathan Schaeffer, Wim Pijls, and Arie de Bruin. [http://plaat.nl/Papers/AAAI-final.pdf Exploiting Graph Properties of Game Trees] -->

[[Category:Articles with example Python (programming language) code]]
[[Category:Combinatorial game theory]]
[[Category:Trees (graph theory)]]