Context may be all you need

[IA Series 1/n] AI Search - Terms and Algorithms

This is the first post in a series on intelligent agents, it focus on defining terms and algorithms used when using AI to search for solutions.

1. Basic Search Terms

Agent: An entity that perceives its environment and takes actions to achieve goals.

State: A configuration or situation in the problem environment.

Actions: Operations that can be applied to transform one state into another.

State Space: The set of all states reachable from the initial state by any sequence of actions.

Transition Model: Describes what happens when an action is applied to a state (function T(s, a) → s').

Path Cost Function: A function that assigns a numeric cost to each path, typically the sum of individual action costs.

Goal Test: A function that determines whether a given state is a goal state.

Initial State: The starting point for the search problem.

Solution: A sequence of actions leading from the initial state to a goal state.

Optimal Solution: A solution with the lowest path cost among all possible solutions.

Node: A data structure used in search algorithms containing a state, parent node, action, path cost, and depth information.

Frontier: The set of all leaf nodes (nodes that have been generated but not yet expanded) available for expansion at any given point during search.

2. Search Algorithms

Uninformed Search: Search strategies that have no additional information about states beyond the problem definition. These algorithms can only generate successors and distinguish a goal state from a non-goal state. Examples include BFS and DFS.

Informed Search: Search strategies that use problem-specific knowledge (heuristics) to find solutions more efficiently. These algorithms have information that can help evaluate how close a state might be to a goal. Examples include A* Search and Greedy Best-First Search.

Adversarial Search: A search technique used in competitive environments where agents have opposing goals. Unlike traditional search problems where a single agent works toward a goal, adversarial search involves multiple agents working against each other (e.g., in games like chess or Go). Algorithms include Minimax and Alpha-Beta Pruning, which account for an opponent’s optimal countermoves.

Uninformed Search Algorithms

Depth-First Search (DFS): A search algorithm that uses a stack (LIFO - Last In, First Out) to manage the frontier, exploring as far as possible along each branch before backtracking. This approach explores deeper nodes before shallower ones.

Breadth-First Search (BFS): A search algorithm that uses a queue (FIFO - First In, First Out) to manage the frontier, exploring all nodes at the present depth before moving to nodes at the next depth level. This approach explores shallower nodes before deeper ones.

Heuristic Function - h(n): A function that estimates the cost of the cheapest path from a given state to a goal state. It provides problem-specific knowledge to guide search algorithms. An admissible heuristic never overestimates the true cost to reach the goal.

Greedy Best-First Search: An informed search algorithm that expands the node that appears to be closest to the goal according to the heuristic function. It always selects the most promising node based solely on h(n), ignoring the cost already incurred to reach that node.

Manhattan Distance: A heuristic function that calculates the sum of the absolute differences between the coordinates of two points. In grid-based problems, it represents the number of steps needed to reach the goal if there were no obstacles, counting only horizontal and vertical movements (no diagonals). For points (x₁, y₁) and (x₂, y₂), it is calculated as |x₁ - x₂| + |y₁ - y₂|.

A* Search: An informed search algorithm that combines the path cost so far g(n) and the estimated cost to the goal h(n) to determine which node to expand next. It selects the node with the lowest f(n) = g(n) + h(n). A* is optimal when:

  • h(n) is admissible: The heuristic never overestimates the true cost to the goal
  • h(n) is consistent (or monotonic): For every node n and successor n' with step cost c, h(n) ≤ h(n') + c

Minimax: An adversarial search algorithm used for decision-making in two-player games. The algorithm recursively evaluates all possible moves, assuming that the opponent will make the most optimal move from their perspective. The maximizing player tries to maximize the evaluation function, while the minimizing player tries to minimize it. The algorithm alternates between max and min levels as it traverses the game tree, ultimately selecting the move that leads to the best worst-case outcome.

Alpha-Beta Pruning: An optimization technique for the Minimax algorithm that reduces the number of nodes evaluated in the search tree. It maintains two values, alpha (the minimum score that the maximizing player is assured) and beta (the maximum score that the minimizing player is assured). If at any point a move is found that would cause the current position to have a value that the opponent could avoid by an earlier move choice, that branch can be “pruned” (eliminated from further consideration). Alpha-Beta pruning yields the same result as Minimax but is much more efficient.

Depth-Limited Minimax: A variant of the Minimax algorithm that addresses the computational complexity by limiting the search to a predetermined depth in the game tree. Instead of searching all the way to terminal states, the algorithm stops at a specified depth and applies an evaluation function to estimate the value of non-terminal states. This approach makes Minimax practical for games with large branching factors, though it may result in less accurate evaluations compared to a full Minimax search.

Evaluation Function: A function that estimates the value or utility of a non-terminal game state. In depth-limited minimax search, the evaluation function is used to assign scores to states at the cutoff depth, providing a heuristic assessment of how favorable a position is for a player. A well-designed evaluation function considers various game-specific features (e.g., piece values, board position, mobility) to approximate the true value of a state without exploring the game tree to completion.