-
Notifications
You must be signed in to change notification settings - Fork 0
/
TTTsim4.py
319 lines (235 loc) · 9.85 KB
/
TTTsim4.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
import copy
#Takes in a 3x3 board and returns a list of (row,col) coordinates of spots not filled with 'X' or 'O'
def openSpots(board):
spots = []
for row in range( len(board) ):
for col in range( len(board[row]) ):
if board[row][col] == 0:
spots.append( (row,col) )
return spots
#Takes in a 3x3 board and returns True if there is 3 in a row, and false otherwise
def isGameOver(board):
#checking Rows
if board[0][0] == board[0][1] == board[0][2] != 0:
return True, board[0][0]
elif board[1][0] == board[1][1] == board[1][2] != 0:
return True, board[1][0]
elif board[2][0] == board[2][1] == board[2][2] != 0:
return True, board[2][0]
#Checking Cols
elif board[0][0] == board[1][0] == board[2][0] != 0:
return True, board[0][0]
elif board[0][1] == board[1][1] == board[2][1] != 0:
return True, board[0][1]
elif board[0][2] == board[1][2] == board[2][2] != 0:
return True, board[0][2]
#Checking Diagnols
elif board[0][0] == board[1][1] == board[2][2] != 0:
return True, board[0][0]
elif board[0][2] == board[1][1] == board[2][0] != 0:
return True, board[0][2]
#No 3-in-a-row
else:
return False, 0
#takes in a 3x3, rotates 90 degrees
def rot90(board):
return [ [ board[2][0] , board[1][0] , board[0][0] ],
[ board[2][1] , board[1][1] , board[0][1] ],
[ board[2][2] , board[1][2] , board[0][2] ] ]
def rot180(board):
return [ [ board[2][2] , board[2][1] , board[2][0] ],
[ board[1][2] , board[1][1] , board[1][0] ],
[ board[0][2] , board[0][1] , board[0][0] ] ]
def rot270(board):
return [ [ board[0][2] , board[1][2] , board[2][2] ],
[ board[0][1] , board[1][1] , board[2][1] ],
[ board[0][0] , board[1][0] , board[2][0] ] ]
#takes in 3x3 board and reflects it over the line from 0,1 to 2,1
def flipOverVert(board):
return [ [ board[0][2] , board[0][1] , board[0][0] ],
[ board[1][2] , board[1][1] , board[1][0] ],
[ board[2][2] , board[2][1] , board[2][0] ] ]
#takes in 3x3 board and reflects it over the line from 1,0 to 1,2
def flipOverHor(board):
return [ board[2],
board[1],
board[0] ]
def flipOverUpRight(board):
return [ [ board[2][2] , board[1][2] , board[0][2] ],
[ board[2][1] , board[1][1] , board[0][1] ],
[ board[2][0] , board[1][0] , board[0][0] ] ]
def flipOverDownLeft(board):
return [ [ board[0][0] , board[1][0] , board[2][0] ],
[ board[0][1] , board[1][1] , board[2][1] ],
[ board[0][2] , board[1][2] , board[2][2] ] ]
def similar(check, memory):
#check is the board that we want to "check" for similarity with boards in memory
#memory is a list of boards that form a basis for a given number of moves
for i in range(len(memory)):
board = memory[i]
if check[1][1] == board[1][1]:
if board==flipOverVert(check) or board==flipOverHor(check) or board==flipOverUpRight(check) or board==flipOverDownLeft(check):
return True, i
elif board == rot180(check):
return True, i
elif board == rot90(check) or board == rot270(check):
return True, i
elif board == check:
return True, i
return False, len(memory)
#Xs are 1 and 0s are 2, empty spaces are 0
#uniq is a dictionary of unique boards
# keys are number of moves
# values are a list of unique boards formed the given number of moves
uniq = {}
terminalBasis = {}
nonTerminalBasis = {}
uniq[0] = [ [ [0, 0, 0],
[0, 0, 0],
[0, 0, 0] ] ]
terminalBasis[0] = []
nonTerminalBasis[0] = [ [ [0, 0, 0],
[0, 0, 0],
[0, 0, 0] ] ]
#dict of valid games after being played;
# key1 = # of Xs and Os
# value= dict of distinct games
# key2 = last board played (from 0 to len(nonTerminalBasis[key1]) )
# value = set of games with nonTerminalBasis[key1][key2] board played last
gamesContinued = { 0: { 0: [ [0] ] } , 1:{} , 2:{} , 3:{} , 4:{} , 5:{} , 6:{} , 7:{} , 8:{} , 9:{} , 10:{} }
gamesFinished = { 0:{} , 1:{} , 2:{} , 3:{} , 4:{} , 5:{} , 6:{} , 7:{} , 8:{} , 9:{} , 10:{} }
gameCount = { 'nonTerminal' : { 'duplicates': {} ,
'nonDuplicates' : {} },
'terminal' : { 'duplicates': {} ,
'nonDuplicates' : { 'X' : {},
'O' : {} } } }
gameCount['nonTerminal']['nonDuplicates'] = {0:0, 1:0, 2:0, 3:0, 4:0, 5:0, 6:0, 7:0, 8:0, 9:0, 10:0}
gameCount['nonTerminal']['duplicates'] = {0:0, 1:0, 2:0, 3:0, 4:0, 5:0, 6:0, 7:0, 8:0, 9:0, 10:0}
gameCount['terminal']['nonDuplicates']['X'] = {0:0, 1:0, 2:0, 3:0, 4:0, 5:0, 6:0, 7:0, 8:0, 9:0, 10:0}
gameCount['terminal']['nonDuplicates']['O'] = {0:0, 1:0, 2:0, 3:0, 4:0, 5:0, 6:0, 7:0, 8:0, 9:0, 10:0}
gameCount['terminal']['duplicates'] = {0:0, 1:0, 2:0, 3:0, 4:0, 5:0, 6:0, 7:0, 8:0, 9:0, 10:0}
#Iterates over 'board statuses' ie. when there are x number of Xs or Os, where play = x
for play in range(0,10):
#Determining whose turn it is
if play % 2 == 0:
player = 'X'
else:
player = 'O'
print('Play = ' + str(play) + ' , and player = ' + player)
print('Uniqs = ' + str(len(uniq[play])))
print('nonTerminalBasis = ' + str(len(nonTerminalBasis[play])))
print('terminalBasis = ' + str(len(terminalBasis[play])))
nonTbasis = []
Tbasis = []
basis = []
dealWithAfter = {}
playedNextRound = 0
endedThisRound = 0
#iterates over the unique boards
# Thought: should I only iterate over non-winning boards in the basis...
for i in range(len(gamesContinued[play])):
dealWithAfter[i] = []
U = nonTerminalBasis[play][i]
possibleSpots = openSpots(U)
for spot in possibleSpots:
row = spot[0]
col = spot[1]
board = copy.deepcopy(U)
board[row][col] = player
#Thought: when I append gamesAfter, should I append a 'relevantAfter' dict
#so we don't have to iterate at the begining
if play < 4 or isGameOver(board)[0] == False:
sim = similar(board, nonTbasis)
if sim[0] == False:
nonTbasis.append(board)
for seq in gamesContinued[play][i]:
if sim[1] in gamesContinued[play+1].keys():
newSeq = seq + [sim[1]]
if newSeq in gamesContinued[play+1][ sim[1] ]:
gameCount['nonTerminal']['duplicates'][play+1] += 1
else:
gameCount['nonTerminal']['nonDuplicates'][play+1] += 1
gamesContinued[play+1][ sim[1] ] += [ seq + [sim[1]] ]
else:
gamesContinued[play+1][ sim[1] ] = [ seq + [sim[1]] ]
gameCount['nonTerminal']['nonDuplicates'][play+1] += 1
else:
dealWithAfter[i] += [ board ]
for i in dealWithAfter:
for board in dealWithAfter[i]:
sim = similar(board, Tbasis)
if sim[0] == False:
Tbasis.append(board)
basisIndex = len(nonTbasis) + sim[1]
winner = isGameOver(board)[1]
for seq in gamesContinued[play][i]:
if basisIndex in gamesFinished[play+1].keys():
newSeq = seq + [basisIndex]
if newSeq in gamesFinished[play+1][ basisIndex ]:
gameCount['terminal']['duplicates'][play+1] += 1
else:
gameCount['terminal']['nonDuplicates'][winner][play+1] += 1
gamesFinished[play+1][ basisIndex ] += [ seq + [basisIndex] ]
else:
gameCount['terminal']['nonDuplicates'][winner][play+1] += 1
gamesFinished[play+1][ basisIndex ] = [ seq + [basisIndex] ]
print('Number of games to be played next round')
print(gameCount['nonTerminal']['nonDuplicates'][play+1])
print('Number of games ended this round with X win')
print(gameCount['terminal']['nonDuplicates']['X'][play+1])
print('Number of games ended this round with O win')
print(gameCount['terminal']['nonDuplicates']['O'][play+1])
nonTerminalBasis[play+1] = nonTbasis
terminalBasis[play+1] = Tbasis
uniq[play+1] = nonTbasis + Tbasis
for k in uniq:
print('******** Basis for ' + str(k) + ' plays ****')
if len(uniq[k]) < 16:
print(' *** nonTerminalBasis ***')
for line in range(3):
statment = ''
for j in nonTerminalBasis[k]:
statment += str(j[line][0]) + ',' + str(j[line][1]) + ',' + str(j[line][2])+ ' | '
print(' ' + statment)
print(' *** terminalBasis ***')
for line in range(3):
statment = ''
for j in terminalBasis[k]:
statment += str(j[line][0]) + ',' + str(j[line][1]) + ',' + str(j[line][2])+ ' | '
print(' ' + statment)
else:
print(' *** nonTerminalBasis ***')
for line in range(3):
statment = ''
for j in nonTerminalBasis[k][:12]:
statment += str(j[line][0]) + ',' + str(j[line][1]) + ',' + str(j[line][2])+ ' | '
print(' ' + statment)
print(' *** terminalBasis ***')
for line in range(3):
statment = ''
for j in terminalBasis[k][:12]:
statment += str(j[line][0]) + ',' + str(j[line][1]) + ',' + str(j[line][2])+ ' | '
print(' ' + statment)
for k in uniq:
print(str(k) + ' ' + str(len(uniq[k])) + ' ' + str(len(nonTerminalBasis[k])) + ' ' + str(len(terminalBasis[k])))
'''
for line in range(3):
statment = ''
for j in uniq[9][:15]:
statment += str(j[line][0]) + ',' + str(j[line][1]) + ',' + str(j[line][2])+ ' | '
print(statment)
'''
print('-----------------------------------------------------------------------------------------------------')
for k in range(11):
print('terminal nonDuplicates: X wins:' + str(gameCount['terminal']['nonDuplicates']['X'][k]) + ' O Wins: ' + str(gameCount['terminal']['nonDuplicates']['O'][k]))
print('-----------------------------------------------------------------------------------------------------')
for k in range(11):
print('nonTerminal: nonDuplicates: ' + str(gameCount['nonTerminal']['nonDuplicates'][k]) + ' duplicates: ' + str(gameCount['nonTerminal']['duplicates'][k]))
print('-----------------------------------------------------------------------------------------------------')
'''
for line in range(3):
statment = ''
for j in uniq[9][15:]:
statment += str(j[line][0]) + ',' + str(j[line][1]) + ',' + str(j[line][2])+ ' | '
print(statment)
'''