Pacman AI, Part I

Introduction

This is the first part of the Pacman AI project. In this part of the project, I implemented several search algorithm, such as DFS, BFS, A*, UCS, Sub-optimal Search etc. In this post, I will also discuss how these algorithms can turn into each other under certain conditions.

Implementation of Algorithms

Screen Shot 2017-10-25 at 11.19.50 PM.png

The implementation of these algorithms are all based on the graph search, and their differences are just that they have different priorities for unvisited paths/nodes to enqueue or dequeue.

Discussion

Two search algorithms are defined to be equivalent if and only if they expand the same nodes in the same order and return the same path.

  • How can we make Uniform Cost Search equivalent to Breadth-First Search?

          We can set the cost dij = a, a>0.

  • How can we make Uniform Cost Search equivalent to Depth-First Search?

          We can set the cost dij = a, a<0.

  • How can we make a new UCS with cost dij equivalent to a know UCS with cij?

          We can set dij = a*cij, a>0.

  • How to choose costs dij that make running Uniform Cost Search algorithm with these costs dij equivalent to running Greedy Search with the original costs cij and heuristic function h?

          We can set dij = h(j) − h(i).

  • How to choose the costs dij that make running Uniform Cost Search algorithm with these costs dij equivalent to running A* Search with the original costs cij and heuristic function h.

          We can set dij = cij + h(j) − h(i).

As we may see from the above comparison, all these search algorithms are essentially under the same logic. The only difference between each other is how they decide the priority of the nodes to search.

Conclusion

This is the end of Pacman AI, Part I.

Readers of the post should not copy any of my code for their own course assignment, but feel free to be inspired and come up with your own ones. I do not want to upload code file to GitHub because that makes my code handy to copy and paste.

 

AI

Arthur Zhang View All →

A current master student in WUSTL, department of Electrical and System Engineering.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: