- write program that can play tic-tac-toe effectively (see section to do thisyou will need to create game tree which is tree where each position corresponds to game configurationwhichin this caseis representation of the tic-tac-toe board (see section the root corresponds to the initial configuration for each internal position in the 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 playerpositions at even depths correspond to moves for and positions at odd depths correspond to moves for leaves are either final game states or are at depth beyond which we do not want to explore we score each leaf 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 leaves 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 position in such that if represents ' turnwe compute ' score as the maximum of the scores of ' children (which corresponds to ' optimal play from pif an internal node represents ' turnthen we compute ' score as the minimum of the scores of ' children (which corresponds to ' optimal play from pp- implement the tree adt using the binary tree representation described in exercise - you may adapt the linkedbinarytree implementation - write program that takes as input general tree and position of and converts to another tree with the same set of position adjacenciesbut now with as its root notes discussions of the classic preorderinorderand postorder tree traversal methods can be found in knuth' fundamental algorithms book [ the euler tour traversal technique comes from the parallel algorithms communityit is introduced by tarjan and vishkin [ and is discussed by jaja [ and by karp and ramachandran [ the algorithm for drawing tree is generally considered to be part of the "folkloreof graph-drawing algorithms the reader interested in graph drawing is referred to the book by di battistaeadestamassiaand tollis [ and the survey by tamassia and liotta [ the puzzle in exercise - was communicated by micha sharir