1. (20pt) Describe state description, move generator, terminal test and utility function for Tic-Tac-Toe game. Draw the first 3 levels of game tree. Combine all symmetry states to reduce branch factor. For example the two states below are symmetry and may be represent as one state. X X O 0 Develop an evaluation function for non-terminal states. Use examples to explain how this evaluation function works on different states.