#!/usr/bin/python
# Code by [[User:Gdr]]. Licensed under the GPL and GFDL.
# A tic-tac-toe position has cells numbered from 0-8. It is represented
# in compressed form as an 18-bit number where bit 2i is 1 iff cell i is
# full, and bit 2i+1 is 1 iff cell i contains X.
# A list of winning lines.
lines = [(0,1,2),(3,4,5),(6,7,8),(0,3,6),(1,4,7),(2,5,8),(0,4,8),(2,4,6)]
# List of pairs for each winning line, each pair being:
# 0. A mask for testing the winning line against the board.
# (This is also the result of comparing the mask if line is a win for X.)
# 1. Result of comparing the mask if line is a win for O.
win_masks = [(sum([3 << (2 * i) for i in l]),
sum([2 << (2 * i) for i in l])) for l in lines]
# A mask for testing that the board is full.
full_mask = sum([2 << (2 * i) for i in xrange(9)])
# Return True if the game is over in 'pos', False if play can continue.
def game_over(pos):
if pos & full_mask == full_mask:
return True
for x,o in win_masks:
if pos & x in (x,o):
return True
return False
# Return the number of games that can be played starting at 'pos' with
# 'player' to move (0 = O, 1 = X), 'positions' being a dictionary of
# positions seen so far.
def count_games(pos, player, positions):
positions[pos] = 1
if game_over(pos):
return 1
games = 0
for i in xrange(9):
if pos & (2 << (2 * i)) == 0:
new_pos = pos | ((2 + player) << (2 * i))
games += count_games(new_pos, 1 - player, positions)
return games
# All the symmetries of the tic-tac-toe board, represented as
# permutations of the cells.
symmetries = [(0,1,2,3,4,5,6,7,8),
(2,5,8,1,4,7,0,3,6), # quarter-turn clockwise
(8,7,6,5,4,3,2,1,0), # half-turn
(6,3,0,7,4,1,8,5,2), # quarter-turn anticlockwise
(6,7,8,3,4,5,0,1,2), # reflection in horizontal line
(2,1,0,5,4,3,8,7,6), # reflection in vertical line
(0,3,6,1,4,7,2,5,8), # reflection in leading diagonal
(8,5,2,7,4,1,6,3,0)] # reflection in trailing diagonal
# Return the position 'pos' transformed by the permutation 'perm'.
def permute(pos, perm):
return sum([((pos >> (2*i)) & 3) << (2*perm[i]) for i in xrange(9)])
# Return the canonical representative of the position 'pos'. This is the
# lowest-number encoding of the position under the eight symmetries.
def canonical(pos):
return min([permute(pos, sym) for sym in symmetries])
# As 'count_games', but consider positions identical if they are related
# by a symmetry of the board.
def count_games_2(pos, player, positions):
# assert(pos == canonical(pos))
positions[pos] = 1
if game_over(pos):
return 1
games = 0
new_positions = {}
for i in xrange(9):
if pos & (2 << (2 * i)) == 0:
new_pos = canonical(pos | ((2 + player) << (2 * i)))
if not new_positions.has_key(new_pos):
new_positions[new_pos] = 1
games += count_games_2(new_pos, 1 - player, positions)
return games
if __name__ == '__main__':
p = {}
games = count_games(0, 1, p)
print "Neglecting symmetry,",
print "there are %d positions and %d games." % (len(p), games)
p = {}
games = count_games_2(canonical(0), 1, p)
print "With symmetry,",
print "there are %d positions and %d games." % (len(p), games)
# Neglecting symmetry, there are 5478 positions and 255168 games.
# With symmetry, there are 765 positions and 26830 games.
