General Pacman AI: Game Agent With Tree Search, Adversarial Search And Model-Based RL Algorithms

Tree search algorithms like DFS, BFS and A* with plain logic can be easily implemented and works well in single-agent games, performing the property of completeness and optimality. Adversarial search algorithms like Minimax and Alpha-Beta Pruning perform an optimal result in zero-sum games like chess. Reinforcement Learning receives feedback in rewards, and the reward function defines the agent’s utility. All the learning is based on observed samples of outcomes to maximize expected rewards. This paper examines all the algorithms mentioned above to compare the correctness and optimality of the Pacman game. In the experiment, the paper illustrates why model-based reinforcement learning is optimal for the Pacman and meanwhile analyzes the correctness and complexity of all algorithms examined.