Theory of Computer Games, NTU Homework #2 Due date: 2:20pm, December 27, 2012. Description: Write a program that plays 9*9 Hex with Monte-Carlo game tree search techniques. The purpose of this homework is to ask you to master the basic techniques of Monte-Carlo tree search, not to test your efforts in designing GUI. Input: (standard input) A game board and a number indicating the time limit. Output: (standard output) The cell you selected to play. Input format: cell numbering: 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 In this game board, for example, cell 33 is connected with cells 24, 25, 32, 34, 41, 42. The first player X wins by connecting a cell in the topmost row to a cell in the bottommost row with 'X'. The second player O wins by connecting a cell in the leftmost column to a cell in the rightmost column with 'O'. A cell is either 'X', 'O', or '.'. There will be 9+1 lines in the input. There are exactly i space(s) in the i-th line (for i<=9). There is a space between any two adjective cells in the same row. The last line contains an integer between 3~10 (inclusive), which is the time limit (in seconds). Sample Input: . . . . . . . . X . . . . . . X X O . . X . . O O X . . X O . . X X O . . . . O O . X X X . O X O O O O O O O X . X X X X X X . X . O O . O O O . . . . . . . . X 3 Sample Output: // note that we have 21 'X' and 20 'O', so the next player is O. 38 Solution Package: 1. Source Code 2. Report Explaining the techniques you implemented and the coefficients you picked. Explain how they are picked. 3. Need to implement at least UCB, UCT and progressive pruning. The rest are bonus.