-
Notifications
You must be signed in to change notification settings - Fork 2
/
game_logic.py
244 lines (214 loc) · 9.1 KB
/
game_logic.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
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
import random
class Node:
def __init__(self, number, score, game_bank, depth, player, divided_by=None):
# Game parameters
self.number = number
self.score = score
self.game_bank = game_bank
# Useful for printing and the program
self.depth = depth
self.player = player
self.divided_by = divided_by
# Useful for alpha_beta
self.intermediate_heuristic = None
self.heuristic = None
# Children
self.children = []
def add_child(self, child):
self.children.append(child)
def is_leaf(self):
return self.number % 3 != 0 and self.number % 4 != 0 and self.number % 5 != 0
def other_player(self):
return "human" if self.player == "computer" else "computer"
def divide_by_3(self):
if self.number % 3 == 0:
new_number = self.number // 3
new_score = self.score + 1 if new_number % 2 == 0 else self.score - 1
new_game_bank = self.game_bank + 1 if new_number % 5 == 0 else self.game_bank
return Node(new_number, new_score, new_game_bank, self.depth + 1, self.other_player(), 3)
return None
def divide_by_4(self):
if self.number % 4 == 0:
new_number = self.number // 4
new_score = self.score + 1 if new_number % 2 == 0 else self.score - 1
new_game_bank = self.game_bank + 1 if new_number % 5 == 0 else self.game_bank
return Node(new_number, new_score, new_game_bank, self.depth + 1, self.other_player(), 4)
return None
def divide_by_5(self):
if self.number % 5 == 0:
new_number = self.number // 5
new_score = self.score + 1 if new_number % 2 == 0 else self.score - 1
new_game_bank = self.game_bank + 1 if new_number % 5 == 0 else self.game_bank
return Node(new_number, new_score, new_game_bank, self.depth + 1, self.other_player(), 5)
return None
def leaf_heuristic_eval(self, player, first_player, type):
result = self.score
if self.score % 2 == 0:
result -= self.game_bank
else:
result += self.game_bank
if result % 2 == 0: # winner is the first player
if first_player == player:
if type == 'max':
return 1
else:
return -1
else:
if type == 'max':
return -1
else:
return 1
else: # winner is the second player
if first_player == player:
if type == 'max':
return -1
else:
return 1
else:
if type == 'max':
return 1
else:
return -1
def minimax(self, player, first_player, type):
global visited_nodes_counter
visited_nodes_counter += 1
if self.is_leaf():
return self.leaf_heuristic_eval(player, first_player, type)
other_player = "computer" if player == "human" else "human"
if type == 'max':
max_eval = float('-inf')
best_child = None
for child in self.children:
eval = child.minimax(other_player, first_player, 'min')
if eval > max_eval:
max_eval = eval
best_child = child
return best_child.divided_by
else:
min_eval = float('inf')
best_child = None
for child in self.children:
eval = child.minimax(other_player, first_player, 'max')
if eval < min_eval:
min_eval = eval
best_child = child
return best_child.divided_by
def alpha_beta(self, ancestor_intermediate_value, player, first_player, type):
global visited_nodes_counter
visited_nodes_counter += 1
if self.is_leaf():
self.heuristic = self.leaf_heuristic_eval(player, first_player, type)
return self.heuristic
#Check if we can give an intermediate heuristic
no_heuristic_child = False
heuristic_child = False
heuristics = []
for child in self.children:
if child.heuristic != None:
heuristic_child = True
heuristics.append(child.heuristic)
else:
no_heuristic_child = True
if no_heuristic_child and heuristic_child:
#Give an intermediate heuristic
if type == 'max':
self.intermediate_heuristic = max(heuristics)
else:
self.intermediate_heuristic = min(heuristics)
# Check if we can cut off
if type == 'max':
if self.intermediate_heuristic != None and ancestor_intermediate_value != None:
if self.intermediate_heuristic >= ancestor_intermediate_value:
# Beta cut-off
self.heuristic = self.intermediate_heuristic
return self.heuristic
else:
if self.intermediate_heuristic != None and ancestor_intermediate_value != None:
if self.intermediate_heuristic <= ancestor_intermediate_value:
self.heuristic = self.intermediate_heuristic
# Alpha cut-off
return self.heuristic
other_player = "computer" if player == "human" else "human"
if type == 'max':
max_eval = float('-inf')
best_child = None
for child in self.children:
eval = child.alpha_beta(self.intermediate_heuristic, other_player, first_player, 'min')
if eval > max_eval:
max_eval = eval
best_child = child
self.heuristic = max_eval
return best_child.divided_by
else:
min_eval = float('inf')
best_child = None
for child in self.children:
eval = child.alpha_beta(self.intermediate_heuristic, other_player, first_player, 'max')
if eval < min_eval:
min_eval = eval
best_child = child
self.heuristic = min_eval
return best_child.divided_by
class Game:
@staticmethod
def generate_start_numbers():
numbers = []
for _ in range(5):
number = random.randint(40000, 50000)
while (number in numbers) or (number % 3 != 0) or (number % 4 != 0) or (number % 5 != 0):
number = random.randint(40000, 50000)
numbers.append(number)
return numbers
def __init__(self, first_player, algorithm, initial_selected_number):
self.first_player = first_player
other_player = "computer" if first_player == "human" else "human"
self.algorithm = algorithm
self.state = Node(initial_selected_number, 0, 0, 0, other_player)
def create_tree(self):
queue = [self.state]
while queue:
current_node = queue.pop(0)
children = [current_node.divide_by_3(), current_node.divide_by_4(), current_node.divide_by_5()]
for child in children:
if child:
current_node.add_child(child)
queue.append(child)
def print_tree(self):
queue = [self.state]
current_depth = 0
print("Depth 0 (root): ", end="")
while queue:
current_node = queue.pop(0)
if current_node.depth > current_depth:
current_depth = current_node.depth
print(f"\nDepth {current_depth} ({current_node.player}): ", end="")
if current_node.player == "human":
print(" ", end="")
print(f"({current_node.number}|{current_node.score}|{current_node.game_bank})", end="")
if current_depth > 0:
print(f"[{current_node.divided_by}] ", end="")
for child in current_node.children:
queue.append(child)
print()
def play(self, number):
new_state = None
if number == 3:
new_state = self.state.divide_by_3()
elif number == 4:
new_state = self.state.divide_by_4()
elif number == 5:
new_state = self.state.divide_by_5()
if new_state is not None:
new_state.depth = 0
self.state = new_state
else:
print("Invalid move! Please choose a valid divisor.")
def get_computer_play(self):
global visited_nodes_counter
visited_nodes_counter = 0
if self.algorithm == "minimax":
divisor = self.state.minimax(player='computer', first_player=self.first_player, type='max')
return visited_nodes_counter, divisor
elif self.algorithm == "alpha-beta":
divisor = self.state.alpha_beta(ancestor_intermediate_value=None, player='computer', first_player=self.first_player, type='max')
return visited_nodes_counter, divisor