Depth-First Search, Heuristics, and Game Theory Explained
Depth-First Search (DFS)
Depth-First Search (DFS) is an algorithm used to traverse or recursively explore all nodes of a graph or tree in a systematic, but not uniform, manner. It expands each node it encounters recursively along a specific path. When there are no more nodes to visit along that path, it backtracks to explore the siblings of the node and continues the process.
Heuristics
Definition
Heuristics are techniques that increase the efficiency of a search. It involves analyzing and extrapolating data based on past experiences and their consequences. This approach is crucial for AI methods or game algorithms. Heuristics are exploratory during problem-solving, where solutions are discovered by evaluating progress toward the final result. It’s the “extra” element that allows us to reach the solution more quickly.
Objective
The objective of heuristics is to guide the search process in the most profitable direction by suggesting a way forward when multiple options exist.
Heuristic Types
- General: Suitable for a wide variety of domains.
- Domain-Specific: Exploit domain-specific knowledge to solve problems.
Assessment
Admissible Heuristics
Admissible heuristics are optimistic by nature. In all admissible heuristics, cost never decreases along all paths. These heuristics are considered monotone. When not monotonous, correct it as follows: Consider two nodes, n and n’.
- n is the parent node of n’.
- g(n) = 3, h(n) = 4 -> f(n) = 7
- g(n’) = 4, h(n’) = 2 -> f(n’) = 6
Any paths that pass through n’ also pass through n, so f(n’) is not relevant. Therefore, every time you build a new node, confirm that its cost is less than its parent.
f(n) = max(f(n), g(n’) + h(n’))
Dominant Heuristics
Consider two heuristics, h1 and h2. If h2(n) >= h1(n) for any node n, then h2 dominates h1. Domination results in efficiency: a dominant heuristic expands fewer nodes. It is preferable to use a dominant heuristic function if it is admissible.
Game Theory
The objective of game theory is to analyze not just random elements but the strategic behavior of players. Games can be classified in various ways, but we focus on those classified by the outcome. They can be zero-sum, where one player’s gain implies an equal loss for another, or non-zero-sum, where the sum of players’ earnings may increase or decrease based on their decisions.
Minimax Algorithm
This algorithm is generally applied to two-player games where one player’s gain equals the other’s loss. It assumes the program has all the time needed to reach the terminal states.
- Generate the tree until the terminal states.
- Apply the evaluation function and take the respective heat.
- Use the terminal state utility to calculate the value of the nodes at the next level.
- Finally, backtrack to the top of the tree, with Max choosing the maximum value and Min choosing the minimum.
Alpha-Beta Pruning
Alpha-Beta pruning is an improvement over Minimax, offering the opportunity to prune branches that are not efficient. The efficiency of alpha-beta depends on the order in which successors are analyzed, prioritizing those more likely to be better. Assuming this is possible, alpha-beta can anticipate minimax twice as fast.
Alpha-Beta Algorithm
alpha-beta (node, depth, alpha, beta)
if (node is terminal) or (depth == 0) return Evaluation(node)
if node is maximizing
for all children i (node)
alpha = max(alpha, literate(childi, depth - 1, alpha, beta))
if (alpha >= beta) return beta; //"can prune the following children"
return alpha
if node is minimizing
for all children i (node)
beta = min(beta, literate(childi, depth - 1, alpha, beta))
if alpha <= beta return alpha
return beta