/Pacman-Search

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

Primary LanguagePython

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.