Theory of Computer Games, NTU

Homework #2

Due date: 2:20pm, December 19, 2013.

Description:
Write a program that plays 7*7 KillAllGo 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/Output: (standard input/output)
Your program takes the following comments from the screen and then reacts.
1. reset: empty the board
2. time i: set the search time limit to be i seconds, default value is 10,
           i is a positive integer
3. put b/w x y: put a black/white stone at (x,y), 1 <= x,y <=7
4. display: print the whole board and the time limit using a format set by you
   print a black stone as "X", a white stone as "O" and an empty cell as "."
5. start game: from now on every ply is recorded and no loops is allowed
6. think b/w: think in turns of black/white and output x y within the time limit
              the output is 0 0 if it decides to pass
7. quit: end of execution

A sample session:
>reset
>ok
>time 15
>ok
>reset
>ok
>display
time limit=15
.......
.......
.......
.......
.......
.......
.......
>put b 2 2
>ok
>put b 6 2
>ok
>display
time limit=15
.......
.......
.......
.......
.......
.X...X.
.......
>start game
>ok
>think w
>3 5
>display
time limit=15
.......
.......
..O....
.......
.......
.X...X.
.......
>put b 6 6
>ok
>display
time limit=15
.......
.O...X.
.......
.......
.......
.X...X.
.......

Rules for KillAllGo:

1. The black wins if there is no white stone left after placing a black stone.
2. The white wins if there is some white stones left at the end.
   Namely, the white has a string with 2 eyes;
   or the black cannot make any ply without killing itself.
   example:
   .O.O.O.
   O.O.O.O
   .O.O.O.
   O.O.O.O
   .O.O.O.
   O.O.O.O
   .O.O.O.
3. You cannot make a ply so that the resulting position has happened before.
   No loops is allowed at any time.
4. A block of connected stones is captured and removed if it has no liberty.
5. One loses if the time limit exceeds.

Solution Package:
1. Source Code
2. Report
   Explain 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.