write program that can play tic-tac-toe effectively (see section to do thisyou will need to create game tree twhich is tree where each node corresponds to game configurationwhichin this caseis representation of the tic-tac-toe board the root node corresponds to the initial configuration for each internal node in tthe children of correspond to the game states we can reach from ' game state in single legal move for the appropriate playera (the first playeror (the second playernodes at even depths correspond to moves for and nodes at odd depths correspond to moves for external nodes are either final game states or are at depth beyond which we don' want to explore we score each external node with value that indicates how good this state is for player in large gameslike chesswe have to use heuristic scoring functionbut for small gameslike tic-tac-toewe can construct the entire game tree and score external nodes as indicating whether player has windrawor lose in that configuration good algorithm for choosing moves is minimax in this algorithmwe assign score to each internal node in tsuch that if represents ' turnwe compute ' score as the maximum of the scores of ' children (which corresponds to ' optimal play from vif an internal node represents ' turnthen we compute ' score as the minimum of the scores of ' children (which corresponds to ' optimal play from vp- write program that takes as input fully parenthesizedarithmetic expression and converts it to binary expression tree your program should display the tree in some way and also print the value associated with the root for an additional challengeallow for the leaves to store variables of the form and so onwhich are initially and which can be updated interactively by your programwith the corresponding update in the printed value of the root of the expression tree