AI: Pacman, Search

I found an online tutorial, http://ai.berkeley.edu, on artificial intelligence.  Actually, it was more of a course, but anyway….

Before a machine can begin to make decisions, it needs to find the best/correct answer to the question/problem it is trying to solve.  This first part is done with search algorithms.  Here, the problems are presented in the form of a maze.  The heat map shows which part of the maze the algorithm searched first before finding a path that reaches the goal.

Depth First Search

Depth first search will search all the way down the branch until it reaches a dead end before returning to the previous fork and searching the next branch.  This can be inefficient if the goal is located on a different branch near the beginning.  The algorithm will have to search every dead end before returning to the fork that leads to the correct path.

 

Breadth First Search

Breadth first search looks down all branches simultaneously, searching the shortest distance first.  This algorithm is efficient if the goal is shallow (close to the starting position), but it can be inefficient if the goal is very deep (near the bottom of the search tree).

 

Uniform Cost Search

Uniform cost search is similar to breadth first search in the fact that it will search the shallowest paths first.  However, rather than simply using the distance or the number of nodes from the starting position, it can take in a cost function in order to assign search priority.  The algorithm will only search as deeply only as long as the cost of that path is the cheapest.

In this example, there are food pellets on the right side of the map, so the cost for searching the left side of the map was made more expensive.  Pac-Man did not begin searching the left side of the map until he finished searching the right side.

In this example, there were ghosts starting on the right side of the map.   the cost function for searching the right side of the map was made more expensive.  Pac-Man avoided the right side and the ghosts.

A Star Search

A* search improves upon uniform cost search by adding a heuristic.  Here Pac-Man uses the Manhattan distance to the goal and prioritizes the positions that lead closer to the goal.

Find all the food.  In previous scenarios, Pac-Man only had to find a path from the starting position to the goal.  In this case, Pac-Man has to find a path to all of the food pellets.  The algorithm uses the sam tree search as before, where each node represent a game state, but this time, each node contains information on the number of food left on the map in addition to the position of Pac-Man.

Find the shortest path.  Again, this uses a search tree but also include a distance heuristic.

Non-Optimized

Sometimes a complicated algorithm is not necessary.  In this example, Pac-Man will move towards the nearest food pellet.  This works fairly well.  The algorithm is fast and effective, even though it is not able to find the shortest path.

Results

Provisional grades
==================
Question q1: 3/3
Question q2: 3/3
Question q3: 3/3
Question q4: 3/3
Question q5: 3/3
Question q6: 3/3
Question q7: 4/4
Question q8: 3/3
------------------
Total: 25/25

Disclaimer

The materials shown here were based off of a free online course. As such, I am showing only the results and not the code.  Find out more at http://ai.berkeley.edu.

# Licensing Information: You are free to use or extend these projects for
# educational purposes provided that (1) you do not distribute or publish
# solutions, (2) you retain this notice, and (3) you provide clear
# attribution to UC Berkeley, including a link to http://ai.berkeley.edu.

 

Leave a Reply

Your email address will not be published. Required fields are marked *

CommentLuv badge