• Added Jan 22: random test cases and test case generator
• Clarified Jan 23: for test files, each line ends with an end of line character '\n', and each test file ends with quit command

CMPUT657 Assignment 1 - Single Agent Search - Solitaire Clobber

Due Feb 1, 11:59pm.
Submit all in one archive file (.zip or .tar.gz) by email to mmueller. Clobber is a recent two player board game. Solitaire Clobber is the one-player version (or equivalently, the version where both players work together to achieve a common goal.)

Notes

• There are (at least) two different ways to define Solitaire Clobber. We choose the standard way, where like in the two player case, moves by Black and White stones alternate. (The other case, which we do not consider in this assignment, is when at each turn you can choose to move either a black or a white stones).
• Goal: minimize the number of stones remaining at the end. k-reducibility - can reduce initial position to k stones. k-reducibility - can reduce to single stone.
• Starting position: for the two-player game, it is usual to start with a ``checkerboard'' pattern where black and white stones alternate. See e.g. the wikipedia page. Reducibility for Solitaire Clobber for 1-dimensional and rectangular checkerboard patterns is solved by Demain et al - see paper above. We will look at general starting positions as follows: on a grid, not necessarily complete rectangles, neighboring stones do not need to be different color.

Write a Solitaire Clobber player that can do two things:
• Solve small positions perfectly, i.e. determine the minimal number of stones that it can be reduced to. Output this number, and a sequence of moves to achieve that result.
• Play large Solitaire Clobber positions as well as possible in limited time. Find a sequence of moves to reduce a given board to as few stones as possible.

Program requirements

Your program can be written in any language as long as it compiles and runs on our lab machines (Linux). Your program will be tested on machine X (to be determined). You can use the sample code provided in class, but your are free to use any solution method that you like. You can use standard libraries but no specialized libraries for heuristic search. In case of doubt please ask the instructor before using it.

Your program executable should be called a1. Your program should read from standard input (e.g. stdin, cin) and write to standard output (stdout, cout) as detailed below. You can write to standard error for debugging - it will be ignored. Note: be sure to flush your output buffers after writing a solution. If your output is written to a buffer, but not flushed when the program is killed by the script, your output may be lost or incomplete. Do not read/write any files.

Other details: A memory limit of 2 GB will be enforced. Time limits are given below.

Input and Output Format

1. ```setboard n m
(board description)
```
Set the current game board. Here, n is the number of rows and m the number of columns. The board description consists of n lines of text, where each line consists of m symbols. The three symbols used are 'B' for black stone, 'W' for white stone, and '.' for empty square.
Example:
```setboard 2 5
.BW.W
WBBWB
```

Limits: you can assume that both n and m are at least 1 and no larger than 100. There are no limits on the board position, so e.g. an empty board or a board filled with black stones are valid input.

Output: this command should produce no output.

2. ```solve color time-limit
```
Solve the current board optimally, with color ("b" for black or "w" for white) to play first, with the given time limit (in seconds). Solve requires you to use an exact method, which only output an answer if it is guaranteed correct. So the top function in your search must be a complete method. Your program should stop computing and print the answer only if it has solved the problem optimally. Otherwise, the program will be killed by the test script at the time limit. You can assume that there has been at least one setboard command before this command.

Example:

```solve w 1
(output:) 2 2,1-2,2 1,2-1,3 2,4-2,5 1,5-2,5 2,2-2,3 1,3-2,3
```

Limits: you can assume that the time limit is in the range [0.01 .. 100] seconds.

Output: this command should produce output of the following form:

```n sequence
```
Where n is the number of stones that the position was reduced to, and sequence is a sequence of moves to achieve that number. A move is represented as from-to, where from and to are squares on the board written as row,column. These coordinates start at the top left with row 1, column 1. There is no whitespace in the middle of a move, but whitespace between moves. Example - see above.
3. ```reduce color time-limit
```
Same as solve, but use the heuristic version of your program, not the exact solver. Be sure to output something before the time limit. But only output one solution. (You may want to write progress of your search to stderr.)
4. ```quit
```
Quit the program. Do not leave any processes running. It will slow down the marking process.

By default, your program is limited to using one computational thread. I.e. you may use other threads e.g. for input/output, but your computation for solve and reduce should only be done in a single thread.

As an option, you can make up for at most 10% of lost marks in your assignment by adding a multithreaded version of your code as follows: Implement a command line option --threads . So if your program is started up with a1 --threads 2 it will be allowed to use up to two computational threads.

If you support this option, clearly indicate this in your documentation. In that case I will also test your code in multithreaded settings, and if it performs better I will award extra marks (within the limits above) at my discretion.

Testing

We will provide several test cases, correct answers for simple cases, and best-achieved answers by a simple program written by me. We will also provide code for this simple program - the basic Nested Monte Carlo code adapted to Solitaire Clobber. In a test file, each line ends with an end of line character '\n'. Each test file ends with a quit command.

Added Jan 22: random test cases and test case generator

• code directory, contains new code and scripts:
• gen.cpp, random test case generator
• gensample-reduce.sh and gensample-solve.sh, which I used to call the generator to create the sample tests below
• testcases directory, contains random test cases
• These cases cover a variety of board sizes. Most files contain only one setboard and two calls to solve or reduce. Each location has a fixed probability of being Black, White or Empty. For reduce this is 45%-45%-10%. For solve it is 40%-40%-20%. I set all time limits to 4.5 seconds arbitrarily. You may want to set to more meaningful values for your testing.
• There is one test file named multicase-reduce.txt which contains multiple test cases.

Verify

We will provide a verify tool which will check the output produced by solve or reduce calls. This tool will be used to evaluate your program's output.

We require that you to test the output of your program with verify as soon as possible. Given the large number of students, we will not be able to fix issues after the submission deadline.

Sample use case for verify:

```a1 < test1.txt > result1.txt
verify result1.txt
```

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 a1 that will run on our test machine X (to be announced).
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 the executable a1 when run as-is on machine X. No extra installation steps please.
4. A directory test, containing 10 test files. The files are named test1.txt,...,test10.txt . Each test file contains one or more valid test cases, and one or more valid calls to solve or reduce as follows: test 1 to 5 should only contain tests for solve, and tests 6 to 10 only for reduce. Do not mix them in one file. Do create some cases that are challenging for your program. I plan to use test cases for cross-testing with all submitted programs.
5. A file named your lastname_firstname_documentation.pdf . This file will contain a 2-3 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 Solitaire Clobber, content of papers, coding tricks etc.

Evaluation

Your program will be evaluated by running it on a number of test cases. The score will be a function of the number cases solved for solve, and the scores achieved for reduce compared to my baseline. Details to be discussed/determined. The weights will be
• 5% test cases
• 15% documentation
• 30% solve
• 50% reduce

Q: Can my reduce function call solve?
A: Sure, if you are confident you can solve something within the time limit given.

Q: Can my solve function call reduce?
A: It depends. It is not permitted to use an incomplete, simulation-based method as the top level (without extra improvements to make it complete), since it cannot guarantee that the solution is optimal. However, it is perfectly OK to use reduce as a subroutine, for example to create a good ordering of moves for the exact search.

Q: Can my solve function return a not proven-optimal result instead of timing out on a hard problem?
A: No, this kind of "speculation" is not allowed for solve. I do realize it is hard to catch, and might be the unintended side effect of a bug. But please do your best to avoid this.

Q: When will the sample code, the sample test cases and the verify program be posted?
A: Working on it...

Q: When will "machine X" be specified? Which computer should I work on?
A: I have asked helpdesk for advice to find the best candidate for machine X. For now, most of you will probably want to work on their own computers or lab machines. But before submitting, please make sure to test that everything works on machine X.

Q: Do I need to code in C/C++?
A: No, anything that is installed on a standard research machine is OK.

(End of Assignment 1)