Short answers, pulled from the story.
A game tree is a directed graph whose nodes are positions in a sequential game that has perfect information. Such games include chess, checkers, Go, and tic-tac-toe. Nodes represent arrangements of pieces on a board game while edges are moves that transfer pieces from one position to another.
The game tree for tic-tac-toe has 255,168 leaf nodes representing all possible different ways the game can be played. This count establishes a baseline for measuring how complex a game truly is. The number of leaf nodes equals the total possible distinct sequences of play from start to finish.
Backward induction or retrograde analysis works recursively to solve a game by coloring final plies based on wins for player 1, player 2, or ties. Analysts move up through each ply checking if nodes exist colored opposite as the current player to determine outcomes. The color of the root node determines the nature of the game after all nodes are processed.
Complete game trees for larger games like chess are much too large to search within available time limits. Algorithms designed to play these classes of games use partial game trees instead of full ones to make computation feasible. Alpha-beta pruning allows analysts to skip moves when another option proves better for the same player.
Randomized algorithms provide speed and practicality compared to deterministic versions that take significant time. These methods allow systems to function where complete enumeration remains computationally prohibitive while foiling an enemy opponent who cannot beat the system by knowing the algorithm used. Randomized algorithms have an expected run time that scales differently than deterministic approaches.