Friday, August 7, 2009

tic-tac-toe: game on!

This is my last post about this topic (see sideboard for more). What I have is a fairly long listing (250 lines) which uses the utilities from here, and analyzes the outcomes of playing tic-tac-toe. You can run it on any computer with Python installed (e.g. any Mac).

It has four major sections. (1) We build up game positions as shown previously, through move # 3. We make sure to check that a new position is not a permutation of one already known. Also we move from the center out, so that if there are two identical positions, we keep the one in which the center was X's first move. (2) We then do move # 4, continuing as before, but also checking to be sure that if X threatens to win, we block him. (3) For moves # 5-9 we check for several things in turn:

• is the position already won
• can the player win
• can the opponent win
• can the player make a "double threat"---and win on next turn.
• can the opponent make a double threat---then we block.


The last part organizes the output. All the results from both the intermediate stages and either won or filled (drawn) boards are stored in a dictionary labeled mD, keyed by the move list for that position (1-based indexing) For example, 27853149 means X took square 2, then O took square 7, and so on. We also store the logic for the game in another dictionary labeled rD, so for each position, we can say what the reason was for us to make the last move. We filter for boards which terminate a chain by looking for those with no "daughters"---that is, there are no keys in the dictionary which begin with this key.

The positions could be analyzed in a variety of ways. Here are two:
(1) If you've played you know that it is difficult to win if you do not go first. But it is not impossible! There are six winning games for O. Here is my favorite:

27314985
. X X O X X O X X O X X
. . . . . . X . . X . .
O . . O . . O . . O . O
273 2731 27314 273149
block X block center

O X X O X X
X . . X O .
O X O O X O
2731498 27314985
block winner:O


We see that X took the side position, then O the corner, then X the opposing corner (273). It looks pretty good for X! O has to block on the next move. But now O threatens and X must block, and finally O has an unanswerable double threat.

The other question I looked at was: does X always win if he takes the center first? The answer is surprising. X wins only 4/10. The others are draws. Here is one of the wins:

5284793
. O . . O . . O . . O .
. X . O X . O X . O X .
. X . . X . X X . X X O
528 5284 52847 528479
DT for X block

. O X
O X .
X X O
5284793
winner:X


Here is the code:

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)