# Cmput 455 sample code
# Count number of TicTacToe states in the tree model (not DAG)
# Written by Martin Mueller

from game_basics import EMPTY, BLACK, WHITE
from tic_tac_toe import TicTacToe

                
# Count the number of Tic Tac Toe positions in the full game tree
# It does not detect duplicates or symmetries
# So the numbers are much larger than for the DAG computation
def countTicTacToeTree():
    t = TicTacToe()
    positionsAtDepth = [0] * 10
    countAtDepth(t, 0, positionsAtDepth)
    print("Tic Tac Toe positions in tree model: ", positionsAtDepth)

def countAtDepth(t, depth, positionsAtDepth):
    positionsAtDepth[depth] += 1
    if t.endOfGame():
        return
    for i in range(9):
        if t.board[i] == EMPTY:
            t.play(i)
            countAtDepth(t, depth + 1, positionsAtDepth)
            t.undoMove()

countTicTacToeTree()