Classic Graph Search

In classical AI, problem-solving is often framed as a search problem. Whether navigating a map, resolving a puzzle, or planning a sequence of actions, the system represents states as nodes and transitions between states as edges in a graph. Searching this graph to find a path from an initial state to a goal state is a fundamental technique in AI.

While we will look at game-specific search algorithms like alpha-beta pruning in the chess chapter, here we cover the fundamentals of graph representation and pathfinding using Depth-First Search (DFS).

The examples for this chapter are in the directory source-code/search.

Graphs and Search Representation

A graph consists of a set of nodes (or vertices) connected by edges.

  • Directed Graph: The edges have a direction (e.g., from Node A to Node B).
  • Adjacency List: A common way to represent a graph in code, mapping each node to a list of its outgoing neighbors.
  • Cycles: A cycle occurs when a path starting from a node can lead back to the same node (e.g., B -> C -> D -> B). Cycles can cause infinite loops in search algorithms if not handled properly.

Depth-First Search (DFS)

Depth-First Search is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.

DFS is naturally recursive, which makes it elegant to implement. However, when searching general graphs (which may contain cycles), we must keep track of visited nodes to prevent infinite recursion.

Implementing Graph Search in TypeScript

Here we define a simple Graph implementation in TypeScript. We represent nodes with a unique string identifier and an optional note, and directed edges using an adjacency list.

  1 // graph.ts - Graph and DFS implementation in TypeScript
  2 
  3 /**
  4  * Represents a node in the graph structure.
  5  * Each node is uniquely identified by an ID and can have an optional note.
  6  */
  7 interface Node {
  8   /** Unique identifier for the node (e.g., "A", "B"). */
  9   id: string;
 10   /** A descriptive label or information associated with the node. */
 11   note: string;
 12 }
 13 
 14 /**
 15  * Represents an edge between two nodes.
 16  */
 17 interface Edge {
 18   from: string;
 19   to: string;
 20 }
 21 
 22 /**
 23  * A simple Graph data structure.
 24  */
 25 class Graph {
 26   /**
 27    * A collection of all nodes in the graph, mapped by their unique IDs.
 28    */
 29   private nodes: Map<string, Node> = new Map();
 30   private adjacencyList: Map<string, string[]> = new Map();
 31 
 32   /**
 33    * Adds a new node to the graph and initializes its entry in the adjacency list.
 34    * 
 35    * @param id - The unique identifier for the new node.
 36    * @param note - A description or metadata for the node.
 37    */
 38   addNode(id: string, note: string): void {
 39     this.nodes.set(id, { id, note });
 40     if (!this.adjacencyList.has(id)) {
 41       this.adjacencyList.set(id, []);
 42     }
 43   }
 44 
 45   /**
 46    * Adds a directed edge from one node to another.
 47    */
 48   addEdge(from: string, to: string): void {
 49     if (this.nodes.has(from) && this.nodes.has(to)) {
 50       this.adjacencyList.get(from)?.push(to);
 51     } else {
 52       console.error(`Error: One or both nodes (${from}, ${to}) do not exist.`);
 53     }
 54   }
 55 
 56   /**
 57    * Performs a Depth First Search (DFS) to find a path from startNode to goalNode.
 58    * @returns The path as an array of node IDs, or null if no path exists.
 59    */
 60   findPathDFS(startNode: string, goalNode: string): string[] | null {
 61     const visited = new Set<string>();
 62     const path: string[] = [];
 63 
 64     const dfs = (currentId: string): boolean => {
 65       visited.add(currentId);
 66       path.push(currentId);
 67 
 68       if (currentId === goalNode) {
 69         return true;
 70       }
 71 
 72       const neighbors = this.adjacencyList.get(currentId) || [];
 73       for (const neighbor of neighbors) {
 74         if (!visited.has(neighbor)) {
 75           if (dfs(neighbor)) {
 76             return true;
 77           }
 78         }
 79       }
 80 
 81       path.pop(); // Backtrack
 82       return false;
 83     };
 84 
 85     if (!this.nodes.has(startNode) || !this.nodes.has(goalNode)) {
 86       console.error("Error: Start or goal node does not exist.");
 87       return null;
 88     }
 89 
 90     const success = dfs(startNode);
 91     return success ? path : null;
 92   }
 93 
 94   /**
 95    * Prints the current graph structure for debugging.
 96    */
 97   printGraph(): void {
 98     console.log("Nodes:");
 99     this.nodes.forEach((node) => {
100       console.log(` - ${node.id}: ${node.note}`);
101     });
102     console.log("Edges:");
103     this.adjacencyList.forEach((neighbors, from) => {
104       console.log(` - ${from} -> ${neighbors.join(", ")}`);
105     });
106   }
107 }
108 
109 // --- Example Usage ---
110 
111 const myGraph = new Graph();
112 
113 // Set up example graph data
114 myGraph.addNode("A", "Start Node");
115 myGraph.addNode("B", "Intermediate Node 1");
116 myGraph.addNode("C", "Intermediate Node 2");
117 myGraph.addNode("D", "Goal Node");
118 myGraph.addNode("E", "Dead End");
119 
120 // Set up edges
121 myGraph.addEdge("A", "B");
122 myGraph.addEdge("A", "C");
123 myGraph.addEdge("B", "D");
124 myGraph.addEdge("C", "E");
125 myGraph.addEdge("E", "B"); // Cycle example
126 
127 console.log("Current Graph Structure:");
128 myGraph.printGraph();
129 
130 const start = "A";
131 const goal = "D";
132 console.log(`\nSearching for path from ${start} to ${goal}...`);
133 
134 const resultPath = myGraph.findPathDFS(start, goal);
135 
136 if (resultPath) {
137   console.log("Path found:", resultPath.join(" -> "));
138 } else {
139   console.log("No path found.");
140 }

How the Code Works

  1. Interfaces:

    • Node defines the structure for our vertices, capturing an id and a descriptive note.
    • Edge represents a directed connection between two nodes.

  2. Graph Class:

    • We use a Map<string, Node> to store the node metadata.
    • We use a Map<string, string[]> as our adjacency list to map each node ID to its list of neighbor node IDs.
    • addNode and addEdge populate these structures.

  3. Recursive DFS (findPathDFS):

    • visited is a Set<string> used to track nodes we have already visited during the search. This is critical to prevent infinite loops when the graph contains cycles.
    • path is an array of node IDs that tracks the current path from the start node.
    • The helper function dfs(currentId) is called recursively:
      • Mark currentId as visited and push it to path.
      • If currentId is the goalNode, return true (path found).
      • Otherwise, iterate through all of currentId’s neighbors. If a neighbor has not been visited, recursively call dfs on it.
      • If all neighbors are explored and the goal is not found, we backtrack by popping currentId from path and returning false.

Example Run

We construct a directed graph containing five nodes (A, B, C, D, and E) and the following directed edges:

  • A -> B and A -> C (branching point)
  • B -> D (leads to the goal)
  • C -> E (leads to a dead end)
  • E -> B (creates a cycle: A -> C -> E -> B -> D)

Here is the graph structure visualized:

1 graph TD
2     A[A: Start] --> B[B: Intermediate 1]
3     A --> C[C: Intermediate 2]
4     B --> D[D: Goal]
5     C --> E[E: Dead End]
6     E --> B

Running the Example

Make sure you install the necessary dependencies (we use tsx to run the TypeScript file directly):

1 npm install
2 npx tsx graph.ts

Output:

 1 Current Graph Structure:
 2 Nodes:
 3  - A: Start Node
 4  - B: Intermediate Node 1
 5  - C: Intermediate Node 2
 6  - D: Goal Node
 7  - E: Dead End
 8 Edges:
 9  - A -> B, C
10  - B -> D
11  - C -> E
12  - E -> B
13 
14 Searching for path from A to D...
15 Path found: A -> B -> D

Because DFS explores paths systematically, it immediately finds the path A -> B -> D. If we were to search for a path from C to D, DFS would traverse C -> E -> B -> D, successfully avoiding an infinite loop when crossing the cycle E -> B.

Wrap-up

Depth-First Search is a foundational search algorithm. While it is memory-efficient compared to Breadth-First Search (BFS) for deep trees, it does not guarantee finding the shortest path (which BFS or Dijkstra’s algorithm would). In the next chapter, we will build on search concepts to implement a chess engine using alpha-beta pruning, where the search space is dynamically evaluated to make intelligent game decisions.

Up next

Chess Game with Alpha-Beta Search