# Games and Symmetry

### Daniel Warner

My ultimate goal is determine whether the game Pentago is a first player win.  But  I need to start by getting my computational ducks in line.  So, lets examine an old standby.

## Tic-Tac-Toe

Let's examine the possible 3-by-3 Tic-Tac-Toe boards.

T = [1 2 3;

4 5 6;

7 8 9]

If we label the squares from left to right, top to bottom, then each possible game can be represented by a sequence of the numbers from 1 to $n^2$, where none of the numbers is repeated.  This follows from the fact that each play consists of marking a square that has not yet been marked.  An upper bound on the number of possible games is the size of the set of all permutations of the $n^2$ numbers, that is, $n^2$ factorial.

What are these upper bounds for the $n=2$, $3$, $4$, and $6$ Tic-Tac-Toe games?

Which of these these bounds are strictly larger than the actual number of possible games and why?

for N in [2,3,4,6]: print N," ",N^2,"! = ", factorial(N^2)

For $n$ greater than 2, the numbers, $(n^2)!$, overestimate the number of games because if a game ends in $k$ moves, then that game is the initial sequence of $(n^2-k)!$ permutations.  None of those permutations will be examined further.

Note that for $n=2$, $4!$ is exactly the number of games.  White always wins in 3 moves, and Black would only have one square to play if the game were not already over.

Write a program that, given $n$, will play all $(n^2)!$ sequences of moves.
It should not check for wins and thus should continue until all $n^2$ moves have been made.

Now consider a program that, given $n$, will play all $(n^2)!$ "games".  It will not check for wins, but it will simply count the number of "games" (complete sequences) that were generated and print the final count.

def TTT01(N): white = 1 board = [0 for i in range(N*N)] game = [] count = 0 for i in range(N*N): count = move1(N, board, game, white, i, 1, count) print count def move1(N, board, game, p, move, level, count): # white = +1 # black = -1 board[move] = p game.append(move) if level == N*N: count += 1 if N == 2: print board, game else: q = -p for i in range(N*N): # print level,i,board if board[i]==0: count = move1(N, board, game, q, i, level+1, count) board[move] = 0 game.pop() return count

Here are the intermediate results, when we run the program for the $n=2$ case.

TTT01(2)

Here is the time and the count for running the program for the $n=3$ case.

time TTT01(3)

A very rough estimate for how long the $n=4$ case might take would be to multiply the time for the $n=3$ case by the ratio of $(4^2)! / (3^2)!$.

However, this is may be a significant overestimate since tails that get ignored when a game ends are probably a lot larger than for the $n=3$ case.

Estimated_Time = factorial(4^2)/factorial(3^2) * 3.08 print Estimated_Time, "seconds" print Estimated_Time/60, "minutes" print Estimated_Time/(60*60), "hours" print Estimated_Time/(60*60*24), "days" print Estimated_Time/(60*60*24*365), "years"

How much does it help to check for wins?  One way to calculate a win is to examine all the rows, columns, and diagonals after every move.  However, a more succinct approach is to keep an array corresponding to each of the possible wins, which will be $2n+2$ for an $n$-by-$n$ board.  This give rise to the following code.

Write a program that, given $n$, will play all $(n^2)!$ games''.
It should not check for wins and thus should continue until all possible $n^2$ moves have been made.
If $n=2$, then your program should print enough intermediate results to confirm that it is working correctly.
For all other values of $n$ your program should not print out any intermediate results, but it should simply
count the number of games'' (complete sequences) that were generated and print the final count.
def win_check(N, wins, i, j, update): # wins is an 2N+2 array with one entry for each winning row, column, and diagonal # update indicates the player. It is +1 for White and -1 for Black # This convention makes it easy to update and downdate the array. wins[i] += update wins[N+j] += update if i==j: wins[2*N] += update if i+j == N-1: wins[2*N+1] += update if abs(wins[i])==N or abs(wins[N+j])==N or abs(wins[2*N])==N or abs(wins[2*N+1])==N: return True else: return False
# Sanity check N = 3 wins = [1,1,1,1,1,-1,2,1] win_check(N,wins,2,2,1) print wins win_check(N,wins,2,2,-1) print wins

We can modify the TTT01 function so that it checks for a win on each move and keeps track of how many wins at each level.

def TTT02(N): white = 1 board = [0 for i in range(N*N)] wins = [0 for i in range(2*N+2)] stats = [0 for i in range(N*N+1)] for i in range(N): for j in range(N): stats = move2(N, board, wins, white, i, j, 1, stats) print stats print "Total number of games: ",sum(stats) def move2(N, board, wins, p, r, c, level, stats): # white = +1 # black = -1 move = N*r + c board[move] = p if win_check(N, wins, r, c, p): stats[level-1] += 1 if N == 2: print board, wins elif level == N*N: # We have a draw stats[level] += 1 else: q = -p for i in range(N): row = N*i for j in range(N): # print level,i,board if board[row+j]==0: stats = move2(N, board, wins, q, i, j, level+1, stats) board[move] = 0 win_check(N, wins, r, c, -p) return stats

Here are the intermediate results for the $n=2$ case.

TTT02(2)

Here's the main results and the time for the $n=3$.

time TTT02(3)

The total number of games for $n=3$ is 255,168 out of the $9! =$ 362,880 possible sequences.  We can reduce the previous time estimates by that fraction, although the correct fraction is probably smaller.

Unfortunately the code to check for a win makes the program run longer.

N = 4 r = 255168/factorial(3^2) print "N:",N," r:",r Estimated_Time = r*factorial(N^2)/factorial(3^2) * 9.74 print Estimated_Time, "seconds" print Estimated_Time/60, "minutes" print Estimated_Time/(60*60), "hours" print Estimated_Time/(60*60*24), "days" print Estimated_Time/(60*60*24*365), "years"

Notice that the game that starts \{1,2,5\} is a different game from the game that starts \{5,2,1\}.
However the boards at this point are identical.
Since we can label each square as 0 if it is empty, 1 if it is marked White, and 2 if it is marked Black,
we can generate a unique number for each board.
For example, if White has marked squares 1 and 5 while Black has marked square 2, then we can
count base 3 and give this board the id $(1\cdot 3^{(1-1)} + 2\cdot 3^{(2-1)} + 1\cdot 3^{(5-1)})= 88$.
With this approach it is easy to see that there is a one-to-one correspondence between
the distinct $n$-by-$n$ boards and the numbers from 0 to
$(2 \cdot 3^0 + 2 \cdot 3^1 + \cdots + 2 \cdot 3^{(n^2-1)})$.
It follows that an upper bound for the total number of distinct boards is simply $3^{n^2}$.
\begin{itemize}
\item What are these upper bounds for the $n=2$, $3$, $4$, and $5$ Tic-Tac-Toe boards?
\item Why are these numbers larger than the actual number of possible boards?

Notice that the game that starts [1,2,5] is a different game from the game that starts [5,2,1].  However the boards at this point are identical.  Since we can label each square as 0 if it is empty, 1 if it is marked White, and 2 if it is marked Black, we can generate a unique number for each board.  For example, if White has marked squares 1 and 5 while Black has marked square 2, then we can count base 3 and give this board the id $(1\cdot 3^{(1-1)} + 2\cdot 3^{(2-1)} + 1\cdot 3^{(5-1)})= 88$.

With this approach it is easy to see that there is a one-to-one correspondence between the numbers

from 0 to $(2 \cdot 3^0 + 2 \cdot 3^1 + \cdots + 2 \cdot 3^{(n^2-1)})$ and the distinct $n$-by-$n$ boards.

It follows that an upper bound for the total number of distinct boards is simply $3^{n^2}$.

What are these upper bounds for the $n=2$, $3$, $4$, and $5$ Tic-Tac-Toe boards?

for N in [2,3,4,6]: print N," Possible boards = ", 3^(N^2)

Although this approach includes every board that can occur in a legitimate game, it also includes boards which can not occur such as a board where all the squares are marked white.  Another illegitimate board would be one where both white and black have a win.

Note that for $n=2$ the number of possible boards is larger than the number of possible games, but for larger values of $n$ the number of possible boards is orders of magnitude less that the number of possible games.

for N in [2,3,4,6]: print N, factorial(N^2), 3^(N^2)

We can reduce the number of boards even more by taking into account the group of symmetries.

Sage makes this step very easy.

Recall our labeling of the 3-by-3 Tic-Tac-Toe board.

T = [1 2 3;

4 5 6;

7 8 9]

# Define the generators for the group of symmetries of the Tic-Tac-Toe board. r = Permutation("(1,7,9,3)(2,4,8,6)") f = Permutation("(1,3)(4,6)(7,9)") r,f
# Quick check r*r;r*f;f*r
# Generate the group of symmetries for the Tic-Tac-Toe board. G = PermutationGroup([r,f]) print G
G.
print "Degree of G: ",G.degree() print "Order of G: ", G.order() print G.list()
print G.cayley_table()
g = G.an_element() print type(g)
g.

The following function is needed for automatically generating variables.

def var_gen(name): return var("%s"%(name))

Now we have the tools to automatically build the cycle index polynomial.

def cycle_index(G): var('term poly') N = G.degree() myvars = [var_gen("x%s"%(i)) for i in range(1,N+1)] poly = 0 for p in G: print p,type(p) c = p.cycle_tuples() print c,type(c) print len(c) if 0 == len(c): term = myvars^N else: term = 1 cnt = N for t in c: print t,type(t) k = len(t) term *= myvars[k-1] cnt -= k if 0<cnt: term = term*myvars^cnt poly = poly + term poly = poly / G.order() return poly
print "The cycle index polynomal" poly = cycle_index(G) show(poly) print type(poly)
# Pattern Inventory for Tic-Tac-Toe var('e k w') PTTT = expand(poly(x1=(e+w+k), x2=(e^2+w^2+k^2), x3=(e^3+w^3+k^3), x4=(e^4+w^4+k^4))) PTTT
print type(PTTT)
# R = PolynomialRing(QQ,"e,k,w") # R.inject_variables(verbose=True) R.<e,k,w> = QQ[] print R pex = R.an_element() print type(pex)
ptt = R(PTTT) print ptt print type(ptt)
ptt.

Now we can write a little routine that isolates the coefficients for the Legitimate Non-equivalent Boards.

N = G.degree() ek = N - 1 wk = 1 kk = 0 LNB = [ptt.coefficient({e:ek,w:wk,k:kk})] for cnt in range(1,N,2): ek = ek - 1 kk = kk + 1 LNB.append(ptt.coefficient({e:ek,w:wk,k:kk})) ek = ek - 1 wk = wk + 1 LNB.append(ptt.coefficient({e:ek,w:wk,k:kk})) print LNB sum(LNB)

The action of a permutation group on a function whose domain is N is defined by performing the group operations and then applying the function.

a*b*f  ::=  f(a*b)

In other words, the operations are evaluated from left to right, including the final operation which is the evaluation of the function.

def pretty_board(N,b): chars = ['b','-','w'] for i in range(N): row = [chars[b[i*N+j]+1] for j in range(N)] print row

Let's quickly verify the actions of the group of symmetries.

b = [-1, -1, 0, 0, 1, 0, 1, 0, 0] for g in G: print g p = Permutation(g) print p print p*b pretty_board(3,p*b)

The dictionary data structure encourages us to find a key for each board and then record properties for that board.

def board_num(board): r""" Determine the num for the board The TTT board is a list of 9 values each value is 0, 1, or 2. """ num = 0 pow = 1 for b in board: if b < 0: d = 2 else: d = b num += d*pow pow = 3*pow return num

Another quick verification.

board = [0,0,0,0,0,0,0,0,0] for k in range(len(board)): board[k] = floor(3*random()-1) print board_num(board),board

Now we introduce the symmetries by using as the id for each board, the smallest number of all the equivalent boards.

def board2id(board): id = 3^len(board) for g in G.list(): perm = Permutation(g) bn = board_num(perm*board) id = min(id,bn) # print bn,id return id def id2board(N,id): s = id board = [0 for i in range(N*N)] for k in range(N*N): p = s % 3 if p==2: board[k] = -1 else: board[k] = p s = s // 3 return board

Another quick check.

b1 = [1,0,0,0,0,0,0,0,0] print board2id(b1), b1 b2 = [0,1,0,0,0,0,0,0,0] print board2id(b2), b2 b3 = [0,0,0,0,1,0,0,0,0] print board2id(b3), b3 b4 = [1, 0, -1, 0, 0, 0, 0, 0, 0] print board2id(b4), b4

And yet another quick check.

# Sanity check b = [1,0,-1,0,1,-1,0,0,1] pretty_board(3,b) bn = board_num(b) print bn id = board2id(b) print id bb = id2board(3,id) pretty_board(3,bb)

### Putting it all together.

We can now investigate all the possible nonequivalent Tic-Tac-Toe games.

def TTT03(N,cache): board = [0 for k in range(N*N)] wins = [0 for k in range(2*N+2)] white = +1 for i in range(N): for j in range(N): move3(board, wins, white, i, j, N, 0, cache) print len(cache) def move3(board, wins, p, i, j, N, level, cache): # print board, wins, p, i, j, N, level, cache # white = +1 # black = -1 sq = i*N+j board[sq] = p bn = board_num(board) if cache.has_key(bn): (score,count) = cache[bn] cache[bn] = (score,count+1) else: cache[bn] = (0,1) if win_check(N, wins, i, j, p): # We have a win (score,count) = cache[bn] if score == 0: cache[bn] = (p,count) if N == 2: pretty_board(N,board) print cache elif level+1 == N*N: # We have a draw (score,count) = cache[bn] if score == 0: cache[bn] = (2,count) else: q = -p for ii in range(N): row = ii*N for jj in range(N): if board[row+jj]==0: move3(board, wins, q, ii, jj, N, level+1, cache) board[sq] = 0 # Downdate the wins data structure win_check(N, wins, i, j, -p)

Now let's run the program and display the list of the boards that are generated and the number of times each one is encountered for the $n=2$ case.

cache = {} TTT03(2,cache)
print len(cache) print cache wc = 0 wb = [] for bn in cache.keys(): (score,count) = cache[bn] if score == 1: wc += 1 wb.append((bn,count)) print wc,wb for x in wb: bn = x print bn pretty_board(2,id2board(2,bn))

Let's run the program for the $n=3$ case and time it.

cache = {} time TTT03(3,cache)
print factorial(9),3^9

## Tritego

Let's examine the possible 4-by-4 Tritego boards.

T = [ 1  2  3  4;

5  6  7  8;

9 10 11 12;

13 14 15 16]

# Define the generators for the group of symmetries of the 4-by-4 Tic-Tac-Toe board. r = Permutation("(1,13,16,4)(2,9,15,8)(3,5,14,12)(6,10,11,7)") f = Permutation("(1,4)(2,3)(5,8)(6,7)(9,12)(10,11)(13,16)(14,15)") r,f
# Quick check r*r;r*f;f*r
# Generate the group of symmetries for the Tritego board. G = PermutationGroup([r,f]) print G print "Degree of G: ",G.degree() print "Order of G: ", G.order() print G.list() print G.cayley_table() g = G.an_element() print type(g)
def cycle_index(G): var('term poly') N = G.degree() myvars = [var_gen("x%s"%(i)) for i in range(1,N+1)] poly = 0 for p in G: # print p,type(p) c = p.cycle_tuples() # print c,type(c) # print len(c) if 0 == len(c): term = myvars^N else: term = 1 cnt = N for t in c: # print t,type(t) k = len(t) term *= myvars[k-1] cnt -= k if 0<cnt: term = term*myvars^cnt poly = poly + term poly = poly / G.order() return poly
print "The cycle index polynomal" poly = cycle_index(G) show(poly) print type(poly)
# Pattern Inventory for Tritego var('e k w') PTTT = expand(poly(x1=(e+w+k), x2=(e^2+w^2+k^2), x4=(e^4+w^4+k^4))) PTTT
print type(PTTT)
R.<e,k,w> = QQ[] print R pex = R.an_element() print type(pex)
ptt = R(PTTT) print ptt print type(ptt)
N = G.degree() ek = N - 1 wk = 1 kk = 0 LNB = [ptt.coefficient({e:ek,w:wk,k:kk})] for cnt in range(1,N,2): ek = ek - 1 kk = kk + 1 LNB.append(ptt.coefficient({e:ek,w:wk,k:kk})) ek = ek - 1 wk = wk + 1 LNB.append(ptt.coefficient({e:ek,w:wk,k:kk})) print LNB sum(LNB)

At this point we can essentially duplicate the recursive search.

However, we now need to modify both the move command because it must also allow the 8 rotations.

In addition the win_check routine needs to be modified, since we now include 3 in a row on the 4-b-4 board as well as the possibility of a two-win draw.

# SC2010 in New Orleans