Nov 16, 2026 | 511 words | 5 min read
7.1.5. PCMs: Decision Trees#
These pre-class materials introduce decision trees, an algorithm used to model outcomes and make optimal choices.
In engineering, understanding how to simulate scenarios and calculate probabilities is essential for predictive modeling. In this module, you will learn how decision trees map out possible paths, how complexity limits computation, and how engineers optimize algorithms to solve complex problems.
What is a Decision Tree?#
A decision tree is an algorithm that simulates the resultant paths from a set of possible choices.
To operate, the algorithm simulates all possible subsequent moves until it reaches an end state. It classifies each outcome (such as a win, loss, or tie) and calculates the probability of success for each initial choice. The system then selects the branch with the highest probability of achieving the desired outcome. After the system or opponent makes a subsequent move, the algorithm repeats the process with the remaining possible paths.
Complexity and Computation Limits#
Some systems have a relatively limited number of outcomes. For example, a game of Tic-Tac-Toe has 986,405 possible combinations, which a computer can easily map to the end.
More complex systems, like chess, possess \(10^{120}\) possible combinations. This number is greater than the estimated atoms in the visible universe, making it impossible for a computer to simulate every single path.
Check for Understanding
Why is it impossible for a computer to use a standard, unoptimized decision tree to map out every possible game of chess from start to finish?
A. Chess has an estimated \(10^{120}\) possible combinations, which far exceeds the
processing limits of any computer.
B. Computers cannot accurately classify qualitative outcomes like wins, losses, or
ties.
C. The rules of chess constantly change, making it impossible to program a stable
tree.
D. Chess pieces do not follow a strict mathematical pattern.
Show Answer
Correct Answer: A
Some systems, like Tic-Tac-Toe, have a limited number of outcomes (986,405) that a computer can easily map.
However, chess has \(10^{120}\) possible ways to play, which is greater than the estimated number of atoms in the visible universe. Because of this complexity, computers cannot simulate every single path without optimization.
Engineering and Optimization#
To solve complex problems using decision trees, engineers must optimize the algorithm so it does not overwhelm the computer’s processing limits. When programmers built the Deep Blue computer to play chess, they optimized the system using three specific strategies:
Limited Simulation: Instead of mapping the entire game, the computer only simulated three to four moves ahead.
State Scoring: The algorithm used predetermined rules to score the value of each simulated board position, factoring in parameters like king safety and board control.
Strategic Assumptions: The system assumed the opponent would always make the best possible move, allowing the algorithm to safely eliminate unneeded branches and save computing power.
The Evolution of Machine Learning#
Early decision tree algorithms required engineers to pre-program all the rules and domain knowledge into the system. Modern algorithms use neural networks and machine learning to learn the rules of a system autonomously through training. This advancement allows a single AI algorithm to quickly master multiple different complex scenarios.