$.$ Problem Description

You are to develop a program that plays the perfect game of Tic$-$tac$-$toe. It should never lose. Your

project can be done in three steps of increasing complexity.

$$ Basic Level $($for a maximum grade of $75\%)$: Develop the Tree ADT as an array$-$based concrete

implementation.

$$ Intermediate Level $($for a maximum grade of $88\%)$: Your program will then create every possible

Tic$-$tac$-$toe board configuration organized as a tree.

$$ Advanced Level $($for a maximum grade of $100\%)$: Once the configurations have been calculated,

you will employ a minimax algorithm to evaluate each position. When playing the game, the user

will go first $($X$)$ and the computer $($O$)$ must respond with the move that maximizes its chances of

victory. If done correctly, the computer will never lose. However, most games played with a

competent human will end in a draw $($a $$Cat$$s Game$).$