Oct 13, 2019
Pacman Search
Source Code is available at:
Github: Pacman Search
🎮 An array of AI techniques is employed to playing Pac-Man. Informed, Uninformed and Adversarial Search algorithms are implemented in this project.
1️⃣ Informed Search Algorithm
😮 Informed Search Algorithm implemented in this project are Depth First Search(DFS), Breadth First Search(BFS) and Uniform Cost Search(UCS).
🅰 Depth First Search
Expand deepest node.
🅱 Breadth First Search
Expand shallowest node.
🅾 Uniform Cost Search
Expand least cost node.
2️⃣ Uninformed Search Algorithm
😃 Uninformed Search Algorithm implemented in this project is A* Search Algorithm.
🅰 A* Search Algorithm
Minimize the total estimated solution cost.
3️⃣ Adversarial Search Algorithm
😍 Adversarial Search algorithm implemented in this project are Minimax Search algorithm and Alpha-Beta Pruning.
🅰 Minimax Search Algorithm
Max maximizes results, Min minimizes results. Compute each node’s minimax value’s the best achievable utility against an optimal adversary.
🅱 Alpha-Beta Pruning
Minimax: generates the entire game search space. Alpha-Beta algorithm: prune large chunks of the trees.
👀 References
▶️📝 UC Berkeley's introductory artificial intelligence course, CS 188.