-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathlogic.py
409 lines (346 loc) · 14.3 KB
/
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
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
"""
Created: 29 October 2023 18:30
Author: Martins Anerua
Notes:
1. A state is a particular unique game board
2. state[9] represents the player whose turn it is to play (not the one whose play resulted in the current game state)
3. Solitude is the Maximizer and human player is the Minimizer
"""
from typing import Tuple, List
import copy
import math
PLAY = 0
WIN = 1
LOSS = 2
DRAW = 3
ERROR = -1
def is_draw(state, mini, maxi):
"""
Parameters
----------
state : list
A list of length 10, representing a particular state of the game.
mini : str
The Minimizer player.
maxi : str
The Maximizer player.
Returns
-------
bool
Returns True if the game, as represented by state, is a draw and returns False otherwise.
"""
if is_win(state, mini) or is_win(state, maxi):
return False
else:
return '-' not in state
def is_win(state, player):
"""
Parameters
----------
state : list
A list of length 10, representing a particular state of the game.
player : str
A string of one character, representing the player whose win status is to be checked.
Returns
-------
bool
Returns True if the game results in a win for player, and returns False if it doesn't.
"""
condition1 = ((player == state[0]) and (player == state[1]) and (player == state[2]))
condition2 = ((player == state[3]) and (player == state[4]) and (player == state[5]))
condition3 = ((player == state[6]) and (player == state[7]) and (player == state[8]))
condition4 = ((player == state[0]) and (player == state[3]) and (player == state[6]))
condition5 = ((player == state[1]) and (player == state[4]) and (player == state[7]))
condition6 = ((player == state[2]) and (player == state[5]) and (player == state[8]))
condition7 = ((player == state[0]) and (player == state[4]) and (player == state[8]))
condition8 = ((player == state[2]) and (player == state[4]) and (player == state[6]))
return condition1 or condition2 or condition3 or condition4 or condition5 or condition6 or condition7 or condition8
def is_a_way(state, player, mini, maxi):
"""
Parameters
----------
state : list
A list of length 10, representing a particular state of the game.
player : str
A string of one character, representing the player whose status is to be checked.
Returns
-------
bool
Returns True if there is ONLY one a way to win for player in the current game state. Returns False otherwise
"""
if end_state(state, mini, maxi) or is_two_ways(state, player, mini, maxi):
return False
else:
condition1 = (('-' == state[0]) and (player == state[1]) and (player == state[2])) or (
(player == state[0]) and ('-' == state[1]) and (player == state[2])) or (
(player == state[0]) and (player == state[1]) and ('-' == state[2]))
condition2 = (('-' == state[3]) and (player == state[4]) and (player == state[5])) or (
(player == state[3]) and ('-' == state[4]) and (player == state[5])) or (
(player == state[3]) and (player == state[4]) and ('-' == state[5]))
condition3 = (('-' == state[6]) and (player == state[7]) and (player == state[8])) or (
(player == state[6]) and ('-' == state[7]) and (player == state[8])) or (
(player == state[6]) and (player == state[7]) and ('-' == state[8]))
condition4 = (('-' == state[0]) and (player == state[3]) and (player == state[6])) or (
(player == state[0]) and ('-' == state[3]) and (player == state[6])) or (
(player == state[0]) and (player == state[3]) and ('-' == state[6]))
condition5 = (('-' == state[1]) and (player == state[4]) and (player == state[7])) or (
(player == state[1]) and ('-' == state[4]) and (player == state[7])) or (
(player == state[1]) and (player == state[4]) and ('-' == state[7]))
condition6 = (('-' == state[2]) and (player == state[5]) and (player == state[8])) or (
(player == state[2]) and ('-' == state[5]) and (player == state[8])) or (
(player == state[2]) and (player == state[5]) and ('-' == state[8]))
condition7 = (('-' == state[0]) and (player == state[4]) and (player == state[8])) or (
(player == state[0]) and ('-' == state[4]) and (player == state[8])) or (
(player == state[0]) and (player == state[4]) and ('-' == state[8]))
condition8 = (('-' == state[2]) and (player == state[4]) and (player == state[6])) or (
(player == state[2]) and ('-' == state[4]) and (player == state[6])) or (
(player == state[2]) and (player == state[4]) and ('-' == state[6]))
return condition1 or condition2 or condition3 or condition4 or condition5 or condition6 or condition7 or condition8
def is_two_ways(state, player, mini, maxi):
"""
Parameters
----------
state : list
A list of length 10, representing a particular state of the game.
player : str
A string of one character, representing the player whose status is to be checked.
Returns
-------
bool
Returns True if there are AT LEAST two ways to win for player in the current game state. Returns False otherwise
"""
if end_state(state, mini, maxi):
return False
else:
condition1 = (('-' == state[0]) and (player == state[1]) and (player == state[2])) or (
(player == state[0]) and ('-' == state[1]) and (player == state[2])) or (
(player == state[0]) and (player == state[1]) and ('-' == state[2]))
condition2 = (('-' == state[3]) and (player == state[4]) and (player == state[5])) or (
(player == state[3]) and ('-' == state[4]) and (player == state[5])) or (
(player == state[3]) and (player == state[4]) and ('-' == state[5]))
condition3 = (('-' == state[6]) and (player == state[7]) and (player == state[8])) or (
(player == state[6]) and ('-' == state[7]) and (player == state[8])) or (
(player == state[6]) and (player == state[7]) and ('-' == state[8]))
condition4 = (('-' == state[0]) and (player == state[3]) and (player == state[6])) or (
(player == state[0]) and ('-' == state[3]) and (player == state[6])) or (
(player == state[0]) and (player == state[3]) and ('-' == state[6]))
condition5 = (('-' == state[1]) and (player == state[4]) and (player == state[7])) or (
(player == state[1]) and ('-' == state[4]) and (player == state[7])) or (
(player == state[1]) and (player == state[4]) and ('-' == state[7]))
condition6 = (('-' == state[2]) and (player == state[5]) and (player == state[8])) or (
(player == state[2]) and ('-' == state[5]) and (player == state[8])) or (
(player == state[2]) and (player == state[5]) and ('-' == state[8]))
condition7 = (('-' == state[0]) and (player == state[4]) and (player == state[8])) or (
(player == state[0]) and ('-' == state[4]) and (player == state[8])) or (
(player == state[0]) and (player == state[4]) and ('-' == state[8]))
condition8 = (('-' == state[2]) and (player == state[4]) and (player == state[6])) or (
(player == state[2]) and ('-' == state[4]) and (player == state[6])) or (
(player == state[2]) and (player == state[4]) and ('-' == state[6]))
conditions = [condition1, condition2, condition3, condition4, condition5, condition6, condition7, condition8]
return conditions.count(True) > 1
def end_state(state, mini, maxi):
"""
Parameters
----------
state : list
A list of length 10, representing a particular state of the game.
mini : str
The Minimizer player.
maxi : str
The Maximizer player.
Returns
-------
bool
Returns True if the state is a win state for any player or a draw state. Returns False otherwise.
"""
return is_draw(state, mini, maxi) or is_win(state, mini) or is_win(state, maxi)
def has_center(state, focus):
"""
Parameters
----------
state : list
A list of length 10, representing a particular state of the game.
focus : str
A string of one character, representing the player whose status is to be checked.
Returns
-------
bool
Returns True if 'focus' is present in the center position of 'state'. Returns False otherwise.
"""
return state[4] == focus
def has_corner(state, focus):
"""
Parameters
----------
state : list
A list of length 10, representing a particular state of the game.
focus : str
A string of one character, representing the player whose status is to be checked.
Returns
-------
bool
Returns True if 'focus' is present in at least one of the corner positions of 'state'. Returns False otherwise.
"""
return (state[0] == focus) or (state[2] == focus) or (state[6] == focus) or (state[8] == focus)
def static_value(state, mini, maxi):
"""
Parameters
----------
state : list
A list of length 10, representing a particular state of the game.
mini : str
The Minimizer player.
maxi : str
The Maximizer player.
Returns
-------
value : int
Returns the static value of 'state'. This ranges from +100 to -100 inclusively.
"""
value = 0
if is_win(state, maxi):
value = 100
else:
if is_win(state, mini):
value = -100
else:
if is_draw(state, mini, maxi):
value = 0
else:
if is_two_ways(state, maxi, mini, maxi):
value += 50
if is_a_way(state, maxi, mini, maxi):
value += 10
if has_center(state, maxi):
value += 5
if has_corner(state, maxi):
value += 1
if is_two_ways(state, mini, mini, maxi):
value -= 50
if is_a_way(state, mini, mini, maxi):
value -= 10
if has_center(state, mini):
value -= 5
if has_corner(state, mini):
value -= 1
return value
def get_all_next_moves(state, mini, maxi):
"""
Parameters
----------
state : list
A list of length 10, representing a particular state of the game.
mini : str
The Minimizer player.
maxi : str
The Maximizer player.
Returns
-------
moves : list
Returns a list of all valid possible states that differ from 'state' by one move.
"""
moves = []
if end_state(state, mini, maxi):
return moves
else:
indices = []
for _ in range(9):
if state[_] == '-':
indices.append(_)
player = copy.deepcopy(state[9])
for index in indices:
temp_state = copy.deepcopy(state)
temp_state[index] = player
if player == maxi:
temp_state[9] = mini
elif player == mini:
temp_state[9] = maxi
moves.append(temp_state)
return moves
def minimax(state, depth, alpha, beta, mini, maxi):
"""
Parameters
----------
state : list
A list of length 10, representing a particular state of the game.
depth : int
The depth of the search tree.
alpha : int
Alpha value.
beta : TYPE
Beta value.
mini : str
The Minimizer player.
maxi : str
The Maximizer player.
Returns
-------
list
Implements the minimax algorithm with alpha-beta pruning and
returns a list whose first index is the alpha/beta value of the game state
and the second index is another list representing the next state recommended
by the algorithm.
"""
if end_state(state, mini, maxi) or depth == 0:
return [static_value(state, mini, maxi), ""]
next_moves = get_all_next_moves(state, mini, maxi)
move = []
if state[9] == maxi:
for s in next_moves:
score = minimax(s, depth - 1, alpha, beta, mini, maxi)[0]
if score > alpha:
move = copy.deepcopy(s)
alpha = score
if alpha >= beta:
break
return [alpha, move]
elif state[9] == mini:
for s in next_moves:
score = minimax(s, depth - 1, alpha, beta, mini, maxi)[0]
if score < beta:
move = copy.deepcopy(s)
beta = score
if alpha >= beta:
break
return [beta, move]
def avail_position(state):
"""
Parameters
----------
game : list
A list of length 10, representing a particular state of the game.
Returns
-------
avail : list
Returns a list of all available positions in state.
"""
avail = []
for _ in range(0,9):
if state[_] == '-':
avail.append(_)
return avail
def play(state: List[str], mini: str, maxi: str) -> Tuple[List[str], int]:
if not end_state(state, mini, maxi):
ai_move = minimax(state, 2, -math.inf, math.inf, mini, maxi)[1]
if not end_state(ai_move, mini, maxi):
# return ai_move and PLAY
return ai_move, PLAY
elif is_win(ai_move, maxi):
# return ai_move and WIN
return ai_move, WIN
elif is_draw(ai_move, mini, maxi):
# return ai_move and DRAW
return ai_move, DRAW
else:
# Scary. Hope we never get here
return ai_move, ERROR
else:
if is_win(state, mini):
# return state and LOSS
return state, LOSS
elif is_win(state, maxi):
# this condition shouldn't run
return state, ERROR
else:
# return state and DRAW
return state, DRAW