Updates

Feb 6: updated description of boardsize to not refer to clear_board anymore. Feb 3: removed clear_board command, you do not need to write it.

CMPUT657 Assignment 2 - Two Player Game - Clobber

Due Feb 22, 11:59pm.
Submit all in one archive file (.zip or .tar.gz) by email to mmueller. Clobber is a recent two player board game. In this assignment you write a program to play this game as well as possible.

Required Reading and Some Clobber Links

Task of this Assignment

Write a Clobber player that can do one thing:

Program requirements

As in assignment 1, your program will be tested on muriel, and both muriel and muriel1 are available for testing. You can use the sample codes provided in class, but you are free to use any solution method that you like. You can also use and modify the Fuegito library. You can use standard libraries but no further specialized libraries for heuristic search or games. In case of doubt please ask the instructor before using it.

Your program executable's name: see below. Your program should use a subset of the GTP protocol, as specified below. It should read GTP commands from standard input (e.g. stdin, cin) and write responses to standard output (stdout, cout). You can write other things to standard error for debugging - they will be ignored. Note: be sure to flush your output buffers after each write. If your output is written to a buffer, but not flushed, your output may be lost or incomplete.

Program Restrictions

GTP Commands - Input and Output

Your program will implement the following subset of standard GTP, version 2, adapted to Clobber. The input can be any of the commands below. The output is stated in each case. Each output starts with the characters "= ", followed by the output listed below. Even when the output is listed as (none), you need to respond to a command with "= ", followed by a newline '\n'.

Move format for Input and Output

For readability, we change the move format from Assignment 1, to the usual letter-number style used e.g. by Fuegito. Using letters is not a problem in this assignment since the board size is limited to 10.

Rows are numbered from 1 (at the bottom) to n (at the top), where n is the board size. Columns are lettered a,b,c... from the left.

Moves are specified by the coordinates of from and to squares, as in a1a2 or e5d5.

Examples:

   a b c 
 
3  O X O  3
2  X O X  2
1  O X O  1
 
   a b c 
   a b c d e f 
 
6  X O X O X O  6
5  O X O X O X  5
4  X O X O X O  4
3  O X O X O X  3
2  X O X O X O  2
1  O X O X O X  1
 
   a b c d e f 
    a b c d e f g h i j 
 
10  X O X O X O X O X O  10
 9  O X O X O X O X O X   9
 8  X O X O X O X O X O   8
 7  O X O X O X O X O X   7
 6  X O X O X O X O X O   6
 5  O X O X O X O X O X   5
 4  X O X O X O X O X O   4
 3  O X O X O X O X O X   3
 2  X O X O X O X O X O   2
 1  O X O X O X O X O X   1
 
    a b c d e f g h i j 

Initial Position

The initial board position is a checkerboard pattern, with point a1 being white. See examples above.

GTP Commands to implement

boardsize n
Set board to size n, with 3 <= n <= 10, and initialize it to a checkerboard pattern as explained in "Initial Position" above. Black always moves first.
Output: (none)
genmove
Output: 'move-spec'
Generate a legal move for the color whose turn it is, and play it. Move-spec is in the format above. If there is no legal move, your program must send "resign".
play 'move-spec'
Play a legal move for the color whose turn it is. Move-spec is in the format above.
Output: (none)
name
Output: The name of your program as a string.
version
Output: The version of your program. A string of your choice, such as 0.0.1
protocol_version
Output: Return 2 since we're implementing the current version of GTP which is 2.
showboard
(Optional) Show the current board in some human-readable format.
Output: board state, e.g. as in Fuegito or in setboard for assignment 1.
timelimit n
Set the time limit to n seconds for the whole game, with 10 <= n <= 1000. Your program will have to manage the time to use for each move.
Output: (none)

Example - How to Play a Game

Here is how a typical test game will proceed:
  1. The game manager starts up and connects to both programs.
  2. It sends both players the initial position with boardsize
  3. It sends both players the timelimit.
  4. It then asks the Black player for the first move by sending it a genmove command.
  5. After receiving 'move' from Black, it sends White a play 'move' command, followed by a genmove command to ask the White player for its answer.
  6. The manager keeps issuing genmove commands and play commands until one player generates resign, which ends the game.
  7. The manager also keeps track of time used by both, and if one player exceeds their time limit it ends the game.
I may or may not have time to prepare a sample game manager before the due date. But I will try. You can look at gogui-twogtp for an example of a game manager for the game of Go.

Sample start of Game

Manager ==> Black:
boardsize 3

Black ==> Manager:
=

Manager ==> White:
boardsize 3

White ==> Manager:
=

Manager ==> Black:
timelimit 10

Black ==> Manager:
=

Manager ==> White:
timelimit 10

White ==> Manager:
=

Manager ==> Black:
genmove

Black ==> Manager:
= a2a3

Manager ==> White:
play a2a3

White ==> Manager:
=

Manager ==> White:
genmove

White ==> Manager:
= c1b1

Testing

Tests will consist of games played between all programs, including some reference opponents to be defined.

Deliverables

Submit exactly the following. No extra files, use the names required.
  1. Put all items below into a single directory, named your lastname_firstname. Compress this directory into a single file using zip or tar.gz and email to mmueller before the deadline.
  2. An executable named a2-name that will run on muriel. name should be the name of your program as returned by your GTP command name.
  3. A directory called source, containing your source code and an automated way to build it such as a Makefile. The build needs to re-produce your executable when run as-is on muriel. No extra installation steps please.
  4. A file named your lastname_firstname_documentation.pdf . This file will contain a 4-5 page description of your program. The first section will be build instructions. (short, such as: go to source directory and type make.) The rest of the document should focus on what is special about your program. Do not discuss rules of Clobber, content of papers, standard search algorithms, coding tricks etc.

Evaluation

Your program will be evaluated by playing it against opponent players as above. The weights will be

Questions and Answers

Q: Fuegito is a bit different than what you ask us to do. Why?
A: That's just the way it is. It also has some bugs. I may or may not have time before the due date to prepare a version that works well with our assignment spec. Don't rely on it.

(End of Assignment 2)