## Thursday, August 6, 2009

### tic-tac-toe: utilities

Let's continue with what is admittedly a rather silly example: a simulation of tic-tac-toe boards with the ultimate goal of analyzing strategy. This post just gives some code for utility functions. For example, there are functions to give all rotations and reflections for a board.

There are other functions (not yet debugged properly) for assessing board status. If you want to follow along at home, save the code as TTTUtils.py on your Desktop so you can import it in the following steps.

Here is the output, along with comments to tell what is going on:

 # start1 2 34 5 67 8 9# rotations (left)3 6 92 5 81 4 79 8 76 5 43 2 17 4 18 5 29 6 3# reflections7 8 94 5 61 2 33 2 16 5 49 8 71 4 72 5 83 6 99 6 38 5 27 4 1

[Update: I added several functions (multipleReps, winners, doubleThreat, etc.)]
Here's the code:

 rows = [ [0,1,2], [3,4,5], [6,7,8] ]cols = [ [0,3,6], [1,4,7], [2,5,8] ]diags = [ [0,4,8], [2,4,6] ]corners = [0,2,6,8]all = rows + cols + diagsdef boardRep(bL): rL = list() for iL in [[0,1,2],[3,4,5],[6,7,8]]: line = list() for i in iL: e = bL[i] if e: line.append(e) else: line.append('.') rL.append(' '.join(line)) return '\n'.join(rL) + '\n' def multipleReps(mD,kL): repL = list() for k in kL: repL.append(boardRep(mD[k])) pL = [[],[],[]] for rep in repL: L = rep.strip().split('\n') for i,line in enumerate(L): pL[i].append(line) L = [k.ljust(11) for k in kL] pL.append(''.join(L)) for i in range(3): pL[i] = (' '*4).join(pL[i]) return '\n'.join(pL) + '\n' R = range(1,10)def rotateLeft(bL): # easier to think in 1..9 D = {1:3,2:6,3:9,4:2,5:5, 6:8,7:1,8:4,9:7} # keep lists indexed in 0..8 return [bL[D[i]-1] for i in R]def threeRotations(bL): rL = list() for i in range(3): bL = rotateLeft(bL) rL.append(bL) return rL def switch(bL,i,j): bL[i],bL[j] = bL[j],bL[i] def fourReflections(L): rL = [ L[6:] + L[3:6] + L[:3] ] bL = L[:] for i,j in zip((0,3,6),(2,5,8)): switch(bL,i,j) rL.append(bL) bL = L[:] for i,j in zip((1,2,5),(3,6,7)): switch(bL,i,j) rL.append(bL) bL = L[:] for i,j in zip((1,0,3),(5,8,7)): switch(bL,i,j) rL.append(bL) return rL def allPermutations(bL): rL = threeRotations(bL) rL.extend(fourReflections(bL)) return rL# find a line that can windef winners(bL,who): #print 'test winners for', who #print boardRep(bL) rL = list() for line in all: vL = [bL[i] for i in line] vL.sort() if vL == [None, who, who]: for i in line: if not bL[i]: break # return a list of (i, line) rL.append((i,line)) #if rL: print 'returning', rL,'\n' return rL def doubleThreat(bL,p,v=False): if v: print 'doubleThreat DT' iL = openPos(bL) rL = list() for i in iL: if v: print 'testing', i bL2 = bL[:] bL2[i] = p if v: print boardRep(bL2) wL = winners(bL2,who=p) if wL and len(wL) > 1: if v: print 'DT saving', if v: print i rL.append(i) if v: print 'DT returning', rL return rLdef promisingLines(bL,who): #print 'promisingLine', bL, who rL = list() for line in all: vL = [bL[i] for i in line] if vL.count(who) == 1: if vL.count(None) == 2: for i in line: if not i: break rL.append((i,line)) return rL def wonPosition(bL): for line in all: vL = [bL[i] for i in line] if vL.count(None) == 0: p = vL[0] if vL.count(p) == 3: return pdef noPossibleWin(bL): for line in all: vL = [bL[i] for i in line] vL = [e for e in vL if e] if len(vL) == 1: return False if len(vL) == 2: if vL[0] == vL[1]: return False return Truedef openPos(bL): return [i for i in range(len(bL)) if not bL[i]]def closedPos(bL): return [i for i in range(len(bL)) if bL[i]] def findKforBoard(bL): for k in mD: if mD[k] == bL: return kif __name__ == '__main__': bL = list() for i in R: bL.append(str(i)) print boardRep(bL) for e in threeRotations(bL): print boardRep(e) for e in fourReflections(bL): print boardRep(e)