junthbasnet / pacman-search

Array of AI Search algorithms is employed to playing Pac-Man ⍩⃝.

Pacman Search

---

An array of AI techniques is employed to playing Pac-Man . Following Informed, Uninformed and Adversarial Search algorithms are implemented in this project.

• Informed Search:
  • Breadth First Search
  • Depth First Search
  • Uniform Cost Search
• Uninformed Search:
  • A* Search
• Adversarial Search:
  • Minimax Search
  • Alpha-Beta Pruning

1. Depth First Search

Expand deepest node.

cd Informed and Uninformed Search
python pacman.py -l mediumMaze -p SearchAgent -z .8 --frameTime 0.05

2. Breadth First Search

Expand shallowest node.

cd Informed and Uninformed Search
python pacman.py -l mediumMaze -p SearchAgent -a fn=bfs -z .8 --frameTime 0.05

3. Uniform Cost Search

Expand least cost node.

cd Informed and Uninformed Search
python pacman.py -l mediumMaze -p SearchAgent -a fn=ucs -z .8 --frameTime 0.05

4. A* Search

Minimize the total estimated solution cost.

cd Informed and Uninformed Search
python pacman.py -l mediumMaze -p SearchAgent -a fn=astar,heuristic=manhattanHeuristic -z .8 --frameTime 0.05

5. Adversarial Search (Minimax)

Max maximizes results, Min minimizes results. Compute each node’s minimax value’s the best achievable utility against an optimal adversary.

cd Adversarial Search
python pacman.py -p MinimaxAgent -l smallClassic -a depth=2 --frameTime 0

If you lose, try increasing depth because depth matters.

6. Alpha-Beta Pruning

Minimax: generates the entire game search space. Alpha-Beta algorithm: prune large chunks of the trees.

cd Adversarial Search
python pacman.py -p AlphaBetaAgent -l smallClassic -a depth=3 --frameTime 0

If you lose, try increasing depth because depth matters.

References

UC Berkeley's introductory artificial intelligence course, CS 188.