#!/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.