Short answers, pulled from the story.
A game tree is a directed graph that represents all possible game states in a sequential game with perfect information. Its nodes are positions in the game and its edges are the moves connecting those positions. Games including chess, checkers, Go, and tic-tac-toe can all be represented this way.
The complete game tree for tic-tac-toe has 255,168 leaf nodes. Each leaf node represents one distinct way the game can be played from start to finish.
Backward induction, also called retrograde analysis, colors nodes from the bottom of the tree upward. Wins for each player and ties are labeled at the final ply, then the algorithm propagates those labels layer by layer until the root node is colored, revealing the game's outcome under perfect play.
The complete game tree for chess is too large to generate on any existing computer. Chess programs instead search as many plies from the current position as time allows, using techniques like alpha-beta pruning to skip branches where a better move for the same player already exists.
Randomized algorithms offer two advantages: faster expected run time compared to the deterministic approach for trees where every node has degree 2, and resistance to exploitation. Because the tree is evaluated in random order, an opponent who knows the algorithm cannot use that knowledge to steer the game toward a favorable outcome.
A decision tree is any subtree of a complete game tree that is sufficient to solve the game and determine optimal play. The sizes of decision trees of various shapes are used as formal measures of game complexity.