Tic-Tac-Toe: The extensive-form representation of a game can be cumbersome even for very simple games. Consider the game of tic-tac-toe, in which two players mark "X" or "O" in a 3 × 3 matrix. Player 1 moves first, then player 2, and so on. If a player gets three of his kind in a row, column, or one of the diagonals then he wins, and otherwise it is a tie. For this question assume that even after a winner is declared, the players must completely fill the matrix before the game ends.
a. Is this a game of perfect or imperfect information? Why?
b. How many information sets does player 2 have after player 1's first move?
c. How many information sets does player 1 have after each of player 2's moves for the first time?
d. How many information sets does each player have in total? (Hint: For this and part (e) you may want to use a spreadsheet program like Excel.)
e. How many terminal nodes does the game have?