File talk:Tictactoe-X.svg
Jump to navigation
Jump to search
This concept originally appeared in Ian Stewart's "Mathematical Recreations" section of Scientific American http://www.ncbi.nlm.nih.gov/pubmed/10914406 Which in turn was based on "Fractal Images of Formal Systems," The Journal of Philosophical Logic 26: 181-222, 1997 http://www.pgrim.org/fractal/index.html It was certainly popularized by xkcd who deserves credit for that.
Source of image[edit]
This file and related files were generated by a computer program that I wrote, and which I also hereby release under CC SA-3.0 and GFDL licences:
''' inspired by xkcd: Tic-Tac-Toe [http://xkcd.com/832/] '''
def svg_prologue(f):
f.write('''<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<svg
xmlns:svg="http://www.w3.org/2000/svg"
xmlns="http://www.w3.org/2000/svg"
version="1.1">
<defs>
<style type="text/css">
.XO { /* general styling for Xs and Os */
fill: none;
stroke-linecap: butt;
stroke-linejoin: miter;
stroke-opacity: 1;
}
.XO_1 { /* level 1 X/O */
stroke-width: 27px;
}
.XO_2 { /* level 2 X/O */
stroke-width: 9px;
}
.XO_3 { /* level 3 X/O */
stroke-width: 3px;
}
.XO_4 { /* level 4 X/O */
stroke-width: 1px;
}
.XO_5 { /* level 5 X/O */
stroke-width: .33px;
}
.XO_sel { /* optimal move */
stroke: red;
}
.XO_unsel { /* already-placed move */
stroke: black;
}
.X { /* normal X */
}
.O { /* normal O */
}
.win3 { /* 3-in-a-row line */
fill: none;
stroke: black;
stroke-linecap: butt;
stroke-linejoin: miter;
stroke-opacity: 1;
}
.win3_2 { /* win line after 4 or 5 moves */
stroke-width: 6px;
}
.win3_3 { /* win line after 6 or 7 moves */
stroke-width: 2px;
}
.win3_4 { /* win line after 8 or 9 moves */
stroke-width: .66px;
}
.win3X { /* 3-in-a-row line for X */
}
.win3O { /* 3-in-a-row line for O */
}
.rect_win { /* rectangle for a win */
fill: none;
stroke: black;
stroke-width: 1px;
stroke-linecap: butt;
stroke-linejoin: miter;
stroke-opacity: 1;
}
.rect_draw { /* rectangle for a draw */
fill: none;
stroke: black;
stroke-width: 1px;
stroke-linecap: butt;
stroke-linejoin: miter;
stroke-opacity: 1;
}
.rect_subdiv { /* rectangle for an unresolved board */
fill: none;
stroke: none;
}
.rect_sel { /* rectangle for a single selected piece */
fill: #ccc;
stroke: none;
}
.rect_unsel { /* rectangle for a single unselected piece */
fill: none;
stroke: none;
}
</style>
</defs>
''')
def svg_epilogue(f):
f.write('''
</svg>''')
WINS = [ # ((p0,p1,p2), (x0,y0, x1,y1))
((0,1,2), (0,1./6, 1,1./6)), # row0
((3,4,5), (0,3./6, 1,3./6)), # row1
((6,7,8), (0,5./6, 1,5./6)), # row2
((0,3,6), (1/6.,0, 1./6,1)), # col0
((1,4,7), (3/6.,0, 3./6,1)), # col0
((2,5,8), (5/6.,0, 5./6,1)), # col0
((0,4,8), (0,0, 1,1)), # diag-l2r
((2,4,6), (1,0, 0,1)), # diag-r2l
]
def check_win(board):
for p, l in WINS:
for player in 'XO':
if all(board[x]==player for x in p):
return (player, p, l)
return None
RESULTS = {'O':{}, 'X':{}}
BESTMOVE = {'O':{}, 'X':{}}
def other(x):
return {'O':'X','X':'O'}[x]
# Optimality is defined as the *shortest time to a win*, for the sake of cleaner output.
def cacher(func):
def f(board, player):
if board in RESULTS[player]:
return RESULTS[player][board]
res = None
out = check_win(board)
if out:
# switch 0,1 and 100,1 around to play losers' Tic-Tac-Toe
if out[0] == player: res = 0,1
else: res = 100,1
elif ' ' not in board:
res = 0,1
if res is None:
res = func(board, player)
RESULTS[player][board] = res
return res
return f
@cacher
def my_move(board, player):
# My turn. Pick the "optimal" move.
best = 9999
bestctr = 9999
curctr = 0
besti = -1
for i, x in enumerate(board):
if x != ' ': continue
newboard = board[:i]+player+board[i+1:]
res, ctr = other_move(newboard, player)
res += 1
if res < best:
best = res
bestctr = ctr
curctr = ctr
besti = i
elif res == best:
if ctr < bestctr:
bestctr = ctr
besti = i
curctr += ctr
BESTMOVE[player][board] = besti
return best, curctr
@cacher
def other_move(board, player):
# Other guy's turn to move. Consider all of his possible moves.
worst = 0
curctr = 0
for i, x in enumerate(board):
if x != ' ': continue
newboard = board[:i]+other(player)+board[i+1:]
res, ctr = my_move(newboard, player)
res += 1
if res > worst:
worst = res
curctr = ctr
elif res == worst:
curctr += ctr
return worst, curctr
PADDING = 1/50.
def subpos(pos, i):
x,y,s,l = pos
s/=3.
x+=s*PADDING
y+=s*PADDING
return (x+(i%3)*s, y+(i//3)*s, s-2*s*PADDING, l+1)
def svg_rect(f, rectclass, pos, hist):
x,y,s,l = pos
f.write(' '*l + '<rect x="%f" y="%f" width="%f" height="%f" id="r%s" class="rect_%s" />\n'%(x, y, s, s, hist, rectclass))
def svg_board(f, board, player, pos, hist):
x,y,s,l = pos
# special case: pass in 'sel' or 'unsel' to display a single mark
if board in ('sel', 'unsel'):
svg_rect(f, board, pos, hist)
if player == 'X':
f.write(' '*l + '<path d="m %f,%f %f,%f m %f,%f %f,%f" id="xo%s" class="X XO XO_%d XO_%s" />\n'%(x,y, s,s, 0,-s, -s,s, hist, l, board))
elif player == 'O':
f.write(' '*l + '<circle cx="%f" cy="%f" r="%f" id="xo%s" class="O XO XO_%d XO_%s" />\n'%(x+s/2., y+s/2., s/2., hist, l, board))
return
if board in BESTMOVE[player]:
best = BESTMOVE[player][board]
board = board[:best]+player+board[best+1:]
hist+=str(best)
else:
best = -1
f.write(' '*l + '<g id="g%s">\n'%hist)
win = check_win(board)
# forced move: don't expand the node
if win is None and board.count(' ') == 1:
i = board.find(' ')
board = board[:i]+other(player)+board[i+1:]
win = check_win(board)
if win:
svg_rect(f, 'win', pos, hist)
elif ' ' not in board:
svg_rect(f, 'draw', pos, hist)
else:
svg_rect(f, 'subdiv', pos, hist)
# draw all the static elements
for i,pt in enumerate(board):
if pt not in 'XO': continue
if i == best:
svg_board(f, 'sel', player, subpos(pos, i), hist+'_'+str(i))
else:
svg_board(f, 'unsel', pt, subpos(pos, i), hist+'_'+str(i))
# check for a win and draw the win line appropriately
if win:
p, pt, ln = win
x1, y1, x2, y2 = ln
f.write(' '*l + ' <line x1="%f" y1="%f" x2="%f" y2="%f" class="win3 win3_%d win3%s" />\n'%(x1*s+x, y1*s+y, x2*s+x, y2*s+y, l, p))
f.write(' '*l + '</g>\n')
return
for i,pt in enumerate(board):
if pt != ' ': continue
newboard = board[:i]+other(player)+board[i+1:]
svg_board(f, newboard, player, subpos(pos, i), hist+str(i))
f.write(' '*l + '</g>\n')
if __name__ == '__main__':
my_move(' '*9, 'X')
other_move(' '*9, 'O')
f=open("ttt-X.svg", "w")
svg_prologue(f)
svg_board(f, ' '*9, 'X', (0, 0, 1000, 0), '')
svg_epilogue(f)
f.close()
f=open("ttt-O.svg", "w")
svg_prologue(f)
for i in xrange(9):
svg_board(f, ' '*i + 'X' + ' '*(8-i), 'O', subpos((0, 0, 1000, 0), i), str(i))
svg_epilogue(f)
f.close()
They are not the result of "tracing" the comic image. nneonneo (talk) 14:24, 11 January 2011 (UTC)
