Talk:Game complexity/ttt.py

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

Talk pages are where people discuss how to make content on Wikipedia the best that it can be. You can use this page to start a discussion with others about how to improve the "Game complexity/ttt.py" page.

Start a discussion