kami2-solver/deterministic_search.py at master · alexander-jiang/kami2-solver · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
import util
import copy

class DepthFirstSearch:
    def solve(self, problem, find_all_solutions=False):
        """
        NOTE find_all_solutions won't necessarily find all possible solutions since the
        visited set only checks the state, so transpositions (i.e. different action sequences that
        result in the same board state) will be skipped on subsequent runs
        """
        # actions and total_cost will be set if there is a path,
        # otherwise, they will still be None
        self.actions = None
        self.total_cost = None
        self.num_states_explored = 0 # for comparison against UCS

        start_state = problem.start_state()
        frontier = [([], start_state),]
        visited = set([])
        actions_tried = []

        while len(frontier) > 0:
            prev_actions, state = frontier.pop()
            actions_tried.append(prev_actions)
            visited.add(state)
            self.num_states_explored += 1
            if self.num_states_explored % 250 == 0:
                print("explored", self.num_states_explored, "states")

            # print("---")
            # print("state: (prev actions were: %s)" % (prev_actions, ))
            # print("    ", state.graph)
            # print("    ", state.node_colors)
            # print("    moves left: %d" % (state.moves_left,))
            if problem.is_terminal_state(state) == 1:
                print("solution found! ", prev_actions)
                print("num states explored: ", self.num_states_explored)
                problem.actions = self.actions
                problem.num_states_explored = self.num_states_explored
                # print("explored these actions:")
                # for action_tried in actions_tried:
                #     print(action_tried)

                if find_all_solutions: continue
                else: break
            if problem.is_terminal_state(state) == -1:
                continue
            for (action, next_state, cost) in problem.actions_and_costs(state):
                if (next_state not in visited and
                    problem.is_terminal_state(next_state) != -1):
                        actions = copy.deepcopy(prev_actions)
                        actions.append(action)
                        frontier.append((actions, next_state))

class UniformCostSearch:
    def solve(self, problem):
        # actions and total_cost will be set if there is a path,
        # otherwise, they will still be None
        self.actions = None
        self.total_cost = None
        self.num_states_explored = 0 # to evaluate heuristic effectiveness

        frontier = util.PriorityQueue()
        # for backtracking (extracting solution): map state -> action, previous state
        predecessor = {}
        visited = set([])

        start_state = problem.start_state()
        frontier.update(start_state, 0)
        previous_g_cost = None
        previous_moves_left = None
        while not frontier.empty():
            state, g_cost = frontier.remove_min()

            # print("min cost state from frontier:")
            # prev_actions = []
            # this_state = state
            # while this_state != start_state:
            #     action, this_state = predecessor[this_state]
            #     prev_actions.insert(0, action)
            # print(prev_actions)
            # print("g_cost =", g_cost)

            visited.add(state)
            self.num_states_explored += 1
            if previous_g_cost != g_cost:
                previous_g_cost = g_cost
                print(f"new g cost: {previous_g_cost}")
            if previous_moves_left != state.moves_left:
                previous_moves_left = state.moves_left
                print(f"new moves left: {previous_moves_left}")

            if self.num_states_explored % 250 == 0:
                print("explored", self.num_states_explored, "states")

            if problem.is_terminal_state(state) == 1:
                print("solution found!")
                self.total_cost = g_cost
                self.actions = []
                while state != start_state:
                    action, state = predecessor[state]
                    self.actions.insert(0, action)
                problem.actions = self.actions
                problem.num_states_explored = self.num_states_explored
                print("actions: ", self.actions)
                print("num states explored: ", self.num_states_explored)
                # print("explored these actions:")
                # for state in visited:
                #     prev_actions = []
                #     while state != start_state:
                #         action, state = predecessor[state]
                #         prev_actions.insert(0, action)
                #     print(prev_actions)
                break
            if problem.is_terminal_state(state) == -1:
                continue

            for (action, next_state, next_cost) in problem.actions_and_costs(state):
                if (next_state not in visited and
                    problem.is_terminal_state(next_state) != -1):
                        # If we've found a better path, update the predecessor
                        if frontier.update(next_state, g_cost + next_cost):
                            predecessor[next_state] = (action, state)