import sys from TTTUtils import * mD = dict() # master (as dict)
# for moves 1-3 we keep all positions # as long as they are not permutations
bL = [None] * 9 # "board" list
# move #1 for i in [0,1,4]: L = bL[:] L[i] = 'X' mD[str(i+1)] = L def test(n): kL = [k for k in mD.keys() if len(k) == n] for k in sorted(kL,reverse=True): if len(k) == n: print k print boardRep(mD[k]) print '---' sys.exit() #test(1)
# we do reverse sort to keep moves # where center(5) was first kL1 = [k for k in mD if len(k) == 1] kL1.sort(reverse=True)
# move #2 added = list() for k in kL1: bL = mD[k] for i in openPos(bL): bL2 = bL[:] bL2[i] = 'O' good = True # now test them if bL2 in added: continue for p in allPermutations(bL2): if p in added: good = False break if good: added.append(bL2) mD[k + str(i+1)] = bL2 #test(2)
# move #3 added = list() kL2 = [k for k in mD.keys() if len(k) == 2] kL2.sort(reverse=True)
for k in kL2: bL = mD[k] for i in openPos(bL): bL2 = bL[:] bL2[i] = 'X' good = True # now test them if bL2 in added: continue for p in allPermutations(bL2): if p in added: good = False break if good: added.append(bL2) mD[k + str(i+1)] = bL2 #test(3)
#=========================================
# move #4, check for X threatens win # we are still checking permutations
# from now on, we keep some info rD = dict() # what reason for move?
added = list() kL3 = [k for k in mD if len(k) == 3] kL3.sort(reverse=True) for k in kL3: bL = mD[k] # a list of i,line for all winners iL = winners(bL,who='X') if iL: i = iL[0][0] bL2 = bL[:] bL2[i] = 'O' k2 = k + str(i+1) mD[k2] = bL2 rD[k2] = 'block X' added.append(bL2) continue for i in openPos(bL): bL2 = bL[:] bL2[i] = 'O' good = True # now test them if bL2 in added: continue for p in allPermutations(bL2): if p in added: good = False break if good: added.append(bL2) mD[k + str(i+1)] = bL2 #test(4)
def testagain(): kL = [k for k in mD if len(k) == 4] print '4 move stage: N =', len(kL) sys.exit() #testagain()
#=========================================
# moves #5-9 def round(N): if N % 2: p1 = 'X'; p2 = 'O' else: p1 = 'O'; p2 = 'X' kL = [k for k in mD if len(k) == N-1] kL.sort(reverse=True) for k in kL: bL = mD[k] # check already have 3 in a row if wonPosition(bL): continue C = False # winners for player, then opponent for who in [p1,p2]: if C: continue # returns list of (i,line) iL = winners(bL,who) if iL: bL2 = bL[:] i = iL[0][0] bL2[i] = p1 k2 = k + str(i+1) mD[k2] = bL2 # save the reason if who == p1: rD[k2] = 'winner:' + p1 else: rD[k2] = 'block' C = True if C: continue # double threat for player,opponent for who in [p1,p2]: if C: continue # DT tries each move, returns i # if a move has two ways to win rL = doubleThreat(bL,who) if rL: i = rL[0] bL2 = bL[:] bL2[i] = p1 k2 = k + str(i+1) mD[k2] = bL2 # save the reason if who == p1: rD[k2] = 'DT for X' else: rD[k2] = 'DT for O' C = True # else, if the center is open, take it if not bL[4]: bL2 = bL[:] bL2[i] = p1 k2 = k + str(i+1) mD[k2] = bL2 rD[k2] = 'center' C = True if C: continue rL = promisingLines(bL,'X') for i,line in rL: if C: continue bL2 = bL[:] bL2[i] = p1 k2 = k + str(i+1) mD[k2] = bL2 rD[k2] = 'possible' C = True if C: continue
if N == 9: i = bL.index(None) bL2 = bL[:] bL2[i] = p1 k2 = k + str(i+1) mD[k2] = bL2 rD[k2] = 'last' continue print boardRep(bL) print 'found nothing' sys.exit() for i in range(5,10): round(i)
#----------------------------------------- def daughters(k,mD): rL = list() n = len(k) for k2 in mD: if len(k2) == n + 1: if k2[:n] == k: rL.append(k2) return rL #for k in mD: if len(k) == 9: print k
def output(kL): pL = list() pL.append(multipleReps(mD,kL[:4]).strip()) s = '' for k in kL[:4]: if k in rD: s += rD[k].ljust(11) else: s += ' ' * 11 pL.append(s) pL.append('')
pL.append(multipleReps(mD,kL[4:]).strip()) s = '' for k in kL[4:]: if k in rD: s += rD[k].ljust(11) else: s += ' ' * 11 pL.append(s) pL.append('-' * 30) return '\n'.join(pL)
for k in sorted(mD.keys(),reverse=True): continue if len(k) < 4: continue if not daughters(k,mD): # look at wins for O if not 'winner' in rD[k]: continue if not 'O' == rD[k][-1]: continue print k kL = list() for i in range(3,len(k)+1): kL.append(k[:i]) print output(kL)
for k in sorted(mD.keys(),reverse=True): if len(k) < 4: continue if not k[0] == '5': continue if not daughters(k,mD): print k #continue kL = list() for i in range(3,len(k)+1): kL.append(k[:i]) print output(kL) |