A Masterball must be represented as an array of arrays with integer values representing the color of the tile in each position:
A solved masterball must look like this:
[ [0, 1, 2, 3, 4, 5, 6, 7],
[0, 1, 2, 3, 4, 5, 6, 7],
[0, 1, 2, 3, 4, 5, 6, 7],
[0, 1, 2, 3, 4, 5, 6, 7]
]
In [3]:
'''
This variables MUST not be changed.
They represent the movements of the masterball.
'''
R_0 = "Right 0"
R_1 = "Right 1"
R_2 = "Right 2"
R_3 = "Right 3"
V_0 = "Vertical 0"
V_1 = "Vertical 1"
V_2 = "Vertical 2"
V_3 = "Vertical 3"
V_4 = "Vertical 4"
V_5 = "Vertical 5"
V_6 = "Vertical 6"
V_7 = "Vertical 7"
R_i moves the ith row to the right. For instance, R_2 applied to the solved state will produce:
[ [0, 1, 2, 3, 4, 5, 6, 7],
[0, 1, 2, 3, 4, 5, 6, 7],
[7, 0, 1, 2, 3, 4, 5, 6],
[0, 1, 2, 3, 4, 5, 6, 7]
]
V_i performs a clockwise vertical move starting with the ith column
V_1 applied to the above state will produce:
[ [0, 4, 3, 2, 1, 5, 6, 7],
[0, 3, 2, 1, 0, 5, 6, 7],
[7, 4, 3, 2, 1, 4, 5, 6],
[0, 4, 3, 2, 1, 5, 6, 7]
]
In [3]:
import search
class MasterballProblem(search.SearchProblem):
def __init__(self, startState):
'''
Store the initial state in the problem representation and any useful
data.
Here are some examples of initial states:
[[0, 1, 4, 5, 6, 2, 3, 7], [0, 1, 3, 4, 5, 6, 3, 7], [1, 2, 4, 5, 6, 2, 7, 0], [0, 1, 4, 5, 6, 2, 3, 7]]
[[0, 7, 4, 5, 1, 6, 2, 3], [0, 7, 4, 5, 0, 5, 2, 3], [7, 6, 3, 4, 1, 6, 1, 2], [0, 7, 4, 5, 1, 6, 2, 3]]
[[0, 1, 6, 4, 5, 2, 3, 7], [0, 2, 6, 5, 1, 3, 4, 7], [0, 2, 6, 5, 1, 3, 4, 7], [0, 5, 6, 4, 1, 2, 3, 7]]
'''
self.expanded = 0
### your code here ###
pass
def isGoalState(self, state):
'''
Define when a given state is a goal state (A correctly colored masterball)
'''
### your code here ###
pass
def getStartState(self):
'''
Implement a method that returns the start state according to the SearchProblem
contract.
'''
### your code here ###
pass
def getSuccessors(self, state):
'''
Implement a successor function: Given a state from the masterball
return a list of the successors and their corresponding actions.
This method *must* return a list where each element is a tuple of
three elements with the state of the masterball in the first position,
the action (according to the definition above) in the second position,
and the cost of the action in the last position.
Note that you should not modify the state.
'''
self.expanded += 1
### your code here ###
pass
In [2]:
def iterativeDeepeningSearch(problem):
### your code here ###
return []
def aStarSearch(problem, heuristic):
### your code here ###
return []
Evaluate it to see what is the maximum depth that it could explore in a reasonable time. Report the results.
Implement at least two admissible and consistent heuristics. Compare A* using the heuristics against IDS calculating the number of expanded nodes and the effective branching factor, in the same way as it is done in figure 3.29 of [Russell10].
In [5]:
def myHeuristic(state):
### your code here ###
return 0
Now apply the develop functions to solve the Masterball problem.
In [6]:
problem = MasterballProblem([ [0, 4, 3, 2, 1, 5, 6, 7],
[0, 3, 2, 1, 0, 5, 6, 7],
[7, 4, 3, 2, 1, 4, 5, 6],
[0, 4, 3, 2, 1, 5, 6, 7]])
print(iterativeDeepeningSearch(problem))
print(aStarSearch(problem, myHeuristic))