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)

What about symmetries?

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

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)

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[0]^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[0]^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)

Adding a cache

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[0] 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[0]^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[0]^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)

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.

SM-6-GamesAndSymmetry

4687 days ago by MathFest