Talk:Game complexity/ttt.py
Appearance
#!/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.