Reference no: EM132991127

CSE4002 Artificial Intelligence Fundamentals - La Trobe University

Solving the Towers of Hanoi Problem using State Space Search

Among many classic AI problems is the Towers of Hanoi problem; one of many versions of this, forms the basis of this assignment and is told as follows:

In a monastery in the deepest parts of Tibet there are three crystal columns and 64 golden rings. The rings are different sizes and rest over the columns. At the beginning of time, all of the rings rested on the leftmost column, and since then the monks have toiled ceaselessly trying to perfectly transfer the rings to their resting place on the final column.

The objective of this problem is to move the entire stack of rings from the first, to the last column, while obeying 3 simple rules:

1. Only one ring can be moved at time.

2. Each move consists of taking the upper ring from one of the stacks and placing it on the top of another stack or an empty pole.

3. A larger ring must not be placed on top of a smaller ring.

A state space representation of a 3 column, 2 ring, Towers of Hanoi problem is shown in the graph:

For this assignment, we will consider a Towers of Hanoi problem with 3 columns and 6 rings; although your final algorithm will most likely be capable of solving more complex versions. You will be expected to use the information given in this assignment to code two state space searching algorithms to achieve the objective state described above; an uninformed (Blind) search, and an informed (Heuristic) search.

Part 1 - Problem Analysis
Before writing the python code implementation of this problem, we must perform an analysis in order to conclude the best methodology.

Representing the Problem

How you choose to represent the states of any given problem can be critical in determining whether a solution can be found. Consider the following figure for our problem:

Scheme 1:
A state is represented by a list, where the list is of length 3 to represent the number of columns. Each index in this list contains the list of all rings stacked on this column; the stack order of each ring is represented by the rings index in each columns' inner list.

Scheme 2:
Another approach is to treat the rings individually, defining a rings class to store their size, current column, and index in that column.

Ring Class:
• Number/Size
• Column
• Column Index

Depending on how you decide to implement your future functions, scheme 2 may result in a cleaner, more readable implementation.

Questions:
1. What representation do you think will be best to implement? Why?

2. What is the optimal number of moves for a Towers of Hanoi problem with n columns and m rings?

3. Write pseudocode to perform the node expansion for this problem. (i.e. in the 8Puzzle we have the left, right, up, down movement functions)

4. Sketch the first four levels (i.e., root node plus next three levels) of the breadth-first search tree. Make sure that you indicate the state corresponding to each node, and

the operators that have been applied to move from one state to another. Do not include illegal states, or states that have already been visited.

5. As discussed in Lab 3, the heuristic function to a problem varies based on application.
For the 8-Puzzle problem, we utilized a count of all misplaced tiles; for the Shortest Path Problem we calculated the distance to the end node. What heuristic function can be used for the Towers of Hanoi Problem? (hint: the end goal is to have all rings on the final column)

6. As in question 4, Sketch the first four levels (i.e., root node plus next three levels) of the A* search tree.

Part 2 - Coding

As previously discussed, your Towers of Hanoi problem must be capable of solving for N Columns and R Rings. The user must enter N and R.

Your final code must implement both Breadth-First Search and A* Search solutions. Similar to your work solving the 8-Puzzle with BFS and A*, both solving algorithms must be implemented into the same file.

The output of your program must be a count of the total number of steps taken to reach the solution; and a path list, showing the rings positions at each level of the search. You need to try different N and R and then create a table (see below) to compare the results between these two algorithms. The compression can be based on the total number of steps taken to reach the solitons and time. You need to run each algorithm 5 times and report the best, worst and average.

Attachment:- Artificial Intelligence Fundamentals.rar