16 def valid_board(board
):
17 xs
, os
= xo_count(board
)
18 return (xs
- os
) == 0 or (xs
- os
) == 1
25 return [b
for b
in itertools
.product('.xo', repeat
=9)
31 if board
[0] == board
[1] == board
[2] and board
[0] != '.':
32 winning_player
= board
[0]
33 if board
[3] == board
[4] == board
[5] and board
[3] != '.':
34 winning_player
= board
[3]
35 if board
[6] == board
[7] == board
[8] and board
[6] != '.':
36 winning_player
= board
[6]
37 if board
[0] == board
[3] == board
[6] and board
[0] != '.':
38 winning_player
= board
[0]
39 if board
[1] == board
[4] == board
[7] and board
[1] != '.':
40 winning_player
= board
[1]
41 if board
[2] == board
[5] == board
[8] and board
[2] != '.':
42 winning_player
= board
[2]
43 if board
[0] == board
[4] == board
[8] and board
[0] != '.':
44 winning_player
= board
[0]
45 if board
[2] == board
[4] == board
[6] and board
[2] != '.':
46 winning_player
= board
[2]
52 return s
[0:3] + '\n' + s
[3:6] + '\n' + s
[6:9]
59 rows
[i
] += [s
[i
*3:i
*3+3]]
60 return '\n'.join(' '.join(r
) for r
in rows
)
66 rotation
= {0: 6, 1: 3, 2: 0, 3: 7, 4: 4, 5: 1, 6: 8, 7: 5, 8: 2}
67 inverse_rotation
= {t
: f
for f
, t
in rotation
.items()}
72 reflection
= {0: 2, 1: 1, 2: 0, 3: 5, 4: 4, 5: 3, 6: 8, 7: 7, 8: 6}
74 def rotate(board
, n
=1):
77 b
= tuple(b
[rotation
[i
]] for i
in range(len(board
)))
81 def reflect(board
, r
=True):
83 return tuple(board
[reflection
[i
]] for i
in range(len(board
)))
87 def transform(board
, n
, r
):
91 def untransform(board
, n
, r
):
93 return rotate(b
, abs(4-n
))
95 def all_transforms(board
):
96 return [(transform(board
, rot
, ref
), rot
, ref
)
98 for ref
in [False, True]]
101 return ''.join(board
)
103 def canonical(board
):
104 return max(all_transforms(board
), key
=lambda brf
: score(brf
[0]))
106 def non_winning_boards():
107 return set([canonical(b
)[0] for b
in all_boards()
112 def successors(board
):
113 xs
, os
= xo_count(board
)
117 for i
in range(len(board
)):
119 succs
+= [tuple(board
[:i
] + ('x',) + board
[i
+1:])]
123 for i
in range(len(board
)):
125 succs
+= [tuple(board
[:i
] + ('o',) + board
[i
+1:])]
130 return [i
for i
, c
in enumerate(board
) if c
== '.']
133 def apply_move(board
, position
, piece
):
134 return tuple(board
[:position
] + (piece
,) + board
[position
+1:])
136 def token_for_player(is_player_1
):