All Board States and Moves of Tic-Tac-Toe
A splinter in my mind
There are certain problems that come to my mind once in a while. I ponder about and evaluate them, struggle with them a little bit but then give up because my knowledge and expertise is not enough to finish solving it. "All states of Tic-Tac-Toe" was one of these problems. I remember thinking about it a decade ago and giving up on computing all of them because I didn't know much about data structure and algorithms.
Yesterday, I was surveying computer science books for future study and saw the below illustration in the first chapter of "The Pattern On The Stone" by Daniel Hillis. (It was recommended by Alan Kay in a Quora question.) It triggered memories of my former struggle with the Tic-Tac-Toe problem. I evaluated it a bit and this time I realized that I finally have the capacity to solve it, once and for all!
Problem space
First, I thought about the problem space/size and how to implement and traverse a tree structure to store successive moves. (Spoilers: the correct data structure is not a tree but a graph, and also the unit state is not an individual board configuration but its symmetry groups but I'll come to that later, please bear with me.)
My first idea was to draw the whole tree on my screen, which is 4K, 3,840 x 2,160 ~= 8M pixels. If each board takes 9 pixels, and we'll draw each path in the tree, there are at most 9! different paths: First move is to place an X on a tile among 9. Second move has 1 tile occupied. Place an O on a tile among 8 etc. Continue down to step 1. Actually, most games end before 9 steps, so only a few leaves have that depth. Hence 9! ~= 360K is an upper bound. 3,840 * 2,160 / 9! ~= 23 pixels. More than enough space! :-)
Another way of looking at the problem is to compute all possible board configurations. A tile can be empty, or can have X or O on it, hence 3 states. There are 9 tiles. 3^9 ~= 20K. This approach ignores the succession between them via player moves. And also, some of these configurations are not legitimate states; there is no path that leads to those states in a game that obeys the rules. Assuming that X starts first, the number of X's is either equal to the number of O's or can be only one more.
Drawing all paths can be fun, however that approach hides some internal structure of the problem. Unlike chess tic-tac-toe does not have a sense of direction. Some board configurations are equivalent to others. For example, initially putting an X at the top left corner or top right corner does not matter in terms of strategy. You can rotate the board 90 degrees counter-clockwise and have the same state (Or turn your head 90 degrees clockwise. Hehe.)
The board is symmetric under rotations and mirroring. To discover the true underlying structure via unique states, one needs to group individual states into symmetry groups, set of states which are equivalent under these symmetry transformations. So, the problem is to find the number of unique board states and how they are connected via player moves. The actual number is surprisingly low!
Data Structures
After clarifying the problem, next is to define data structures to use to solve it. Need to hold individual board states, hold their symmetry groups, and have a traversable structure to connect successive states. Because I am solving a very specialized function, I wanted to do it using primitives and basic structures given with Python without writing my own classes.
Chose to use tuples to represent a board state.
from typing import Iterable, List, Set
State = Iterable[Iterable[int]]
There are additional unspoken constraints on the State type, such as inner tuple should be made of tree integers, 0, 1 or 2. 0 being empty tile, 1 is X and 2 is O. Better practice could be using enums for tile values, and a class for a state. But this type gave me a least complicated functional structure to hold a state. I was able to keep constraints in my mind over the few hours I worked on the problem. A longer project should use more human readable structures.
Example state:
TOP_LEFT_STATE = ((1, 0, 0),
(0, 0, 0),
(0, 0, 0))
A symmetry group, a set of states that are equivalent under rotation and mirror, can be represented via a list of States. SymmetryGroup = List[State] Why a list but not a Traversable (sets are traversable too)? Well... Again bad coding practice. For reasons I'll explain later, I want to have a single, "canonical" state that represents the group and going to place that group at the first element of the list. A better approach should isolate the implementation of "canonical representation of a symmetry group" from its users, say by returning it via a method.
Finally, the structure to hold the connection between groups via player moves is a graph, not a tree. Realized that when I got some unexpected results. It's possible to arrive same board configuration via different paths. I saw plotting all paths as a trivial problem, hence I want same board states that can be arrived via different path to be represented by the same node. In a tree, branches never converge. So, correct data structure to represent this problem is a Directed (we only add new marks at each step, never remove one) Acyclic (not possible to come back to the same state) Graph, DAG.
Hence, a Node is made of a value val (which will be the ID of a SymmetryGroup referred by the group, and a list of successors which refer to future game states which can be arrived via legal moves. This graph node class is names in an abstract way, and there is no other structure to represent whole graph.
GroupId = int
class Node(object):
def __init__(self, val: GroupId = None, successors: List[GroupId] = None):
self.val = val
self.successors = successors or []
GroupId is for semantic typing. It basically is an int. I got the idea of a group id from relational databases with auto-incremental IDs, where whenever a new row is added to a table of an Entity the ID is incremented by one. I'd decided to increment a global gid variable by one each time a new symmetry group is computed. Again, it's bad design to couple group computation with graph implementation and counter increments.
By the way, I did not use these type hints other than readability. Does not have any static or dynamic type checker in place.
Algorithms
Now that we have our data structures ready, let's write algorithms that'll compute the graph. Instead of going with an object oriented method where each function relevant to a class is put into the scope of that class, I wrote multiple global level functions that operation on relevant types. Because code is small, didn't go for better isolation.
First wrote some debug functions without them I wouldn't arrive to a working solution. state_str, print_state and print_states which convert a State to a string, "pretty print" them, respectively. Their implementation is not essential.
We need a function to compute symmetry groups of a state.
def get_symmetries(st: State) -> SymmetryGroup:
def get_vertical_mirror(st: State) -> State:
return tuple(reversed(st))
def get_rotations(st: State) -> List[State]:
((a, b, c),
(d, e, f),
(g, h, i)) = st
rot1 = ((g, d, a),
(h, e, b),
(i, f, c))
rot2 = ((i, h, g),
(f, e, d),
(c, b, a))
rot3 = ((c, f, i),
(b, e, h),
(a, d, g))
return [st, rot1, rot2, rot3]
def apply_all_symmetry_operations(st: State) -> List[State]:
mir = get_vertical_mirror(st)
return get_rotations(st) + get_rotations(mir)
all_symmetries = apply_all_symmetry_operations(st)
duplicates_removed = list(dict.fromkeys(all_symmetries))
return duplicates_removed
Weird indentations are for visual readability. Because a state is geometrically, I thought it is legit to split code into multiple lines to increase readability. (fmt: on/off can be used to prevent Black from reformatting those lines.)
Each board configuration can be rotated 90 degrees 3 times. And the same can be done to its mirror (either horizontal to vertical). We compute rotation and mirror operations manually, by adjusting the positions of a, b, c, ... in the tuples. In total there are 8 symmetry operations that can be applied to a state which'll produce a state in the same symmetry group.
Sometimes two operations will result in the same state. Symmetry group should only include distinct configurations. So, as a last step, after we apply 8 operations (1 identity, 3 rotations, 1 mirror, and 3 rotations on the mirror) we take distinct states among them and return their list as the symmetry group. Which can be done via the list(dict.fromkeys(array)) trick that removes duplicates in a list. (See these two tweets by Python core developer Raymond Hettinger 1, 2 on the introduction of dict.fromkeys() to Python and how regular Python dicts now hold the order of insertion, hence above trick can be used to remove duplicates using dict keys as a hash map.
Then, we need to tell whether a given state is a game-ending configuration or not. Which can be done by checking whether any of the rows, columns and diagonals (lines) have all identical non-identical tiles.
def is_end(st: State) -> bool:
def are_same(triplet):
a, b, c = triplet
return a == b == c != 0
horizontals = [[st[ix][0], st[ix][1], st[ix][2]] for ix in range(3)]
verticals = [[st[0][ix], st[1][ix], st[2][ix]] for ix in range(3)]
diag1 = [st[0][0], st[1][1], st[2][2]]
diag2 = [st[2][0], st[1][1], st[0][2]]
lines = horizontals + verticals + [diag1, diag2]
return any(are_same(line) for line in lines)
We need to be able to make a move on a given state, a move being writing a marker on a given tile. We don't do any checks on whether it was a legit move, whether it happened inside the borders of the board or even whether it was an X or O. Keeping consistency is left as a responsibility of the call-site. Since the code is small, it is easy to keep in mind.
def make_move(st: State, row: int, col: int, val: int) -> State:
mutable_st = [list(r) for r in st]
mutable_st[row][col] = val
new_st = tuple(tuple(r) for r in mutable_st)
return new_st
Also note that, because tuples are immutable, a new state is created for each move. This was the reason why I've chosen tuples to represent a state, instead of an int. It's easier to make a mistake with an in-place operation on a mutable objects.
Then we need a way to compute all legit moves on a given state. If a given state is a game-ending state, then it has no next states. Otherwise, we go over all tiles, skip them if they are not empty. And for each empty tile we create a new state by putting an X or an O there. Because players play in turns, assuming that empty board is step=0, then we place Xs at odd steps Os at even steps. Therefor, other than the State itself, step should be given as an argument too.
def get_next_states_raw(st: State, step: int) -> List[State]:
next_states = []
if is_end(st):
return []
new_val = step % 2 + 1
for row in range(3):
for col in range(3):
val = st[row][col]
if val == 0:
new_st = make_move(st, row, col, new_val)
next_states.append(new_st)
return next_states
Compute the DAG of all unique game states
Given above functionality, now we are ready to compute the graph. This is the most cluttered part of the code. It's written as a script that manipulates some global variables. It could have been written in a class, but since it is only going to be used once, I didn't bother to design a class.
However, a better designed, higher abstraction approach could be to have a framework that asks the rule of a game in terms of 1) a board configuration class, 2) initial board state, 3) a list of symmetry operations under which boards are symmetric 4) a function that computes next legitimate states. 5) A class that computes the DAG given previous items. For example, this framework can be applied to Connect Four too.
The computation goes as follows. We start a Depth First Search/Traversal starting from the root node of empty board state symmetry group. At each step of DFS we compute groups of next possible states of each Node.
If any of those next groups has not seen/processed yet, we register it, and set it's node as a successor of current node. Since successors of this new node is not computed it yet, we append it into the queue to be processed at the next step of DFS.
Otherwise, if the group already exists, we just set its node as a successor without creating a second node with the same group. That's when to paths merge into the same node. For example these two paths merge at their 3rd steps (X to top left) -> (O to top center) -> (X to center) and (X to center) -> (O to top center) -> (X to top left).
We keep the state of computation in following variables: states = {} is a map from states to group ids of symmetry groups they belong to. groups = {} is a map from GroupIds to symmetry groups they identify, it's the "registry" of the groups. nodes = {} is the map from GroupIds to graph nodes that store them and their successors.
Helper function to update global state when a new state is discovered. It needs to be given an incremented group id. It computes the symmetry group, register it to groups and let the state know that computed states belongs to that group.
def add_symmetry_group(st: State, gid: GroupId):
global states, groups
symmetry_group = get_symmetries(st)
groups[gid] = symmetry_group
states.update({st: gid for st in symmetry_group})
We initialize with group id counter gid = 1. Add symmetry group of empty board to state. Create a graph node for it, register the node. Increment GroupId counter and append the node to DFS queue.
add_symmetry_group(empty_board_state, gid)
root = Node(gid)
nodes[gid] = root
gid += 1
q = deque([root])
DFS can be decomposed into two parts, first on is looping over 9 steps, and at each step, looping over the items in the queue, pop each of them, process them, if they result in novel nodes add new ones to the queue.
print("step, unique_state_no")
for step in range(9):
print(f"{step}, {len(q)}")
for _ in range(len(q)):
compute_and_queue_successors(q.pop())
We'll print the number of nodes for each step of the games.
The computation and queuing of successor nodes is the hairiest part of the code, which was explained above.
def compute_and_queue_successors(nd: Node) -> None:
global groups, nodes, q, gid
sym_group = groups[nd.val]
# first state of a group is its representative state
canonical_state = sym_group[0]
next_states = get_next_states_raw(canonical_state, step)
for nxt_st in next_states:
# have seen/processed this state before?
if nxt_st in states:
gid_old = states[nxt_st]
# merge this path with other paths leading to this node
# if it is not already merged (i.e. if not a successor
# of current node)
if gid_old not in [suc.val for suc in nd.successors]:
nd.successors.append(nodes[gid_old])
continue
# is it an unseen/unprocessed state?
add_symmetry_group(nxt_st, gid)
new_nd = Node(gid)
nodes[gid] = new_nd
nd.successors.append(new_nd)
q.appendleft(new_nd)
gid += 1
Results
0, 1
1, 3
2, 12
3, 38
4, 108
5, 174
6, 204
7, 153
8, 57
9, 15
10, 0
We start with the root node, empty board, at step=0. 3 unique configurations at step 1 can be these following.
> print_states([groups[nd.val][0] for nd in root.successors])
100 010 000
000 000 010
000 000 000
Remember that these are canonical representations of their symmetry groups. Any X at corner is equivalent to the first one, any X at side center is equivalent to second one, and X at center is the only state in its symmetry groups.
And similarly, the successors of X at the center first step are
> print_states([groups[nd.val][0] for nd in root.successors[2].successors])
200 020
010 010
000 000
which are printed via the debug methods.
Number of unique states first increase as the game moves forward, however, around step=5 we start hitting ending states and those nodes are sinks. And number of distinct states start decreasing after step=6. We don't have any states for step=10 because at step=9 the board if full. Apparently the board can be filled with 15 unique states.
Total number of distinct state through which the game can flow is 765. At this point I was ready to open Wikipedia to find the correct number. Game complexity article in it's Tic-Tac-Toe section says "when rotations and reflections of positions are considered identical, there are only 765 essentially different positions." Boom! Decade long back and forth effort ended happily. ^_^
Same article defines two types of complexities for a game. "The state-space complexity of a game is the number of legal game positions reachable from the initial position of the game." and "The game tree size is the total number of possible games that can be played: the number of leaf nodes in the game tree rooted at the game's initial position. The game tree is typically vastly larger than the state space because the same positions can occur in many games by making moves in a different order" Note that we computed the state-space graph. To get the size of the game tree size we need to compute the number of paths from the root node to each leaf node.
Visualization
We can't stop before visualizing this grap!. We'll plot it using matplotlib and networkx libraries. The graph is very big, which makes it very hard to get a sensible visualization out of it (like it is hard to visualize Solar system in correct proportions, the radii of different trajectory vary wildly).
A NetworkX graph can be constructed from a list of edges. Let's traverse the graph to collect all edges
edges = [] # List[(GraphId, GraphId)]
def traverse(nd):
edges.extend([(nd.val, s.val) for s in nd.successors])
for s in nd.successors:
traverse(s)
traverse(root)
Then create the graph.
import networkx as nx
G = nx.DiGraph()
G.add_edges_from(edges)
If we visualize is using the standard layouts provided by the library, we'll ignore the structural hierarchy of the graph, namely, grouping of nodes into steps, and how it flows into a single direction, in a "tree-like" manner, where sometimes branches merge.
import matplotlib.pyplot as plt
fig, ax = plt.subplots(figsize=(15, 15))
nx.draw_networkx(G, pos=nx.spring_layout(G), ax=ax)
Above is using "spring layout" where internal structure is lost. After some online search, learned that 1) I can draw an image for nodes, and 2) using graphviz it is possible to impose the inherent hierarchy to node distribution of the visualization.
pos = nx.nx_agraph.graphviz_layout(G, prog='dot')
computes the (x, y) positions of nodes on a canvas using Graphviz' dot program.
levels = [0, 1, 2, 3]
colors = ['gray', 'blue', 'red']
cmap, norm = matplotlib.colors.from_levels_and_colors(levels, colors)
creates an absolute color map where 0 is gray, 1 is blue and 2 is red.
fig, ax = plt.subplots(figsize=(50, 10))
for gid, (x, y) in pos.items():
sym_grp = groups[gid]
state = sym_grp[0]
node_image = OffsetImage(state, zoom=3.0, cmap=cmap, norm=norm)
box = AnnotationBbox(node_image, (x, y), frameon=False, pad=0.1)
ax.add_artist(box)
nx.draw(G, pos, with_labels=False, arrows=True, width=0.2, ax=ax, node_size=1, alpha=0.5)
and finally let matplotlib waste less screen real-estate on padding and save the graph in PDF and PNG format with high DPI.
plt.tight_layout()
plt.savefig("tic-tac-toe_game_state_graph.pdf", dpi=300)
plt.savefig("tic-tac-toe_game_state_graph.png", dpi=300)
The computation of the graph is the fastest part. Computing the visualization and saving them as files take orders of magnitude longer them. Here is final visualization:
- for higher resolution PNG click: here
- and even higher resolution PDF click: here
- code of this short project is on Github: https://github.com/vug/tic-tac-toe-game-states-graph
tags: python