I want to know the exact number of legal states for Tic Tac Toe order 5 (25 cells), for each of the 25 turns. I need it to determine recursion depth of my AI.
So below are the rules of Tic Tac Toe for order n I am using:
There are n rows and n columns on a board, for a total of $n^2$ cells.
All cells are initially empty.
There are two players, each player take turns alternatively, no player can move in two consecutive turns.
Game ends when one player has filled n cells of the same row, column or diagonal. Or the whole board is filled.
So without any consideration of the rules above, each cell can be in 3 states, naively the absolute upper bound of number of states for order n is $3^{n^2}$, for orders 3, 4, 5 they are 19,683, 43,046,721 and 847,288,609,443 respectively. Of course, most of them are illegal and cannot be reached via normal gameplay.
I have programmatically checked all Tic Tac Toe states for order 3 and 4.
from typing import List, Tuple
def pack(line: range, last: int) -> int:
return (sum(1 << last - i for i in line), tuple(line))
def generate_lines(n: int) -> List[Tuple[int, Tuple[int]]]:
square = n * n
last = square - 1
lines = []
for i in range(n):
lines.extend(
(
pack(range(i * n, i * n + n), last),
pack(range(i, square, n), last),
)
)
lines.extend(
(
pack(range(0, square, n + 1), last),
pack(range((m := n - 1), n * m + 1, m), last),
)
)
return lines
LINES = [generate_lines(i) for i in (3, 4, 5)]
def check_state_3(board: Tuple[int, int, int]) -> Tuple[bool, int]:
for line, _ in LINES[0]:
for i in (0, 1):
if board[i] & line == line:
return True, i
return board[2].bit_count() == 9, None
GAMESTATES_3_P1 = set()
GAMESTATES_3_P2 = set()
POSITIONS = [[1 << i for i in line[::-1]] for line in [range(9), range(16), range(25)]]
def tally_states_3(board: Tuple[int, int, int], move: bool, states: set) -> None:
if board not in states:
if not check_state_3(board)[0]:
o, x, full = board
for i in POSITIONS[0]:
if not full & i:
if move:
tally_states_3((o, x | i, full | i), 0, states)
else:
tally_states_3((o | i, x, full | i), 1, states)
states.add(board)
tally_states_3((0, 0, 0), 0, GAMESTATES_3_P1)
tally_states_3((0, 0, 0), 1, GAMESTATES_3_P2)
def check_state_4(board: Tuple[int, int, int]) -> Tuple[bool, int]:
for line, _ in LINES[1]:
for i in (0, 1):
if board[i] & line == line:
return True, i
return board[2].bit_count() == 16, None
def tally_states_4(board: Tuple[int, int, int], move: bool, states: set) -> None:
if board not in states:
if not check_state_4(board)[0]:
o, x, full = board
for i in POSITIONS[1]:
if not full & i:
if move:
tally_states_4((o, x | i, full | i), 0, states)
else:
tally_states_4((o | i, x, full | i), 1, states)
states.add(board)
GAMESTATES_4_P1 = set()
GAMESTATES_4_P2 = set()
tally_states_4((0, 0, 0), 0, GAMESTATES_4_P1)
tally_states_4((0, 0, 0), 1, GAMESTATES_4_P2)
print(len(GAMESTATES_3_P1))
print(len(GAMESTATES_3_P2))
print(len(GAMESTATES_3_P1 | GAMESTATES_3_P2))
print(len(GAMESTATES_4_P1))
print(len(GAMESTATES_4_P2))
print(len(GAMESTATES_4_P1 | GAMESTATES_4_P2))
5478
5478
8533
9722011
9722011
14782023
So for Tic Tac Toe order 3, there are 5478 legal states reachable if player X moves first, this counts all reflections and rotations as distinct boards. There are also 5478 states reachable if player O moves first. For a total of 8533 unique states. I have reached the same counts using various methods and I have verified the correctness of the results thoroughly.
It took quite some time and Gibibytes of RAM to crunch the numbers for order 4. So 9722011 states are reachable if either player moves first, and 14782023 states in total.
My result is the same as what I got from this answer.
N: 1 2 3 4
------- - -- ---- -------
ply 0: 1 1 1 1
ply 1: 1 4 9 16
ply 2: - 12 72 240
ply 3: - 12 252 1680
ply 4: - 0 756 10920
ply 5: - - 1260 43680
ply 6: - - 1520 160160
ply 7: - - 1140 400400
ply 8: - - 390 895950
ply 9: - - 78 1433520
ply 10: - - - 1962576
ply 11: - - - 1962576
ply 12: - - - 1543080
ply 13: - - - 881760
ply 14: - - - 333792
ply 15: - - - 83440
ply 16: - - - 8220
======= = == ==== =======
TOTAL: 2 29 5478 9722011
-------
Obviously I cannot use the same method to enumerate all the valid states for order 5.
According to the answer:
There are ${{N^2} \choose x}$ ways to place $x$
Xmarks on an $N\times{}N$ board.There are ${{N^2 - x} \choose o}$ ways to place $o$
Omarks on an $N\times{}N$ board that is already filled with $x$Xs.
Hence ignoring winners there are:
${{N^2} \choose x} \times {{N^2 - x} \choose o}$
distinct boards at ply $p$. Or (plugging the definitions of $x$ and $o$ from above):
${{N^2} \choose {floor({{p+1}\over{2}})}} \times {{N^2 - {floor({{p+1}\over{2}})}} \choose {floor({p \over 2})}}$
So I have tried to calculate the number using the formula:
from typing import List
class Pascal_Triangle:
def __init__(self, end_row: int = 3):
self.data = [[1], [1, 1], [1, 2, 1]]
self.length = 3
if end_row > 3:
self.add_rows(end_row)
def add_rows(self, end_row: int):
last_row = self.data[-1]
for n in range(self.length, end_row):
mid = n // 2 + 1
row = [a + b for a, b in zip(last_row, last_row[1:mid])]
self.data.append(last_row := [1] + row + row[mid - 3 + n % 2 :: -1] + [1])
self.length = end_row
def pretty_print(self):
longest = len(str(self.data[-1][self.length // 2]))
line_length = (longest + 1) * (self.length - 1) + longest
for row in self.data:
print(" ".join(f"{n:^{longest}}" for n in row).center(line_length))
print()
def choose(self, r: int, c: int) -> int:
if r + 1 > self.length:
self.add_rows(r + 1)
return self.data[r][c]
PT = Pascal_Triangle(26)
def count_boards(n: int) -> List[int]:
square = n * n
boards = []
counts = [0, 0]
for i in range(square + 1):
a, b = counts
boards.append(PT.choose(square, a) * PT.choose(square - a, b))
counts[i % 2] += 1
return boards
I got the following results:
In [78]: print(count_boards(3))
[1, 9, 72, 252, 756, 1260, 1680, 1260, 630, 126]
In [79]: print(count_boards(4))
[1, 16, 240, 1680, 10920, 43680, 160160, 400400, 900900, 1441440, 2018016, 2018016, 1681680, 960960, 411840, 102960, 12870]
In [80]: print(count_boards(5))
[1, 25, 600, 6900, 75900, 531300, 3542000, 16824500, 75710250, 257414850, 823727520, 2059318800, 4805077200, 8923714800, 15297796800, 21034470600, 26293088250, 26293088250, 23371634000, 16360143800, 9816086280, 4461857400, 1622493600, 405623400, 67603900, 5200300]
In [81]: print(sum(count_boards(3)))
6046
In [82]: print(sum(count_boards(4)))
10165779
In [83]: print(sum(count_boards(5)))
161995031226
It is clear the numbers are not exact, since it is clearly stated that the counts disregard winners. These counts include states that can only be reached when the game didn't end when there is a winner, which is illegal. More specifically, the numbers are larger from turn 2n onward.
Is there a way to calculate the exact value of number of valid Tic Tac Toe boards for order n?