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)