Python for Bioinformatics: tic-tac-toe: building our repertoire

Thursday, August 6, 2009

tic-tac-toe: building our repertoire

Now let's go through the first three rounds of building a library of all possible boards. A previous post did this by hand. Unfortunately, it shows. There are errors in the previous boards, situations where I did not recognize that two boards were the same under rotation or reflection.

The code is not very pretty at this stage, but it is typical of projects that I've done. While I'm still getting things to work, there are lots of extra print statements, and there are places where a similar operation is repeated, just because that seemed to be faster to write. We'll sort it out later. The main thing is to look carefully at the output to check that when we reject "duplicates" and "permutations" the decision is correct.

Here is a small part of the output at round 3:

123
X  O  X
.  .  .
.  .  .

is accepted

124
X  O  .
X  .  .
.  .  .

is accepted

/snip/

154
X  .  .
X  O  .
.  .  .

is a perm of
152
X  X  .
.  O  .
.  .  .

A partial list of the mistakes from before (and the dups) is:

163 (127)
169 (129)
193 (137)
213 (132)
217 (136)
219 (196)
241 (243)
...

By my count now, we have 53 possible boards at stage 3. Next, going on to stage 4. But first we will have to analyze the boards for forced moves.

import sys
from TTTUtils import *
mD = dict()  # master (as dict)

# round 1
bL = [None] * 9  # "board" list
for i in [0,1,4]:
    L = bL[:]
    L[i] = 'X'
    mD[str(i+1)] = L
    
def test(n):
    for k in sorted(mD.keys()):
        if len(k) == n:
            print k
            print boardRep(mD[k])
            print '---'
    sys.exit()
#test(1)

# round 2
added = list()
kL = [k for k in mD.keys() if len(k) == 1]
kL.sort()
#kL.reverse()
for k in kL:
    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)

def find_kforp(p):
    for k in mD:
        if mD[k] == p:
            return k
    return 'not found'

# round 3
added = list()
kL = [k for k in mD.keys() if len(k) == 2]
kL.sort()
#kL.reverse()
for k in kL:
    bL = mD[k]
    for i in openPos(bL):
        bL2 = bL[:]
        bL2[i] = 'X'
        good = True  # now test them
        if bL2 in added:
            print k + str(i+1)
            print boardRep(bL2)
            print 'is a dup'
            continue
        for p in allPermutations(bL2):
            if p in added:  
                print k + str(i+1)
                print boardRep(bL2)
                print 'is a perm of'
                print find_kforp(p)
                print boardRep(p)
                good = False
                break
        if good:
            print k + str(i+1)
            print boardRep(bL2)
            print 'is accepted\n'
            added.append(bL2)
            mD[k + str(i+1)] = bL2
            
print len(mD.keys())