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:

# start
1 2 3
4 5 6
7 8 9

# rotations (left)
3 6 9
2 5 8
1 4 7

9 8 7
6 5 4
3 2 1

7 4 1
8 5 2
9 6 3

# reflections
7 8 9
4 5 6
1 2 3

3 2 1
6 5 4
9 8 7

1 4 7
2 5 8
3 6 9

9 6 3
8 5 2
7 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 + diags

def 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 win
def 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 rL

def 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 p

def 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 True

def 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 k

if __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)