Comparing Search Algorithms for Pacman Game

Here is a short comparison of 4 search algorithms for Pacman Game:

1. Depth First Search
2. Breadth First Search
3. Uniform Cost Search
4. A-start Search with consistent heuristic

1a. Depth First Search and Big Maze.

Statistics:

• Path total cost = 210
• Time = 0.0 seconds
• Nodes Expanded = 390

1b. Depth First Search and Medium Maze.

Statistics:

• Path total cost = 130
• Time = 0.0 seconds
• Nodes Expanded = 146

2a. Breadth First Search and Big Maze.

Statistics:

• Path total cost = 210
• Time = 0.0 seconds
• Nodes Expanded = 620

2b. Breadth First Search and Medium Maze.

Statistics:

• Path total cost = 68
• Time = 0.0 seconds
• Nodes Expanded = 269

3a. Uniform Cost Search and Big Maze.

Statistics:

• Path total cost = 210
• Time = 0.0 seconds
• Nodes Expanded = 620

3b. Uniform Cost Search and Medium Maze.

Statistics:

• Path total cost = 68
• Time = 0.0 seconds
• Nodes Expanded = 269

4a. A-star and Big Maze. (Manhattan Distance)

Statistics:

• Path total cost = 210
• Time = 0.0 seconds
• Nodes expanded = 549

4b. A-star and Medium Maze. (Manhattan Distance)

Statistics:

• Path total cost = 68
• Time = 0.0 seconds
• Nodes Expanded = 221

Bonus:

Eating all the dotes using A-star. Expanded nodes equal 4110 with total cost 60, in comparison with UCS ~ 16,000 .

All sources can be found in github .