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:

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

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:


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.