## 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:

 `123X O X. . .. . .is accepted124X O .X . .. . .is accepted/snip/154X . .X O .. . .is a perm of152X 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 sysfrom TTTUtils import *mD = dict() # master (as dict)# round 1bL = [None] * 9 # "board" listfor 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 2added = 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 3added = 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()) `