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

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

# This counts the number of Tic Tac Toe positions in the full DAG.
# It detects duplicates but not symmetries.
def countTicTacToeDAG():
    tt = TranspositionTable()
    t = TicTacToe()
    positionsAtDepth = [0] * 10
    countAtDepth(t, 0, positionsAtDepth, tt)
    print("Tic Tac Toe positions in DAG model: ", positionsAtDepth)

def countAtDepth(state, depth, positionsAtDepth, tt):
    result = tt.lookup(state.code())
    if result != None:
        return
    tt.store(state.code(), True)
    positionsAtDepth[depth] += 1
    if state.endOfGame():
        return
    for i in range(9):
        if state.board[i] == EMPTY:
            state.play(i)
            countAtDepth(state, depth + 1, positionsAtDepth, tt)
            state.undoMove()

countTicTacToeDAG()