Prolog and AI Search Algorithms

Analogy categoryAnalogies

Search Is Built Into Prolog Already

Before implementing any explicit AI search algorithm, it helps to recognize that Prolog is already performing search every time it answers a query. SLD resolution explores a proof tree depth-first, trying each matching clause for a goal in order and backtracking to the next alternative on failure, which is exactly the structure of depth-first search over a state space, just applied to logical goals rather than explicit states.

🏏

Cricket analogy: It is like a coach already having a default batting order, top-down, next batter in line, which already constitutes a search strategy for building an innings before any specialized 'which batter next' algorithm gets added.

Implementing Classic Search: DFS, BFS, and Uninformed Search

For a state-space problem such as finding a path through a graph, Prolog's own depth-first backtracking will happily revisit the same node forever if the graph contains a cycle, since it has no notion of a 'visited' set built in. An explicit depth-first search predicate solves this by threading an accumulator list of already-visited states through the recursion and checking, with \+ member(Next, Visited), that the next candidate node hasn't already appeared on the current path before recursing into it.

🏏

Cricket analogy: It is like a fielding captain explicitly tracking which bowlers have already bowled an over, a visited list, to avoid illegally repeating the same bowler consecutively, since nothing stops it by default.

prolog

edge(a, b). edge(a, c). edge(b, d). edge(c, d). edge(d, e).

path(Start, End, Path) :-
    dfs(Start, End, [Start], Path).

dfs(End, End, Visited, Path) :-
    reverse(Visited, Path).
dfs(Current, End, Visited, Path) :-
    edge(Current, Next),
    \+ member(Next, Visited),
    dfs(Next, End, [Next|Visited], Path).

?- path(a, e, P).
% P = [a, b, d, e] ;
% P = [a, c, d, e].

Breadth-First and Iterative Deepening

Because Prolog's native strategy is depth-first, breadth-first search must be implemented explicitly by maintaining a worklist, typically a list of partial paths still to be explored, and always extending the path at the front of that list before any path added later. Iterative deepening offers a middle ground: it repeatedly runs a depth-limited depth-first search with an increasing depth bound, which finds the shortest solution first like BFS does while keeping DFS's much lower memory footprint.

🏏

Cricket analogy: It is like switching from following just one bowler's spell all the way through, depth-first, to rotating through all available bowlers one over at a time, breadth-first, by explicitly maintaining a bowling rotation queue.

For serious constraint-heavy search problems like N-Queens, most practical Prolog code reaches for library(clpfd) constraint solving or an explicit worklist pattern rather than naive generate-and-test backtracking, since propagating constraints early prunes the search space far more effectively than generating full candidate solutions and testing them afterward.

Best-First and Heuristic Search (A*)

A* search ranks every node on the frontier by f = g + h, where g is the cost already accumulated to reach that node and h is a heuristic estimate of the remaining cost to the goal, always expanding the lowest-f node next. Prolog has no built-in priority queue, so an A* implementation typically keeps the frontier as a list of partial paths kept sorted by f-value, or uses library(heaps) to get proper priority-queue performance instead of re-sorting a list on every step.

🏏

Cricket analogy: It is like a captain prioritizing which bowler to bring on next by combining overs bowled so far, the cost so far, with estimated wickets remaining in the pitch conditions, the heuristic, rather than just going in a fixed rotation.

Running Prolog's raw depth-first backtracking directly on an infinite or cyclic state graph without explicit visited-state tracking can cause non-termination, even though the search 'feels' declarative and safe. A recursive path predicate without a visited-list check will happily loop around a cycle forever looking for more solutions, since Prolog has no built-in cycle detection.

Prolog's own SLD resolution already performs depth-first search with backtracking over the proof tree.
Prolog's default search does not avoid cycles automatically; explicit visited-state tracking is needed for cyclic graphs.
Breadth-first search must be implemented explicitly in Prolog via a worklist or queue, since Prolog's native strategy is depth-first.
Iterative deepening combines DFS's low memory use with BFS-like completeness by repeatedly re-running depth-bounded searches.
A* search requires simulating a priority queue in Prolog, commonly via sorted lists or library(heaps).
A* ranks frontier nodes by f = g + h, combining cost-so-far with a heuristic estimate to the goal.
Running raw backtracking on infinite or cyclic state spaces without visited tracking can cause non-termination.