-
Notifications
You must be signed in to change notification settings - Fork 0
/
functions.py
179 lines (144 loc) · 7.64 KB
/
functions.py
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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
import classes
import copy
import Queue
##############################################################################################################################################
# Includes functions that reoccur in all searche types. Include functions that will expand nodes and add them to a frontier,
# functions that will create a new state based on an action performed on a previous node, and checking a node against a list of explored nodes.
###############################################################################################################################################
####################################################################
# Actions are encoded as:
# 1: Send one chicken across
# 2: Send two chickens across
# 3: Send one wolf across
# 4: Send one wolf and one chicken across
# 5: Send two wolves across
####################################################################
# Checks if two banks have equal values
def checkBanksEqual(firstBank, secondBank):
if (firstBank.chickens == secondBank.chickens and firstBank.wolves == secondBank.wolves and firstBank.boat == secondBank.boat):
return True
else:
return False
# Checks if two states have equal configurations (disregards the list of previous actions)
def checkStatesEqual(firstState, secondState):
if (checkBanksEqual(firstState.leftBank, secondState.leftBank) and checkBanksEqual(firstState.rightBank, secondState.rightBank)):
return True
else:
return False
# Checks a state against a list of explored states and returns whether or not it exists in it
def checkNotExplored(added, newState):
for i in added:
if (checkStatesEqual(newState, i)):
return False
return True
# Creates a new state that represents the result of an action performed on a previous state. Actions are encoded as above
def createNewState(action, currentState):
newLeftBoat = newRightBoat = 0
# Switches the boat to the opposite side
if (currentState.leftBank.boat == 1):
newLeftBoat = 0
newRightBoat = 1
else:
newLeftBoat = 1
newRightBoat = 0
currentChickens = currentWolves = oppositeChickens = oppositeWolves = newCurrentChickens = newCurrentWolves = newOppositeChickens = newOppositeWolves = newState = None
# Current side = the side the boat originally was on before being switched over
if (currentState.leftBank.boat):
currentChickens = currentState.leftBank.chickens
currentWolves = currentState.leftBank.wolves
oppositeChickens = currentState.rightBank.chickens
oppositeWolves = currentState.rightBank.wolves
else:
currentChickens = currentState.rightBank.chickens
currentWolves = currentState.rightBank.wolves
oppositeChickens = currentState.leftBank.chickens
oppositeWolves = currentState.leftBank.wolves
# Change the values for chickens and wolves for each side based on the action
if (action == 1):
newCurrentChickens = currentChickens - 1
newCurrentWolves = currentWolves
newOppositeChickens = oppositeChickens + 1
newOppositeWolves = oppositeWolves
elif (action == 2):
newCurrentChickens = currentChickens - 2
newCurrentWolves = currentWolves
newOppositeChickens = oppositeChickens + 2
newOppositeWolves = oppositeWolves
elif (action == 3):
newCurrentChickens = currentChickens
newCurrentWolves = currentWolves - 1
newOppositeChickens = oppositeChickens
newOppositeWolves = oppositeWolves + 1
elif (action == 4):
newCurrentChickens = currentChickens - 1
newCurrentWolves = currentWolves - 1
newOppositeChickens = oppositeChickens + 1
newOppositeWolves = oppositeWolves + 1
else:
newCurrentChickens = currentChickens
newCurrentWolves = currentWolves - 2
newOppositeChickens = oppositeChickens
newOppositeWolves = oppositeWolves + 2
# Create the state
if (currentState.leftBank.boat):
newState = classes.gameState(newCurrentChickens, newCurrentWolves, newLeftBoat, newOppositeChickens, newOppositeWolves, newRightBoat, currentState.prevStates)
else:
newState = classes.gameState(newOppositeChickens, newOppositeWolves, newLeftBoat, newCurrentChickens, newCurrentWolves, newRightBoat, currentState.prevStates)
# Append the action to the list of previous states
newState.prevStates.append(action)
return newState
# Takes a node and a frontier and an explored list and expands the node.
# goalState is input as an argument if astar search is being used. This is to calculate the heuristic for the new nodes by comparing their values
# to the goal state
def expandNode(added, frontier, currentState, goalState = None):
# Check for all valid actions
validActions = currentState.checkValidSuccessors()
# Create a new state for every action that can be performed on the node. Add it if has not been explored before
if (validActions[0]):
newState = createNewState(1, currentState)
if (checkNotExplored(added, newState)):
added.append(newState)
if (goalState != None):
# If a goal state is input (aka if astar search is being used), calculate the heuristic and add to the queue as a tuple
newHeuristic = abs(goalState.leftBank.chickens - newState.leftBank.chickens) + abs(goalState.rightBank.wolves - newState.rightBank.wolves) + 3 * len(newState.prevStates)
frontier.put((newHeuristic, newState))
else:
# Otherwise, just add the new state
frontier.put(newState)
if (validActions[1]):
newState = createNewState(2, currentState)
if (checkNotExplored(added, newState)):
added.append(newState)
if (goalState != None):
newHeuristic = abs(goalState.leftBank.chickens - newState.leftBank.chickens) + abs(goalState.rightBank.wolves - newState.rightBank.wolves) + 3 * len(newState.prevStates)
frontier.put((newHeuristic, newState))
else:
frontier.put(newState)
if (validActions[2]):
newState = createNewState(3, currentState)
if (checkNotExplored(added, newState)):
added.append(newState)
if (goalState != None):
newHeuristic = abs(goalState.leftBank.chickens - newState.leftBank.chickens) + abs(goalState.rightBank.wolves - newState.rightBank.wolves) + 3 * len(newState.prevStates)
frontier.put((newHeuristic, newState))
else:
frontier.put(newState)
if (validActions[3]):
newState = createNewState(4, currentState)
if (checkNotExplored(added, newState)):
added.append(newState)
if (goalState != None):
newHeuristic = abs(goalState.leftBank.chickens - newState.leftBank.chickens) + abs(goalState.rightBank.wolves - newState.rightBank.wolves) + 3 * len(newState.prevStates)
frontier.put((newHeuristic, newState))
else:
frontier.put(newState)
if (validActions[4]):
newState = createNewState(5, currentState)
if (checkNotExplored(added, newState)):
added.append(newState)
if (goalState != None):
newHeuristic = abs(goalState.leftBank.chickens - newState.leftBank.chickens) + abs(goalState.rightBank.wolves - newState.rightBank.wolves) + 3 * len(newState.prevStates)
frontier.put((newHeuristic, newState))
else:
frontier.put(newState)
return added, frontier