The ChampAlg Tool

What is it?

ChampAlg is a simple Java tool for testing implementations of algorithms for the course. Currently, ChampAlg is set up with the following problems:

Minimum Spanning Tree.
Traveling Salesman.
Satisfiability.
Chess.
M-N Tic-Tac-Toe (NxN grid, M-size streak to win).
Collaborative filtering.
Graph Drawing.

For optimization problems (and not games), ChampAlg is symmetrically designed from the problem vs. solution viewpoint:

You can write a solution algorithm and have it tested (by algorithms that generate problems).
Alternatively, you can write an algorithm to create fiendishly hard problems and have it "tested" (by solution algorithms).

For some problems (TSP, GD), ChampAlg has a simple GUI to view and compare solutions to actual problem instances.

For games, ChampAlg provides a GUI to observe two algorithms battle each other step-by-step, or to allow a human to play an algorithm.

Getting started

Let us follow these steps to get run and test a simple TSP algorithm:

Start by downloading and unpacking this ZIP file.
Upon unpacking, enter the directory champalg. This is the directory from which you will run the tool, even though the actual algorithms are in sub-directories.

Let's first make sure that it can execute. At the command-line:

    java edu/gwu/champalg/ChampAlg

You should see something like:

    Usage: java edu/gwu/champalg/ChampAlg <properties-file>

Now run the default algorithms for TSP:

    java edu/gwu/champalg/ChampAlg tsp/tsp.props

NOTE: all execution must start in the home directory of the tool. This is because package names have been set up based on this home directory. If you execute from elsewhere, you will get a class-not-found exception.
Next, examine the directories: there should be a sub-directory for each problem.
Examine the file /tsp/tsp.props:
- The properties file for each problem or game (in the case of chess) defines important files and options.
- For optimization problems, set type=problem. For games like chess, set type=game.
- The target determines whether we are interested in evaluating algorithms that "solve" a problem or algorithms can create problem instances. More about this below.
- The mode determines whether we are running a contest or whether a problem-algorithm is in "learn" mode.
The games are treated very differently, so we'll focus on the optimization problems first.
For every optimization problem, there's a separate directory. Examine the contents of /tsp:
- There is a sub-directory for solution-algorithms under which you can place your own. For example, examine the directory tsp/solutionAlgorithms/simha/ - there should be two algorithms for the TSP problem.
  
  Exercise: What is the tour produced by the algorithm Trivial?
- There is a sub-directory for so-called problem-algorithms, algorithms that create problem instances. Again, examine the directory tsp/problemAlgorithms/simha/ - there should be two problem-making algorithms for the TSP problem.
  
  Exercise: How do the two problem algorithms, Uniform and NonUniform, differ?
- There is a /results directory, which contains the results of the execution.
We'll now examine the output graphically:
- Execute the GUI for TSP as follows:
```
       java tsp/TSPViewer
       
```
- Click "load-problem" and load the file problem_SimhaNonUnif_0.txt.
- Click "load-solution" and load the file solution_SimhaTSPTrivial_SimhaNonUnif_0.txt.
- Change the color.
- Now load solution_SimhaTSPGreedy_SimhaNonUnif_0.txt.
Thus, TSPViewer can be used to compare the solutions produced by algorithms on particular problem instances.
NOTE: the files in /results have long names to indicate: (1) whether or not the file represents a problem or a solution; (2) which problem algorithm; (3) which problem instance; (4) which solution algorithm.

Writing a solution algorithm

Let's go through the following steps to write a solution algorithm for TSP:

Start by creating a sub-directory under /tsp/solutionAlgorithms/ with your name. You can do this from the main directory itself, e.g., for username alice
```
    mkdir tsp/solutionAlgorithms/alice
    
```
Write your code by adding to NearestNeighbor.java, making sure you substitute your username where appropriate.
Now, edit tsp/tsp.props to include your algorithm, making sure the full package name (with your new directory) is specified: tsp.solutionAlgorithms.alice.NearestNeighbor.
Your algorithm will need to implement the SolutionAlgorithm interface. See the javadoc for details.
Your algorithm will need to be in the appropriate package, e.g., tsp.solutionAlgorithms.alice.

From the main directory, compile your algorithm:

    javac tsp/solutionAlgorithms/alice/NearestNeighbor.java

Now you are ready to run a test:

    java edu/gwu/champalg/ChampAlg tsp/tsp.props

Writing a problem algorithm

In a similar manner, you can write algorithms to create "nasty" problem instances for solution algorithms to attempt to solve.

The only difference is, you need to create your own directory under tsp/problemAlgorithms such as tsp/problemAlgorithms/alice and write your code to meet the ProblemAlgorithm interface.

About solution vs. problem algorithms:

ChampAlg first calls the problem algorithms to get problem instances (according to the parameters in the properties file).
Then, ChampAlg runs each solution-algorithm on the problem instances.
ChampAlg reports two numbers: (1) the execution time; (2) the solution quality.
If you are a solution-writer, you will want to compete with other solution-algorithms by setting target=solution in the properties file.
ChampAlg can also run a competition of problem-algorithms. In this case, you set target=problem. The idea is to compare problem-algorithms on a set of solution-algorithms. Obviously, the problem-algorithm that creates the hardest problems is the "better" problem algorithm.
Both types of algorithms can place stuff in the properties file to extract later. See the sample problem-algorithms in tsp/problemAlgorithms/simha/ for an example.

Adding a new problem

ChampAlg also makes it easy to add a new problem:

Create a directory for the new problem under which you need directories for /problemAlgorithms, /solutionAlgorithms and /results.
Create a properties file for the problem.
Then, you will need three Java classes:
- The referee for the problem, such as TSPReferee.java that needs to meet the Referee interface.
- A class to hold problem instances such as TSPProblem.java that satisfies the Problem interface.
- A class to hold solution instances such as TSPSolution.java that satisfies the Solution interface.
No GUI is needed - a GUI is entirely optional.
Once these classes have been written and compiled, the properties file specifies where to find them.
No additional code is needed in the ChampAlg section. Essentially, ChampAlg merely handles files and data, loading classes as specified in the properties file.

Adding a new game is an entirely different matter. Both Chess and TicTacToe are written into ChampAlg. Games do not appear to have enough in common to make a common class hierarchy worth the effort.

Writing in a language other than Java

Clearly, Java is not the best language to squeeze "speed" from an implementation.

ChampAlg is written in Java to make it easy to use in the course.

However, you can implement code in C/C++ in the following way:

Use ChampAlg exactly as above but write only the "shell" of your code in Java.
Write your main algorithm code with all the CPU-heavy computation in C/C++.
Find a way to enable your Java "shell" to communicate with your C/C++ code. This can be done in many ways:
- Communicate through files. Since the communication is not time-critical and is likely to occur just once, this is an easy approach. Simply pass the problem data to the C program, and "wait" until it's done.
- Communicate via a socket in a client/server configuration.
- Use JNI, the native interface to Java.